Quadratic reciprocity

Is 3 a square modulo a prime \(p\)? Testing small primes, 3 is a residue modulo 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, and a nonresidue modulo 5, 7, 17, 19, 29, 31, 41, 43, 53, 67, 79, 89. The pattern is not obvious until you reduce modulo 12: the first list consists of primes \(\equiv \pm 1 \pmod{12}\), the second of primes \(\equiv \pm 5 \pmod{12}\). Whether 3 is a square modulo \(p\) depends only on \(p\) modulo 12. Similar patterns hold for every \(a\), and they all follow from one theorem relating \(\big(\frac{p}{q}\big)\) and \(\big(\frac{q}{p}\big)\). Euler found it empirically, Legendre gave an incomplete proof, and in 1796, at the age of 18, Gauss proved it, calling it the golden theorem. He published eight different proofs; today there are more than three hundred.

The law of quadratic reciprocity

Theorem (quadratic reciprocity). If \(p\) and \(q\) are distinct odd primes, then \[\Big(\frac{p}{q}\Big)\Big(\frac{q}{p}\Big) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.\]

The exponent is even unless both \(p\) and \(q\) are \(\equiv 3 \pmod 4\). So the theorem says: if at least one of \(p, q\) is \(\equiv 1 \pmod 4\), then \(\big(\frac{p}{q}\big) = \big(\frac{q}{p}\big)\); if both are \(\equiv 3 \pmod 4\), then \(\big(\frac{p}{q}\big) = -\big(\frac{q}{p}\big)\). In words, \(p\) is a square modulo \(q\) exactly when \(q\) is a square modulo \(p\), except when both are \(3 \bmod 4\), in which case exactly one of the two holds.

This is astonishing. The two questions, whether \(x^2 \equiv p \pmod q\) and whether \(y^2 \equiv q \pmod p\) have solutions, concern different moduli and seem to have nothing to do with each other. Yet their answers are locked together. Together with the supplementary laws of lesson 9, \[\Big(\frac{-1}{p}\Big) = (-1)^{\frac{p-1}{2}}, \qquad \Big(\frac{2}{p}\Big) = (-1)^{\frac{p^2-1}{8}},\] reciprocity lets us evaluate any Legendre symbol quickly, by repeatedly reducing and flipping, much as the Euclidean algorithm computes a gcd.

Computing with reciprocity

Example: \(\big(\frac{3}{101}\big)\). Since \(101 \equiv 1 \pmod 4\), \(\big(\frac{3}{101}\big) = \big(\frac{101}{3}\big) = \big(\frac{2}{3}\big) = -1\), agreeing with the long computation by Euler's criterion in lesson 9.

Example: \(\big(\frac{713}{1009}\big)\), where 1009 is prime. Factor \(713 = 23 \cdot 31\). Since \(1009 \equiv 1 \pmod 4\), \(\big(\frac{23}{1009}\big) = \big(\frac{1009}{23}\big) = \big(\frac{20}{23}\big) = \big(\frac{4}{23}\big)\big(\frac{5}{23}\big) = \big(\frac{5}{23}\big) = \big(\frac{23}{5}\big) = \big(\frac{3}{5}\big) = -1\). And \(\big(\frac{31}{1009}\big) = \big(\frac{1009}{31}\big) = \big(\frac{17}{31}\big) = \big(\frac{31}{17}\big) = \big(\frac{14}{17}\big) = \big(\frac{2}{17}\big)\big(\frac{7}{17}\big) = \big(\frac{7}{17}\big) = \big(\frac{17}{7}\big) = \big(\frac{3}{7}\big)\). Now \(3, 7 \equiv 3 \pmod 4\), so \(\big(\frac{3}{7}\big) = -\big(\frac{7}{3}\big) = -\big(\frac{1}{3}\big) = -1\). Hence \(\big(\frac{713}{1009}\big) = (-1)(-1) = 1\): 713 is a square modulo 1009, though finding a square root needs another algorithm.

Example: for which primes \(p > 3\) is 3 a residue? If \(p \equiv 1 \pmod 4\), \(\big(\frac{3}{p}\big) = \big(\frac{p}{3}\big)\), which is 1 iff \(p \equiv 1 \pmod 3\). If \(p \equiv 3 \pmod 4\), \(\big(\frac{3}{p}\big) = -\big(\frac{p}{3}\big)\), which is 1 iff \(p \equiv 2 \pmod 3\). Combining by the Chinese remainder theorem: \(\big(\frac{3}{p}\big) = 1\) iff \(p \equiv 1\) or \(11 \pmod{12}\), the pattern observed above. Similarly, since \(5 \equiv 1 \pmod 4\), \(\big(\frac{5}{p}\big) = \big(\frac{p}{5}\big)\), so 5 is a residue modulo \(p\) iff \(p \equiv \pm 1 \pmod 5\).

In general, reciprocity shows that \(\big(\frac{a}{p}\big)\) depends only on \(p\) modulo \(4|a|\). A question about infinitely many primes is reduced to a finite table.

Eisenstein's lemma

Of the hundreds of proofs, one of the shortest and most visual is due to Gotthold Eisenstein (1844), refining Gauss's third proof. It starts from a parity version of Gauss's lemma. Throughout, \(p\) is an odd prime and \(h = (p - 1)/2\).

Lemma (Eisenstein). If \(a\) is odd and \(p \nmid a\), then \[\Big(\frac{a}{p}\Big) = (-1)^{S}, \qquad S = \sum_{k=1}^{h}\Big\lfloor\frac{ka}{p}\Big\rfloor.\]

Proof. Divide: \(ka = p\lfloor ka/p\rfloor + r_k\) with \(0 < r_k < p\). Let \(s_1, \ldots\) be the remainders below \(p/2\) and \(t_1, \ldots, t_\nu\) those above, as in Gauss's lemma. Summing over \(k = 1, \ldots, h\): \[a\sum k = pS + \sum s_i + \sum t_j.\] In the proof of Gauss's lemma we saw that the numbers \(s_i\) and \(p - t_j\) are exactly \(1, \ldots, h\), so \[\sum k = \sum s_i + \nu p - \sum t_j.\] Subtracting, \((a - 1)\sum k = p(S - \nu) + 2\sum t_j\). Modulo 2, with \(a\) odd and \(p\) odd, this says \(0 \equiv S - \nu\). So \(S \equiv \nu \pmod 2\), and Gauss's lemma gives \(\big(\frac{a}{p}\big) = (-1)^\nu = (-1)^S\).

Counting lattice points

Now let \(p\) and \(q\) be distinct odd primes. By Eisenstein's lemma, \(\big(\frac{q}{p}\big) = (-1)^{S(q,p)}\) and \(\big(\frac{p}{q}\big) = (-1)^{S(p,q)}\), where \[S(q, p) = \sum_{x=1}^{(p-1)/2}\Big\lfloor\frac{qx}{p}\Big\rfloor, \qquad S(p, q) = \sum_{y=1}^{(q-1)/2}\Big\lfloor\frac{py}{q}\Big\rfloor.\] Reciprocity therefore follows from the identity \[S(q, p) + S(p, q) = \frac{p-1}{2}\cdot\frac{q-1}{2}.\]

Proof of the identity. Consider the lattice points \((x, y)\) with \(1 \le x \le (p - 1)/2\) and \(1 \le y \le (q - 1)/2\). There are \(\frac{p-1}{2}\cdot\frac{q-1}{2}\) of them. Draw the line \(y = qx/p\) from the origin through the corner \((p/2, q/2)\) of the rectangle. No lattice point lies on it: \(py = qx\) would force \(p \mid x\), impossible for \(1 \le x < p\). For a fixed \(x\), the points below the line are those with \(1 \le y < qx/p\), and there are \(\lfloor qx/p \rfloor\) of them, all with \(y \le (q - 1)/2\) since \(qx/p < q/2\). So \(S(q, p)\) counts the points below the line. By the same argument with the roles of the axes exchanged, \(S(p, q)\) counts the points above it. Together they count every point exactly once.

The figure shows the case \(p = 7\), \(q = 11\). The columns \(x = 1, 2, 3\) contain \(\lfloor 11/7 \rfloor = 1\), \(\lfloor 22/7 \rfloor = 3\) and \(\lfloor 33/7 \rfloor = 4\) points below the line, 8 in all; the rows \(y = 1, \ldots, 5\) contain \(0, 1, 1, 2, 3\) points to the left of it, 7 in all. So \(\big(\frac{11}{7}\big) = (-1)^8 = 1\) and \(\big(\frac{7}{11}\big) = (-1)^7 = -1\). Check directly: \(11 \equiv 4 = 2^2 \pmod 7\), a residue, and the residues modulo 11 are 1, 3, 4, 5, 9, which do not include 7. Since both primes are \(\equiv 3 \pmod 4\), the symbols must differ, and they do.

Applying the same lemma with \(a = 2\) is not allowed, since \(a\) must be odd; that is why the second supplementary law needs its own argument. Note also what the proof uses: Gauss's lemma, which rests on Euler's criterion, Fermat's theorem and Lagrange's theorem, together with a picture. Few theorems so deep have proofs so short.

The Jacobi symbol

Evaluating \(\big(\frac{713}{1009}\big)\) above required factoring 713. For large numbers factoring is slow, and Jacobi's extension of the symbol removes the need.

Definition. For an odd positive integer \(n = p_1p_2\cdots p_k\) (primes not necessarily distinct), the Jacobi symbol is \[\Big(\frac{a}{n}\Big) = \Big(\frac{a}{p_1}\Big)\Big(\frac{a}{p_2}\Big)\cdots\Big(\frac{a}{p_k}\Big).\]

The Jacobi symbol is multiplicative in both entries, depends only on \(a \bmod n\), and satisfies the same reciprocity law and supplementary laws: for odd coprime positive \(m, n\), \(\big(\frac{m}{n}\big)\big(\frac{n}{m}\big) = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}\). These are proved from the prime case using the facts that \(\frac{ab-1}{2} \equiv \frac{a-1}{2} + \frac{b-1}{2} \pmod 2\) for odd \(a, b\). So the symbol can be computed with a gcd-like algorithm and no factoring: \[\Big(\frac{713}{1009}\Big) = \Big(\frac{1009}{713}\Big) = \Big(\frac{296}{713}\Big) = \Big(\frac{2}{713}\Big)^3\Big(\frac{37}{713}\Big) = \Big(\frac{37}{713}\Big) = \Big(\frac{713}{37}\Big) = \Big(\frac{10}{37}\Big) = \Big(\frac{2}{37}\Big)\Big(\frac{5}{37}\Big),\] using \(713 \equiv 1 \pmod 8\). Then \(\big(\frac{2}{37}\big) = -1\) and \(\big(\frac{5}{37}\big) = \big(\frac{37}{5}\big) = \big(\frac{2}{5}\big) = -1\), so the answer is \(+1\), as before.

A warning: when \(n\) is composite, \(\big(\frac{a}{n}\big) = 1\) does not mean \(a\) is a square modulo \(n\). For example \(\big(\frac{2}{15}\big) = \big(\frac{2}{3}\big)\big(\frac{2}{5}\big) = (-1)(-1) = 1\), but 2 is not a square modulo 15, since it is not a square modulo 3. On the other hand, \(\big(\frac{a}{n}\big) = -1\) does prove that \(a\) is not a square modulo \(n\). The Jacobi symbol is the basis of the Solovay–Strassen primality test of lesson 11.

Applications

Primes dividing values of polynomials. Which primes divide some number of the form \(n^2 + 1\)? Exactly 2 and the primes \(\equiv 1 \pmod 4\), by the first supplementary law. Which divide some \(n^2 - 3\)? Those for which 3 is a residue: 2, 3 and \(p \equiv \pm 1 \pmod{12}\). Which divide some \(n^2 + n + 1\)? Completing the square, \(4(n^2 + n + 1) = (2n + 1)^2 + 3\), so \(p > 3\) divides some value iff \(\big(\frac{-3}{p}\big) = 1\), and by reciprocity \(\big(\frac{-3}{p}\big) = \big(\frac{p}{3}\big)\), so iff \(p \equiv 1 \pmod 3\). Such questions are the beginning of algebraic number theory: they ask how primes factor in rings such as \(\mathbb{Z}[i]\) and \(\mathbb{Z}[\omega]\).

Pépin's test. A Fermat number \(F_k = 2^{2^k} + 1\), \(k \ge 1\), is prime if and only if \(3^{(F_k - 1)/2} \equiv -1 \pmod{F_k}\). One direction is reciprocity: \(F_k \equiv 1 \pmod 4\) and \(F_k \equiv 2 \pmod 3\), so if \(F_k\) is prime, \(\big(\frac{3}{F_k}\big) = \big(\frac{F_k}{3}\big) = \big(\frac{2}{3}\big) = -1\), and Euler's criterion gives the congruence. Pépin's test proved \(F_{14}\) composite in 1963 without finding any factor, and for decades afterward no factor of it was known.

Gauss's search for the reasons behind reciprocity led to cubic and biquadratic reciprocity laws, proved by Eisenstein and Gauss, and ultimately to class field theory and the Langlands program, which still guide research in number theory. Reciprocity is a first glimpse of hidden symmetry among the primes.

Reciprocity by computer

The program verifies the law for all pairs of odd primes below 300, recomputes Eisenstein's counts for \(p = 7, q = 11\), implements the Jacobi symbol algorithm, confirms the pattern for 3 modulo 12, and applies Pépin's test to the Fermat numbers \(F_1\) to \(F_{10}\).

import math

primes = [p for p in range(3, 300) if all(p % d for d in range(2, math.isqrt(p) + 1))]

def legendre(a, p):
    t = pow(a, (p - 1) // 2, p)
    return -1 if t == p - 1 else t

ok = all(legendre(p, q) * legendre(q, p) == (-1) ** ((p - 1) // 2 * (q - 1) // 2)
         for p in primes for q in primes if p != q)
print("reciprocity holds for", len(primes), "primes:", ok)

p, q = 7, 11
below = sum(q * x // p for x in range(1, (p - 1) // 2 + 1))
above = sum(p * y // q for y in range(1, (q - 1) // 2 + 1))
print(f"p={p}, q={q}: below {below}, above {above}, total {below + above}",
      " (11/7) =", legendre(11, 7), " (7/11) =", legendre(7, 11))

def jacobi(a, n):
    assert n > 0 and n % 2 == 1
    a, result = a % n, 1
    while a:
        while a % 2 == 0:
            a //= 2
            if n % 8 in (3, 5):
                result = -result
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            result = -result
        a %= n
    return result if n == 1 else 0

print("(713/1009) =", jacobi(713, 1009), " by Euler:", legendre(713, 1009))
print("(2/15) =", jacobi(2, 15), " squares mod 15:", sorted({x * x % 15 for x in range(15)}))
print("Jacobi agrees with Legendre for primes:", all(jacobi(a, p) == legendre(a, p) for p in primes for a in range(1, p)))
print("(1001/9907) =", jacobi(1001, 9907), " (219/383) =", jacobi(219, 383))
classes = {}
for p in primes[2:]:
    classes.setdefault(legendre(3, p), set()).add(p % 12)
print("p mod 12 when (3/p) = 1:", sorted(classes[1]), " when (3/p) = -1:", sorted(classes[-1]))

for k in range(1, 11):
    F = 2 ** (2 ** k) + 1
    print(f"F_{k} prime by Pepin's test:", pow(3, (F - 1) // 2, F) == F - 1)

reciprocity holds for 61 primes: True
p=7, q=11: below 8, above 7, total 15  (11/7) = 1  (7/11) = -1
(713/1009) = 1  by Euler: 1
(2/15) = 1  squares mod 15: [0, 1, 4, 6, 9, 10]
Jacobi agrees with Legendre for primes: True
(1001/9907) = -1  (219/383) = 1
p mod 12 when (3/p) = 1: [1, 11]  when (3/p) = -1: [5, 7]
F_1 prime by Pepin's test: True
F_2 prime by Pepin's test: True
F_3 prime by Pepin's test: True
F_4 prime by Pepin's test: True
F_5 prime by Pepin's test: False
F_6 prime by Pepin's test: False
F_7 prime by Pepin's test: False
F_8 prime by Pepin's test: False
F_9 prime by Pepin's test: False
F_10 prime by Pepin's test: False

The Jacobi algorithm needs no factorization and runs in time comparable to the Euclidean algorithm. Pépin's test confirms that \(F_1, F_2, F_3, F_4\) (5, 17, 257 and 65537) are prime and that \(F_5\) to \(F_{10}\) are composite. No Fermat prime beyond \(F_4\) is known, and Gauss's theorem on constructible polygons from MATH-323 means that the regular polygons with an odd prime number of sides constructible by ruler and compass are exactly those with 3, 5, 17, 257 and 65537 sides, as far as anyone knows.