A dark field of small dots: one row for each odd prime p up to 439 and one column for each a from 1 to 240, with a light dot wherever a is a square modulo p, so that the pattern of quadratic residues looks random from a distance
Unit 10 · Advanced and Advanced + Analytic Number Theory · 70 min

Quadratic Residues and Quadratic Reciprocity

Which numbers are squares modulo a prime, and Gauss's law that answers it
Image: Own rendering

Half of the non-zero residues modulo an odd prime are squares, and this unit shows how to tell which half. Euler's criterion decides it with one exponentiation, the two supplements settle the cases of minus 1 and 2, and the law of quadratic reciprocity ties the question for p and q together, with a complete proof by Eisenstein's count of lattice points. The Jacobi symbol turns the law into an algorithm that needs no factoring, and the closing section looks at the random-looking sequence of Legendre symbols, the Pólya-Vinogradov inequality, and the least non-residue.

Preview: the beginning of the unit

Unit 4 solved every linear congruence \(ax \equiv b \pmod n\). The next step up is the quadratic congruence \(x^{2} \equiv a \pmod p\), and the first question about it is not how to solve it but whether it has a solution at all. Modulo \(13\), for example, \(3\) is a square, because \(4^{2} = 16 \equiv 3\), while \(2\) is not, and nothing about the two numbers explains why. This unit answers the question completely. The answer is the law of quadratic reciprocity, which ties “is \(q\) a square modulo \(p\)” to “is \(p\) a square modulo \(q\)” for any two odd primes \(p\) and \(q\). Euler had noticed the pattern in his tables by the middle of the eighteenth century, nobody could prove it for fifty years, and the proof that finally came was found by a student of eighteen, who called the result the golden theorem.

1 Squares modulo a prime

Throughout the unit \(p\) is an odd prime unless the text says otherwise. The prime \(2\) is left out because modulo \(2\) every integer is a square (\(0 = 0^{2}\) and \(1 = 1^{2}\)), so there is nothing to decide. An integer \(a\) not divisible by \(p\) is a quadratic residue modulo \(p\) if the congruence \(x^{2} \equiv a \pmod p\) has a solution, and a quadratic non-residue if it has none. The residue \(0\) is a square, but it is counted on neither side, and the words “residue” and “non-residue” in this unit always mean the quadratic kind.

How many of the \(p - 1\) non-zero residues are squares? Exactly half. The squaring map, which sends each non-zero residue \(x\) to \(x^{2}\), sends two residues to each square and never more, because \(x^{2} \equiv y^{2} \pmod p\) means \(p \mid (x - y)(x + y)\), so by Euclid’s lemma (Unit 3) \(y \equiv x\) or \(y \equiv -x\). These two residues are different, because \(x \equiv -x\) would mean \(p \mid 2x\), which is impossible for an odd prime \(p\) that does not divide \(x\). So the \(p - 1\) non-zero residues produce \((p - 1)/2\) squares. The primitive roots of Unit 9 say the same thing in another way. If \(g\) is a primitive root modulo \(p\), the non-zero residues are \(g^{0}, g^{1}, \ldots, g^{p-2}\), and \(a \equiv g^{k}\) is a square exactly when \(k\) is even: an even power \(g^{2m}\) is the square of \(g^{m}\), and if \(g^{k} \equiv (g^{m})^{2}\) then \(g^{k - 2m} \equiv 1\), so \(p - 1\) divides \(k - 2m\), and since \(p - 1\) is even, \(k\) is even. The even exponents \(0, 2, \ldots, p - 3\) are \((p - 1)/2\) in number.

The non-zero residues modulo \(13\) on a circle. Each arrow leads from a residue \(x\) to its square \(x^{2} \bmod 13\), and every one of the six fil…
Figure 1. The non-zero residues modulo \(13\) on a circle. Each arrow leads from a residue \(x\) to its square \(x^{2} \bmod 13\), and every one of the six filled residues, the squares, is reached by exactly two arrows, from \(x\) and from \(13 - x\). Own computation.

A symbol that records the answer in one sign makes everything that follows easier to write. It was introduced by Adrien-Marie Legendre (1752-1833) in his book Essai sur la théorie des nombres (1798).

The full unit is part of the program

Want to see a complete unit first? Unit 3, Prime Numbers and Unique Factorization, is free to read.