Mathematics
Quadratic Reciprocity and Its Proofs
Quick fact
Quadratic reciprocity was first proven by Carl Friedrich Gauss in 1796, and he later published six distinct proofs, calling it the 'golden theorem' of number theory.
Why this is interesting
You know that some numbers are perfect squares, but what about 'squares below a clock'? The question of whether one prime is a square modulo another has a hidden symmetry—one that even Gauss found captivating.
Read the full explanation
Understanding Quadratic Reciprocity and Its Proofs
Imagine working with numbers on a clock (modular arithmetic). A quadratic residue modulo a prime p is a number that can be obtained by squaring some other number, the remainder is the same as that square divided by p. For example, modulo 7, the squares of 1 through 6 give the residues 1, 4, 2, 2, 4, 1, so the quadratic residues are 1, 2, 4. Now, the question of whether a number a is a quadratic residue modulo p is not trivial, but the law of quadratic reciprocity gives an elegant symmetry: if you know whether p is a square modulo q, you can immediately know the answer for q modulo p—unless p and q are both 3 modulo 4, in which case the answer flips with a minus sign. This reciprocity is both surprising and practical, because it allows you to decide quadratic residuosity without brute-force checking.
A deeper explanation
The law is formulated using the Legendre symbol (a/p), which equals 1 if a is a quadratic residue modulo p, -1 if it is not, and 0 if p divides a. The law states: for distinct odd primes p and q, (p/q)(q/p) = (-1)^((p-1)/2 (q-1)/2). This simple formula reveals a deep interdependence between the two primes. The proof relies on a clever counting argument (Euler's criterion) and the fact that the product of all nonzero residues modulo a prime has a specific value—leading to a final sign determined by the exponents. The law is not just an abstract curiosity; it enables fast algorithms for computing Legendre symbols via Jacobi symbols, which is essential in primality testing and cryptography. It also illuminates the structure of prime factorization in rings of integers, connecting to algebraic number theory.