Image: Johann Christian August Schwartz, 1803 (public domain)Gauss's golden theorem
On 8 April 1796 Carl Friedrich Gauss, then eighteen and a student at Göttingen, recorded in his mathematical diary that he had proved a theorem that Euler had guessed and Legendre had stated without a complete proof. He called it the theorema aureum, the golden theorem, and he kept coming back to it: by the end of his life he had published six proofs, and two more were found in his papers. The theorem is now called the law of quadratic reciprocity, and it is the centrepiece of the Disquisitiones Arithmeticae of 1801 and of Unit 10 of this masterclass.
Squares modulo a prime
Fix an odd prime p. An integer a not divisible by p is called a quadratic residue modulo p if a is a square modulo p, that is, if x² ≡ a (mod p) has a solution, and a non-residue otherwise. Modulo 7 the squares of 1, 2, 3, 4, 5, 6 are 1, 4, 2, 2, 4, 1, so the residues are 1, 2, and 4 and the non-residues are 3, 5, and 6. Modulo 13 the residues are 1, 3, 4, 9, 10, and 12. For every odd prime, exactly half of the non-zero residues are squares, because x and -x have the same square and no other pairs do.
Legendre introduced a symbol for this: (a/p) is +1 if a is a residue, -1 if a is a non-residue, and 0 if p divides a. Euler's criterion computes it: (a/p) ≡ a^((p-1)/2) (mod p). The symbol is multiplicative in a, so (ab/p) = (a/p)(b/p), which means that to know every symbol modulo p it is enough to know (-1/p), (2/p), and (q/p) for the odd primes q.
The law
The first two are the supplements. The first says (-1/p) = +1 if p ≡ 1 (mod 4) and -1 if p ≡ 3 (mod 4): the number -1 is a square modulo 13 (since 5² = 25 ≡ -1) and not modulo 7. The second says (2/p) = +1 if p ≡ ±1 (mod 8) and -1 if p ≡ ±3 (mod 8).
The law itself concerns two distinct odd primes p and q and says how (p/q) and (q/p) are related: they are equal, unless both p and q are congruent to 3 modulo 4, in which case they are opposite. In a formula, (p/q)(q/p) = (-1)^((p-1)/2 × (q-1)/2). The exponent is odd exactly when both (p - 1)/2 and (q - 1)/2 are odd, that is, when both primes are 3 modulo 4.
Why is this remarkable? Whether q is a square modulo p is a question about the arithmetic modulo p; whether p is a square modulo q is a question about the arithmetic modulo q. Nothing in the definitions connects the two. The law says they are connected by a rule so simple it fits on a line, and it was the first sign that the primes, taken two at a time, obey laws that are not visible one prime at a time. The search for the right generalization occupied the nineteenth century, became Hilbert's ninth problem in 1900, was answered for abelian extensions by Artin in 1927, and continues in the Langlands programme.
A computation
Is 7 a square modulo 101? Euler's criterion asks for 7^50 mod 101, which is a repeated-squaring job. Reciprocity is faster. Since 101 ≡ 1 (mod 4), the law gives (7/101) = (101/7). Now 101 = 14 × 7 + 3, so (101/7) = (3/7). Apply the law again: 7 ≡ 3 (mod 4) and 3 ≡ 3 (mod 4), so (3/7) = -(7/3), and 7 ≡ 1 (mod 3), so (7/3) = (1/3) = +1. Hence (3/7) = -1 and (7/101) = -1: 7 is not a square modulo 101. Three steps, no powers, and the Sage Cell Server in the resources of Unit 10 confirms it with legendre_symbol(7, 101).
The general method is Euclid's algorithm with a sign bookkeeping: reduce the top modulo the bottom, flip using the law, factor out 2s with the second supplement, repeat. Jacobi showed in 1837 that one can skip the factoring altogether by extending the symbol to odd composite denominators, and the resulting algorithm computes (a/p) in a time comparable to the gcd. Unit 10 of the masterclass works the example (35/97) both ways.
Where the law is used
The immediate use is to decide which primes divide numbers of a given quadratic form. The primes dividing some n² + 1 are 2 and the primes ≡ 1 (mod 4), by the first supplement. The primes dividing some n² - 2 are 2 and those ≡ ±1 (mod 8). The primes dividing some n² + 3 are 3 and those ≡ 1 (mod 3). Every such statement is one application of the law, and they feed into which numbers are sums of two squares, the theory of binary quadratic forms, and the class numbers of Unit 11.
In computation, the law is behind the algorithms for square roots modulo a prime, which elliptic curve cryptography needs on every operation, and behind the quadratic sieve and number field sieve that factor large numbers: both need to know, quickly, for which primes a given number is a residue.
The eight proofs, and the rest
Gauss's first proof, in the Disquisitiones, is by induction and is long. His third proof, of 1808, introduced a lemma now called Gauss's lemma, which counts how many of the numbers a, 2a, ..., ((p-1)/2)a have remainders above p/2, and it is the basis of the proof most textbooks give. Gotthold Eisenstein, in 1844, turned Gauss's third proof into a count of lattice points inside a rectangle cut by a diagonal, which is the proof in Unit 10 of the masterclass, with the figure that makes it transparent. Gauss's fourth and sixth proofs use Gauss sums, which connect the law to the roots of unity and point towards the generalizations.
The proofs did not stop with Gauss. Franz Lemmermeyer's catalogue of published proofs passed two hundred and forty some years ago and is still growing, with proofs from finite fields, from the arithmetic of the Gaussian integers, from the theory of elliptic curves, and from quantum mechanics. Few theorems have been proved so often, and the reason is not doubt. Each proof shows the law from a different side, and a mathematician who finds a new side has usually found something else as well.
Reading the original
The Disquisitiones was written in Latin and finished when Gauss was twenty-one; the printing took until 1801. Section IV contains the law, which Gauss called the fundamental theorem, with its proof by induction, and a table of the cases on page 133 of the first edition. An English translation by Arthur A. Clarke was published in 1966 and is in most university libraries. The diary, found in 1898, records 146 discoveries between 1796 and 1814, the first being the construction of the regular 17-gon on 30 March 1796, nine days before the golden theorem. He was eighteen for both.
Unit 10 of the masterclass proves Euler's criterion and both supplements, gives Eisenstein's proof of the law in full, and uses it for the computation above and for the question of how soon the first non-residue appears, which is where the research spotlight of the unit picks up.


