For distinct odd prime numbers $p,q$, the law of quadratic reciprocity isThus the two Legendre symbols agree unless both prime numbers are congruent to $3$ modulo $4$, in which case they have opposite signs.

For an odd prime number $p$, Euler's criterion states thatwhere the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer $a$.

Apply Euler's criterion to $a$, $b$, and $ab$. Multiplication in modular arithmetic givesIf $p$ divides either factor, both sides are zero. Otherwise both sides belong to $\{-1,1\}$; these two values are distinct modulo the odd prime number $p$. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

The binomial theorem isolates the only terms that can survive reduction modulo the prime number $p$:For $1\le r\le p-1$, neither $r!$ nor $(p-r)!$ is divisible by $p$, whereas $p!$ is. Consequently $p\mid \left(\genfrac{}{}{0ex}{}{p}{r}\right)$, and every intermediate term vanishes in modular arithmetic. ThusThis works for arbitrary integers $a,b$, including those divisible by $p$. It is the additive identity behind the Frobenius endomorphism in characteristic $p$.

Put $a=\omega T$. At emission, $s=2T$, the middle segment givesThe planet is at $x_p=c/\omega$, so the inward light signal takes coordinate timeIts arrival time on the planet is therefore $t_r=2(e^a-1)/\omega$. Subtract this from the mission's return time $4\sinh a/\omega$:For large $T$ at fixed acceleration this tends to $2/\omega =2c/(c\omega )$. With the Earth-gravity value above, the wait is approximately two years, despite the millions of planet-years elapsed since departure in part (i).

At $s=0$ and $s=4T$, the mission is at the planet's position $x=c/\omega$. The final coordinate time from the last segment isThe planet is at rest in these coordinates, so its proper time elapsed equals this coordinate-time difference. The astronauts' proper time is the parameter interval, $4T$. ThereforeFor proper acceleration $c\omega =10\mathrm{m}{\mathrm{s}}^{-2}$ and $c=3\times 10^8\mathrm{m}{\mathrm{s}}^{-1}$, ${\omega }^{-1}=3\times 10^7$ seconds, approximately one year. Thus $\omega T=16$ and $e^{16}\approx 3000^2=9\times 10^6$. Neglecting $e^{-16}$ in the hyperbolic sine,The clocks compare two different timelike paths between the same departure and reunion events.

Differentiate each segment and express the four-velocity using a continuous rapidity:At $T$ both rapidities are $\omega T$; at $3T$ both are $-\omega T$. Hence the four-velocity is continuous at both junctions. This expression also gives $g(U,U)=c^2$ everywhere, so the parameter remains proper time on the later segments.

Away from the junctions,with ${\theta }^{\prime }$ successively $+\omega ,-\omega ,+\omega$. The rapidity is continuous but its slope reverses. Thus the four-acceleration has a finite jump to its negative at each junction, while its magnitude stays $c\omega$ on either side. There is no velocity jump; the idealized path is continuously differentiable but not twice differentiable at the switching events.

Since $s$ is proper time, the four-acceleration isIts Minkowski norm squared is $g(A,A)=-c^2{\omega }^2$, so the invariant magnitude of proper acceleration isThe vector is spacelike, which accounts for the minus sign under the square root.

Take spacetime coordinates $X=(ct,x,y,z)$. Differentiating the initial segment gives the four-velocityThe identity ${\cosh }^{2}r-{\sinh }^{2}r=1$ gives $g(U,U)=c^2$, and $dt/ds=\cosh \omega s>0$. The proper time element therefore satisfies $d{\tau }^2=g(dX,dX)/c^2=d{s}^2$, with the future orientation selecting $d\tau =ds$. Thus $s$ is proper time along this path.

Fix $w\in W$. It has five incident edges, so three of them have the same color by the pigeonhole principle. Suppose they are red, with other endpoints $a,b,c$. Any existing edge among $a,b,c$ must be blue, or it would complete a red triangle with $w$.

If all three edges among $a,b,c$ existed, they would therefore form a blue triangle. Thus their triple must contain the unique missing edge $uv$. In particular, both $u$ and $v$ belong to the three red neighbors, so $wu$ and $wv$ are both red. The identical argument works if the chosen three edges are blue.

Therefore $wu$ and $wv$ have the same color for every $w\in W$. The missing edge is crucial: it is the only way the monochromatic neighbor triangle can fail to be present.

Put $A=R(k-1,\ell )$, $B=R(k,\ell -1)$ and consider any coloring of $K_{A+B}$. Choose a vertex $v$. Among its $A+B-1$ neighbors, either at least $A$ are joined to it by red edges, or at least $B$ by blue edges.

In the red case, the induced complete graph on those neighbors contains either a red $K_{k-1}$, which joins with $v$ to make a red $K_k$, or a blue $K_{\ell }$. The blue case similarly gives a red $K_k$ or a blue $K_{\ell -1}$ which extends with $v$ to a blue $K_{\ell }$. Hence every coloring has the required configuration, andThis is the Ramsey number recursion.

The Ramsey number $R(k,\ell )$ is the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ has a red $K_k$ or a blue $K_{\ell }$. Equivalently, every $N$-vertex graph has a clique of size $k$ or an independent set of size $\ell$.

For $N=k$, either there is a blue edge or every edge is red, producing the red $K_k$. Conversely an entirely red $K_{k-1}$ has neither a red $K_k$ nor a blue edge. Therefore

Take the complete bipartite graph $\boxed{K_{3,4}}$. Its seven vertices have degrees four on one side and three on the other. Deleting any two vertices leaves at least one vertex on each side, so the remaining complete bipartite graph is connected.

Every cycle in a bipartite graph alternates between its two parts, using equal numbers of vertices from each. A Hamilton cycle here would have to use three vertices from one part and four from the other, which is impossible. Thus three-vertex connectivity and minimum degree three do not suffice for Hamiltonicity in this seven-vertex example.

Let $v_1\dots v_k$ be a longest path in the finite simple graph. Every neighbor of either endpoint lies on this path, since an outside neighbor would extend it. Define two subsets of $\{1,\dots ,k-1\}$:Their sizes are $d(v_1)$ and $d(v_k)$. The degree hypothesis gives $|I|+|J|\ge n\ge k$, but there are only $k-1$ possible indices. Hence some $i$ belongs to both. The edges at that index close a cycle through every vertex of the path:The graph is connected: any component has at least $n/2+1$ vertices by the minimum degree, so two components would exceed $n$ vertices. If $k<n$, connectedness gives an edge from this cycle to an outside vertex. Starting at that vertex and traversing the cycle without its closing edge gives a path with $k+1$ vertices, a contradiction.

Thus $k=n$ and the cycle is a Hamilton cycle, proving Dirac's theorem. The overlap-of-indices argument is why the degree threshold is half the number of vertices.

A Hamilton cycle is a cycle visiting every vertex of a finite graph exactly once before returning to its starting point. A Hamilton path is a path visiting every vertex exactly once, with no requirement to return or to have its endpoints adjacent. Both conditions concern visiting vertices, rather than traversing every edge.

The tangent space at the identity is the kernel of a linear map from part (i):This says precisely that $JH$ is skew-symmetric. Since $J^{-1}=J$, multiplication by $J$ identifies this tangent space with the three-dimensional space of skew-symmetric $3\times 3$ matrices. In entries it isSubstitution verifies the equation directly and displays its three independent parameters.

Use the six-dimensional vector space of real symmetric $3\times 3$ matrices as the target, rather than all nine matrix entries independently. DefineIts derivative isThe given $J$ is symmetric with $J^2=I$. Every $A\in G$ is invertible, since taking determinants of $A^{T}JA=J$ gives $(\det A{)}^2=1$. For any symmetric target $S$, chooseThen $A^{T}JH=\frac{1}{2}JJS=S/2$, and its transpose is also $S/2$. Thus $D{F}_A(H)=S$ and the derivative is surjective at every point of $G$.

The regular level set theorem now givesIt also proves smooth embeddedness in the entire ambient vector space of matrices. The target symmetry is what gives the correct codimension.

Choose any pair $(a,b)$ from part (i), and put $A=2^a{3}^b$. The divisibilities of the exponents makepositive integers. Their powers areThus $x^3+y^5=z^7$, with all three powers nonzero and distinct. For example, take $a=84+105t$, $b=90+105t$ for every nonnegative integer $t$. Then $A$ strictly increases, giving infinitely many distinct solutions. The construction uses modular congruences to turn the elementary identity $A+2A=3A$ into three prescribed perfect powers.

Writing $a=21r$, the second condition becomes $r\equiv 4(\mathrm{mod}5)$. Writing $b=15s$, its second condition becomes $s\equiv 6(\mathrm{mod}7)$. Consequentlygives an infinite set of positive integer solutions. Conversely these are the positive solutions in the indicated congruence classes, by the Chinese remainder theorem.

Because $p$ is odd, $x$ must be odd. Every odd square is $1$ modulo eight. If $y$ is even, $2y^2$ is zero modulo eight; if $y$ is odd, it is two modulo eight. ThusMore precisely, the first case has even $y$ and the second has odd $y$. These are necessary conditions on the congruence class, as requested; the elementary calculation alone does not prove their sufficiency.

Equivalently, reduction modulo $p$ makes $-2$ a quadratic residue: $p$ cannot divide $y$, since that would also force $p\mid x$ and hence $p^2\mid p$. The two supplementary laws and multiplicativity of the Legendre symbol give the same two allowed classes.

Gauss's lemma states that, for $p\nmid a$, if $N$ of the least positive residues of $a,2a,\dots ,((p-1)/2)a$ exceed $p/2$, then $(a/p)=(-1{)}^N$.

For $a=2$, the residues are simply $2,4,\dots ,p-1$, with no reduction needed. Write $m=(p-1)/2$. A term $2j$ exceeds $p/2$ exactly when $j>p/4$, soIf $p$ is congruent to $1,3,5,7$ modulo eight, the parity of this count is respectively even, odd, odd, even. Gauss's lemma therefore givesThis proves the second supplementary law for quadratic reciprocity, rather than merely applying it.