The Law of Quadratic Reciprocity

We arrive at what Gauss called the golden theorem — he gave eight different proofs of it over his lifetime. It links two seemingly unrelated questions: "is p a square mod q?" and "is q a square mod p?" Astonishingly, the two answers are almost always the same.

The law

For distinct odd primes p and q,

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.

The exponent is even unless both primes are \equiv 3 \pmod 4. So:

The supplements

Reciprocity handles odd primes; two companion rules (the "supplements") finish the job for the special tops -1 and 2:

\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}, \qquad \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}.

The second says 2 is a square modulo p exactly when p \equiv \pm 1 \pmod 8.

A worked evaluation

Reciprocity makes Legendre symbols computable by flipping and reducing, like a Euclidean algorithm for residues. Is 3 a square modulo 13? Since 13 \equiv 1 \pmod 4, flip freely:

\left(\frac{3}{13}\right) = \left(\frac{13}{3}\right) = \left(\frac{1}{3}\right) = +1.

Yes — and indeed 4^2 = 16 \equiv 3 \pmod{13}. No squaring of all residues was needed; the reciprocity law alone cracked it. Extending the symbol to composite bottoms gives the Jacobi symbol, which makes this flipping fully algorithmic.