Quadratic reciprocity

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 a fixed positive odd integer $n$, the Legendre symbol $(n/p)$ for odd prime denominators depends only on $p$ modulo $4n$. For prime numerator $r$, quadratic reciprocity expresses it as $(p/r)$ times a sign determined by $p$ modulo four. Factorization of $n$ and multiplicativity prove the general statement. If a denominator divides $n$, the congruence forces the other prime denominator to be identical, so the zero cases agree too.

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.

A short proof outline connects Gauss's lemma to counting points with integer coordinates. For distinct odd primes $p,q$, define the two floor function sumsThe parity form of Gauss's lemma gives $(q/p)=(-1{)}^M$ and $(p/q)=(-1{)}^N$. In the open rectangle $0<x<p/2$, $0<y<q/2$, the line $y=qx/p$ separates $M$ points below it from $N$ points above it. None lies on the line, because $py=qx$ and coprimality would force $p\mid x$. The total is therefore $(p-1)(q-1)/4$. Combining that count with the parity identities gives quadratic reciprocity.^[ref]

For an odd prime $p\ne 3$, quadratic reciprocity givesThus $-3$ is a square modulo $p$ exactly when $p\equiv 1(\mathrm{mod}3)$.

The factorizationshows that $X^3=-1$ always has $X=-1$ as a solution. For $p\ne 3$, it has two further solutions exactly when $-3$ is a quadratic residue; for $p=3$, all three factors coalesce at the unique root $-1$.