TheoremProved

Law of quadratic reciprocity

Statement

For distinct odd primes $p,q$ , $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$ , where $\left(\dfrac{\cdot}{\cdot}\right)$ denotes the Legendre symbol.

Why is it true?

It links two seemingly unrelated questions — whether $p$ is a perfect square modulo $q$ , and whether $q$ is a perfect square modulo $p$ — showing they almost always agree, and differ only when both primes leave remainder $3$ upon division by $4$ .

Proof sketch

Gauss gave several distinct proofs over his lifetime. One classical route (following Eisenstein) uses Gauss's lemma to express each Legendre symbol as a sign determined by counting certain residues, then counts lattice points in a rectangle in two different ways; a geometric symmetry (reflecting the rectangle through its centre) matches the two counts and yields the reciprocity formula.

Stated by

stated 1783Leonhard Euler

Proved by

proved 1796Carl Friedrich Gauss

Topics that use this theorem

Quadratic residues

Related theorems

Fermat's little theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Carl Friedrich Gauss (trans. Arthur A. Clarke) (1986). Disquisitiones Arithmeticae · DOI:10.1007/978-1-4939-7560-0
Kenneth Ireland, Michael Rosen (1990). A Classical Introduction to Modern Number Theory · DOI:10.1007/978-1-4757-2103-4