Quadratic Reciprocity

Why quadratic reciprocity matters

• Foundation of algebraic number theory. First non-trivial reciprocity law — the prototype for all of class field theory. Cubic, biquadratic, octic, and Artin reciprocity are all generalisations.
• Fast primality tests. Solovay-Strassen and Miller-Rabin both lean on Jacobi-symbol computations that run in O(log² n) only because reciprocity allows the symbol to flip with the Euclidean algorithm.
• Solving x² ≡ a (mod p). Tonelli-Shanks and Cipolla algorithms solve modular square roots; both first call (a|p) — produced via reciprocity — to confirm a solution exists.
• Elliptic curve cryptography. Counting points on y² = x³ + ax + b mod p uses the Legendre symbol of x³ + ax + b for each x; over thousands of primes this informs cryptographic curve selection.
• Class numbers and Pell equations. Whether x² − D y² = -1 has solutions, whether sqrt(D) has odd or even continued-fraction period, and the structure of the class group of Q(sqrt(D)) all hinge on Legendre-symbol patterns governed by reciprocity.
• Distribution of primes in arithmetic progressions. Dirichlet's theorem and the analytic structure of L-functions for quadratic characters depend on quadratic reciprocity — it is the input that turns "arithmetic mod q" into a workable analytic object.
• Educational pinnacle. The deepest result a student typically meets in an undergraduate number theory course; offers an honest taste of how mathematicians find, conjecture, and prove patterns at the boundary of tractability.

Common misconceptions

• "Quadratic reciprocity is obvious or trivial." The statement compresses an extraordinary depth: there is no elementary reason (a|p) and (p|a) should be related at all. Gauss called it the Golden Theorem precisely because it is not obvious — and the 240+ proofs each illuminate a different facet (Gaussian sums, theta functions, lattices, p-adic analysis, algebraic geometry).
• "It only applies to primes." The Legendre symbol is defined only for prime moduli, but the Jacobi symbol generalises (a|n) to any positive odd n via multiplicativity. Reciprocity holds for the Jacobi symbol (with the same exponent) — and that is what powers Solovay-Strassen on composite candidates.
• "Gauss invented it." Euler conjectured an equivalent statement in 1744 and Legendre stated the modern form in 1785. Gauss gave the first complete proof in 1796 — and credited Euler explicitly. The cultural attachment of the theorem to Gauss reflects his proofs and his elevation of it to centerpiece status, not original discovery.
• "(a|p) = +1 means a is a square in Z." No — only mod p. (3|7) = +1 because 3 ≡ 25 = 5² (mod 7), but 3 is not a perfect square in the integers. The Legendre symbol asks a strictly modular question.
• "The supplementary laws are trivial corollaries." The supplements (-1|p) = (-1)^((p-1)/2) and (2|p) = (-1)^((p²-1)/8) are independent statements with their own proofs. They handle cases not covered by reciprocity (where the bottom is prime but the top is -1 or 2) and are typically proven first using Gauss's lemma.
• "Reciprocity computes (a|p) instantly." It reduces (a|p) by Euclidean-like steps. Each step costs a multiplication and a sign update; total cost is O(log² p) bit operations — fast, but not free, and dramatically faster than computing a^((p-1)/2) mod p directly only because Euler's criterion exponent grows linearly with p.

A worked example

Compute (29|53). Both primes are ≡ 1 (mod 4), so reciprocity gives (29|53) = (53|29). Reduce 53 mod 29 = 24, so (53|29) = (24|29) = (8|29)(3|29) = (2|29)³(3|29). Since 29 ≡ 5 (mod 8), (2|29) = -1, so (2|29)³ = -1. Now (3|29): 29 ≡ 1 (mod 4), reciprocity gives (3|29) = (29|3) = (2|3) = -1. Therefore (29|53) = (-1)(-1) = +1, so 29 is a quadratic residue mod 53. Check: 23² = 529 = 9·53 + 52 ≡ 52 (mod 53)… try harder, 32² = 1024 = 19·53 + 17, 9² = 81 ≡ 28, but eventually 24² = 576 = 10·53 + 46 ≡ 46, etc. The reciprocity-based answer is correct, and far cheaper than scanning all residues.

A short history

Euler stated equivalent forms of the law in 1744 and 1772 in his work on Diophantine equations and Fermat's two-square theorem. Legendre coined the symbol (a|p) in 1785 and gave the modern statement, but his attempted proof had a gap (he assumed the existence of primes in certain progressions, a fact later supplied by Dirichlet's theorem). Gauss filled the gap in 1796 in his Disquisitiones Arithmeticae, calling reciprocity the "fundamental theorem" of his number theory. Over the next 200 years, mathematicians produced over 240 distinct proofs — using Gauss sums, theta functions, lattices, p-adic analysis, étale cohomology, and Galois cohomology — each illuminating a different bridge between elementary number theory and modern algebraic frameworks.