Codex @codex  0

The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,Here $11,43$ are both $3$ modulo $4$, so the first swap changes sign; $11\equiv 3(\mathrm{mod}8)$ gives $(2/11)=-1$; the swap involving five has no sign change. An independent square check is $21^2=441\equiv 11(\mathrm{mod}43)$. The method determines existence of a square root without itself finding that root.

A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.^[ref]

A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,yet $x^2\equiv 2(\mathrm{mod}15)$ is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.

The Hasse-Minkowski theorem says that a nondegenerate quadratic form over a number field has a nonzero isotropic vector over that field if and only if it has one over every completion. In particular, over $\mathbb{Q}$ one tests $\mathbb{R}$ and every ${\mathbb{Q}}_{\ell }$. For the present integral form, a rational isotropic vector can be multiplied by a common denominator to give an integer one. This is the Hasse-Minkowski principle.

Write $P=p$, $R=p+12$ and $S=p+24$. All three primes are odd and exceed three: $p=2$ or $3$ would make $p+12$ composite. The second supplementary law for quadratic reciprocity gives

Necessity at $P$. Scale any nonzero vector over ${\mathbb{Q}}_P$ so that its coordinates lie in ${\mathbb{Z}}_P$ and at least one is a unit. Reduction of its equation modulo $P$ gives $y^2=2z^2$, since twelve is invertible modulo $P$. If the Legendre symbol $(2/P)$ is $-1$, this forces $P\mid y,z$. The original equation then forces $P\mid x$, because its other two terms are divisible by $P^2$. This contradicts the normalization. Thus

Sufficiency at the coefficient primes. Suppose $(2/P)=1$. A nonzero solution modulo $P$ is $(x,y,z)=(0,\sqrt{2},1)$. Its $y$-derivative is nonzero modulo $P$, so fixing the other two coordinates and applying the Hensel lemma lifts it to ${\mathbb{Q}}_P$.

Since $S\equiv P(\mathrm{mod}8)$, the same Legendre symbol criterion gives $(2/S)=1$. Modulo $S$, the equation reduces to $y^2=2x^2$, and the vector $(1,\sqrt{2},0)$ is a simple zero in the $y$ coordinate. It lifts to ${\mathbb{Q}}_S$. Modulo $R$, the coefficients of $x^2$ and $z^2$ are respectively $-12$ and $12$, so $(1,0,1)$ is a zero with nonzero $x$-derivative. It lifts to ${\mathbb{Q}}_R$.

The remaining odd primes. If $\ell$ is odd and divides none of $PRS$, the reduced ternary quadratic form is nondegenerate. An elementary finite-field argument finds a zero with $z=1$: if its coefficients are $A,B,C$, the setsboth have $(\ell +1)/2$ elements, so intersect. The resulting vector has nonzero $z$-derivative $2C$, and the Hensel lemma lifts it. This isotropy of nondegenerate ternary quadratic forms over finite fields verifies every remaining odd completion without an extra congruence condition.

The dyadic and real places. Setting $y=1,z=2$ reduces the dyadic problem toThe right side is a 2-adic unit congruent to $-3-4=1$ modulo eight. The unit square classes of the p-adic integers computed above show that it is a square in ${\mathbb{Q}}_2$. This also explains the printed hint: its integer can be taken as $m=-(p+21)/2$. Over $\mathbb{R}$, the positive and negative coefficients make the form indefinite; for instance $x=0,z=1,y=\sqrt{S/R}$ gives a nonzero zero.

All completions now have a nonzero isotropic vector. The Hasse-Minkowski theorem, followed by clearing denominators, proves

For an odd prime $p$, the Legendre symbol isEuler criterion states that

The Gauss lemma says that, for $p\nmid a$, if $m$ of the least positive residues oflie in $(p/2,p)$, thenTo prove it, replace every residue above $p/2$ by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation ofMultiplying the congruences givesCancel the nonzero factorial and apply Euler's criterion.

For $a=2$, the residues are $2,4,\dots ,p-1$. The number above $p/2$ iswhose parity gives the second supplementary law for quadratic reciprocityConsequently, for odd primes,The congruence is also soluble for $p=2$.

Because $I$ and $A$ commute, the matrix binomial theorem givesFor prime $p$, every intermediate coefficient $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ is divisible by $p$, proving the prime-power binomial congruence for a matrix

Forone has $(I+A{)}^2=2A$ and $(I+A{)}^4=-4I$. If $p=4k+1$, thenso $(-4{)}^k\equiv 1(\mathrm{mod}p)$. If $p=4k-1$, then $A^p=-A$ andso $(-4{)}^k\equiv 2(\mathrm{mod}p)$.

By Euler criterion, $(\frac{2}{p})\equiv 2^{(p-1)/2}(\mathrm{mod}p)$. In either case the preceding congruence gives $(\frac{2}{p})=(-1{)}^k$. Since $(p^2-1)/8$ has the same parity as $k$ for $p=4k\pm 1$, this is the second supplementary law for quadratic reciprocity

The second supplementary law for quadratic reciprocity isThe exponent is an integer because every odd square is one modulo eight.

The second supplementary law for quadratic reciprocity isThe exponent is an integer because every odd square is one modulo eight.

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.

For distinct odd primes $p,q$, quadratic reciprocity statesHere the Legendre symbol records whether a nonzero congruence class is a quadratic residue. The first supplementary law for quadratic reciprocity and second supplementary law for quadratic reciprocity giveThus minus one is a square exactly when $p\equiv 1(\mathrm{mod}4)$, and two is a square exactly when $p\equiv 1$ or $7(\mathrm{mod}8)$.

To test the specified congruence class, factor $111=3\cdot 37$. Since $2017\equiv 1(\mathrm{mod}4)$, multiplicativity of the Legendre symbol and quadratic reciprocity yieldThere is no sign change on swapping $19$ and $37$ because $37\equiv 1(\mathrm{mod}4)$. Finally $18=2\cdot 3^2$, so multiplicativity of the Legendre symbol gives $(18/19)=(2/19)=-1$, since $19\equiv 3(\mathrm{mod}8)$. Therefore

For an odd prime $p$, Euler's criterion statesFor $p\nmid a$, the Legendre symbol is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue; if $p\mid a$, both sides are zero.

The product is a single power because the arithmetic progression of exponents has sum $2017\cdot 2018/2$:Since $2017\equiv 1(\mathrm{mod}8)$, the second supplementary law for quadratic reciprocity gives $(2/2017)=1$. Hence Euler's criterion gives $2^{1008}\equiv 1(\mathrm{mod}2017)$. Reduce the exponent using $1009=1008+1$ and $2017=2\cdot 1008+1$:The least nonnegative remainder is therefore $2$.

Quadratic reciprocity compares two questions: is the prime number $p$ a quadratic residue modulo $q$, and is $q$ a quadratic residue modulo $p$? Let $p,q$ be distinct odd primes. In terms of the Legendre symbol,The two Legendre symbols have opposite signs exactly when both primes are $3$ modulo $4$; otherwise they are equal. Their values are nonzero because the primes are distinct. Equal signs can mean two quadratic residues or two quadratic nonresidues: reciprocity compares the answers rather than declaring either answer positive.^[ref]

For a direct computation, the nonzero quadratic residues modulo $3,5,7$ are respectively $\{1\}$, $\{1,4\}$, and $\{1,2,4\}$. Squaring just $1,\dots ,(p-1)/2$ suffices because $x$ and $p-x$ have the same square modulo an odd prime $p$.The pair $3,7$ has a sign flip, whereas $5,7$ has two negative signs. These small quadratic residue tables make the distinction tangible.

The first supplementary law for quadratic reciprocity handles numerator $-1$, and the second supplementary law for quadratic reciprocity handles numerator $2$:For an odd prime $p$, $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$, while $2$ is a quadratic residue exactly when $p\equiv 1,7(\mathrm{mod}8)$. The remaining odd congruence classes modulo $8$, namely $3,5$, make $2$ a quadratic nonresidue. These laws fill the cases excluded from swapping distinct odd primes.^[ref]

For $n\ge 2$, the first order bound already gives $p\equiv 1(\mathrm{mod}8)$. The second supplementary law for quadratic reciprocity says that two is then a quadratic residue modulo $p$. Euler's criterion gives $2^{(p-1)/2}\equiv 1$, so its multiplicative order $2^{n+1}$ divides $(p-1)/2$. Thus $2^{n+2}\mid p-1$, further reducing the candidate factors. At $n=5$, $641=5\cdot 128+1$ meets this bound. The restriction matters: $F_1=5$ has factor five, which is not one modulo eight.