Quadratic residues and the Legendre symbol

Linear congruences are completely understood: lesson 5 says exactly when \(ax \equiv b \pmod n\) is solvable. The next step is quadratic congruences, and they are much more interesting. Which numbers are perfect squares modulo a prime \(p\)? Is 3 a square modulo 101? Is 101 a square modulo 3? Fermat, Euler, Legendre and Gauss all worked on such questions, and the answer, the law of quadratic reciprocity proved in the next lesson, is one of the jewels of mathematics. This lesson builds the tools: quadratic residues, Euler's criterion, the Legendre symbol and Gauss's lemma, and applies them to the question of which primes are sums of two squares.

Reducing to square roots

For an odd prime \(p\) and \(p \nmid a\), the general quadratic congruence \(ax^2 + bx + c \equiv 0 \pmod p\) reduces to taking a square root, just as over the real numbers. Multiply by \(4a\), which is invertible modulo \(p\), and complete the square: \[(2ax + b)^2 \equiv b^2 - 4ac \pmod p.\] So the congruence is solvable exactly when the discriminant \(D = b^2 - 4ac\) is a square modulo \(p\), and if \(y^2 \equiv D\), then \(x \equiv (2a)^{-1}(-b \pm y)\). For example \(x^2 + 3x + 5 \equiv 0 \pmod{11}\): \(D = 9 - 20 = -11 \equiv 0\), so there is the single (double) root \(x \equiv -3 \cdot 2^{-1} \equiv -3 \cdot 6 = -18 \equiv 4\). Check: \(16 + 12 + 5 = 33 \equiv 0\).

Quadratic residues

Definition. Let \(p\) be an odd prime and \(p \nmid a\). Then \(a\) is a quadratic residue modulo \(p\) if \(x^2 \equiv a \pmod p\) has a solution, and a quadratic nonresidue otherwise. (Multiples of \(p\) are treated separately and are neither.)

Theorem. Modulo an odd prime \(p\), exactly \((p - 1)/2\) of the numbers \(1, \ldots, p - 1\) are quadratic residues, namely the squares \(1^2, 2^2, \ldots, \big(\frac{p-1}{2}\big)^2\), and the other \((p - 1)/2\) are nonresidues. Each residue has exactly two square roots.

Proof. Since \((p - x)^2 \equiv x^2\), every square is one of the squares of \(1, \ldots, (p - 1)/2\). These are distinct: if \(x^2 \equiv y^2\), then \(p \mid (x - y)(x + y)\), so \(x \equiv \pm y\), and for \(x, y\) in \(1, \ldots, (p - 1)/2\) the sum \(x + y\) lies strictly between 0 and \(p\), forcing \(x = y\). So there are exactly \((p - 1)/2\) residues, each the square of exactly two classes, \(\pm x\).

The figure shows the squaring map modulo 11. Each residue receives exactly two arrows, one green and one blue, and the nonresidues receive none. The residues modulo 11 are 1, 3, 4, 5, 9. Modulo 13 they are 1, 3, 4, 9, 10, 12, which includes \(12 \equiv -1\); modulo 11, \(-1 \equiv 10\) is not a residue. Explaining that difference is our first goal.

If \(g\) is a primitive root modulo \(p\), the residues are exactly the even powers of \(g\): \(g^{2k} = (g^k)^2\) is a square, and the \((p - 1)/2\) even powers already account for all the residues. So \(a\) is a residue iff \(\operatorname{ind}_g(a)\) is even. This immediately shows that residue times residue is a residue, residue times nonresidue is a nonresidue, and nonresidue times nonresidue is a residue, since indices add. The last rule is a surprise at first: 2 and 6 are nonresidues modulo 11, and \(12 \equiv 1\) is a residue.

Euler's criterion

Theorem (Euler's criterion). Let \(p\) be an odd prime and \(p \nmid a\). Then \(a^{(p-1)/2} \equiv \pm 1 \pmod p\), with \(+1\) if \(a\) is a quadratic residue and \(-1\) if it is a nonresidue.

Proof. By Fermat, \(\big(a^{(p-1)/2}\big)^2 = a^{p-1} \equiv 1\), so \(a^{(p-1)/2}\) is a root of \(x^2 \equiv 1\), whose only roots are \(\pm 1\). If \(a \equiv x^2\), then \(a^{(p-1)/2} \equiv x^{p-1} \equiv 1\). So all \((p - 1)/2\) residues are roots of \(x^{(p-1)/2} \equiv 1\), and by Lagrange's theorem this congruence has no other roots. Hence for a nonresidue \(a^{(p-1)/2} \not\equiv 1\), so it is \(-1\).

Euler's criterion turns the question into a computation that square-and-multiply does quickly, even for primes with hundreds of digits. Is 3 a residue modulo 101? \(3^{50} \bmod 101\): \(3^5 = 243 \equiv 41\), \(3^{10} \equiv 41^2 = 1681 \equiv 65\), \(3^{20} \equiv 65^2 = 4225 \equiv 84 \equiv -17\), \(3^{40} \equiv 289 \equiv -14\), and \(3^{50} = 3^{40}3^{10} \equiv -14 \cdot 65 = -910 \equiv -910 + 909 = -1\). So 3 is a nonresidue modulo 101.

The Legendre symbol

Definition. For an odd prime \(p\), the Legendre symbol is \[\Big(\frac{a}{p}\Big) = \begin{cases} 1 & \text{if } p \nmid a \text{ and } a \text{ is a quadratic residue}, \\ -1 & \text{if } a \text{ is a nonresidue}, \\ 0 & \text{if } p \mid a. \end{cases}\] Legendre introduced it in 1798. Euler's criterion now reads \(\big(\frac{a}{p}\big) \equiv a^{(p-1)/2} \pmod p\).

Properties. For an odd prime \(p\):

• If \(a \equiv b \pmod p\), then \(\big(\frac{a}{p}\big) = \big(\frac{b}{p}\big)\).

• \(\big(\frac{ab}{p}\big) = \big(\frac{a}{p}\big)\big(\frac{b}{p}\big)\): the symbol is completely multiplicative in \(a\). This follows from Euler's criterion, since \((ab)^{(p-1)/2} = a^{(p-1)/2}b^{(p-1)/2}\) and the values \(\pm 1\) are distinct modulo \(p\).

• \(\big(\frac{a^2}{p}\big) = 1\) for \(p \nmid a\).

• \(\sum_{a=1}^{p-1}\big(\frac{a}{p}\big) = 0\), since there are equally many residues and nonresidues.

Multiplicativity means that to evaluate \(\big(\frac{a}{p}\big)\) it is enough to know \(\big(\frac{-1}{p}\big)\), \(\big(\frac{2}{p}\big)\) and \(\big(\frac{q}{p}\big)\) for odd primes \(q\). For example \(\big(\frac{-12}{13}\big) = \big(\frac{-1}{13}\big)\big(\frac{4}{13}\big)\big(\frac{3}{13}\big) = \big(\frac{-1}{13}\big)\big(\frac{3}{13}\big)\).

When is −1 a square?

Theorem (first supplementary law). For an odd prime \(p\), \[\Big(\frac{-1}{p}\Big) = (-1)^{(p-1)/2} = \begin{cases} 1 & p \equiv 1 \pmod 4, \\ -1 & p \equiv 3 \pmod 4. \end{cases}\]

Proof. Euler's criterion gives \(\big(\frac{-1}{p}\big) \equiv (-1)^{(p-1)/2}\), and both sides are \(\pm 1\). For \(p \equiv 1 \pmod 4\) one can even write down a square root of \(-1\): by Wilson's theorem, \(x = \big(\frac{p-1}{2}\big)!\) satisfies \(x^2 \equiv -1\). For \(p = 13\), \(6! = 720 \equiv 5\), and \(5^2 = 25 \equiv -1\).

An application: there are infinitely many primes \(p \equiv 1 \pmod 4\). Given such primes \(p_1, \ldots, p_k\), let \(N = (2p_1\cdots p_k)^2 + 1\). Any prime \(p\) dividing \(N\) is odd and satisfies \((2p_1\cdots p_k)^2 \equiv -1 \pmod p\), so \(-1\) is a residue and \(p \equiv 1 \pmod 4\); and \(p\) is none of the \(p_i\). This complements the argument in lesson 3 for primes \(\equiv 3 \pmod 4\).

Sums of two squares

Which primes are sums of two squares? \(2 = 1 + 1\), \(5 = 1 + 4\), \(13 = 4 + 9\), \(17 = 1 + 16\), \(29 = 4 + 25\), \(37 = 1 + 36\), \(41 = 16 + 25\), while 3, 7, 11, 19, 23, 31, 43 are not. Lesson 1 showed that a number \(\equiv 3 \pmod 4\) is never a sum of two squares. Fermat stated in 1640 that every prime \(p \equiv 1 \pmod 4\) is one; Euler published the first proof in 1752 after years of effort.

Theorem (Fermat). An odd prime \(p\) is a sum of two squares if and only if \(p \equiv 1 \pmod 4\).

Proof (after Thue). Let \(p \equiv 1 \pmod 4\) and choose \(x\) with \(x^2 \equiv -1 \pmod p\), which exists by the first supplementary law. Let \(m = \lfloor\sqrt p\rfloor\), so \(m < \sqrt p < m + 1\) (\(p\) is not a square). Consider the \((m + 1)^2 > p\) numbers \(u - xv\) with \(0 \le u, v \le m\). By the pigeonhole principle two are congruent modulo \(p\): \(u_1 - xv_1 \equiv u_2 - xv_2\). Put \(a = u_1 - u_2\) and \(b = v_1 - v_2\). Then \(a \equiv xb\), not both are 0, and \(|a|, |b| \le m < \sqrt p\). Squaring, \(a^2 \equiv x^2b^2 \equiv -b^2\), so \(p \mid a^2 + b^2\). But \(0 < a^2 + b^2 < 2p\), so \(a^2 + b^2 = p\).

Combining this with the identity \((a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2\), which appears in Diophantus and Brahmagupta, gives the complete answer: a positive integer \(n\) is a sum of two squares if and only if every prime \(q \equiv 3 \pmod 4\) appears to an even power in its factorization. So \(245 = 5 \cdot 7^2 = 14^2 + 7^2\) is a sum of two squares, while \(21 = 3 \cdot 7\) is not.

Gauss's lemma and the prime 2

For the symbol \(\big(\frac{2}{p}\big)\) and for the proof of reciprocity we need a counting criterion found by Gauss.

Theorem (Gauss's lemma). Let \(p\) be an odd prime, \(p \nmid a\). Reduce the numbers \(a, 2a, \ldots, \frac{p-1}{2}a\) modulo \(p\) to the range \(1, \ldots, p - 1\), and let \(\nu\) be the number of them that exceed \(p/2\). Then \(\big(\frac{a}{p}\big) = (-1)^\nu\).

Proof. Write \(h = (p - 1)/2\). Replace each reduced value \(r > p/2\) by \(p - r\), which lies in \(1, \ldots, h\) and is \(\equiv -r\). The resulting \(h\) numbers are distinct: two of the original values \(ia, ja\) cannot be equal, and \(ia \equiv -ja\) would give \(p \mid (i + j)a\), impossible since \(0 < i + j < p\). So they are \(1, 2, \ldots, h\) in some order. Multiplying, \(a \cdot 2a \cdots ha \equiv (-1)^\nu h!\), so \(a^hh! \equiv (-1)^\nu h!\). Cancel \(h!\) and use Euler's criterion.

Theorem (second supplementary law). \(\big(\frac{2}{p}\big) = 1\) if \(p \equiv \pm 1 \pmod 8\) and \(-1\) if \(p \equiv \pm 3 \pmod 8\). Proof: the numbers \(2, 4, \ldots, p - 1\) are already reduced, and \(\nu\) counts those exceeding \(p/2\), which is \(h - \lfloor p/4 \rfloor\). Checking the four cases \(p = 8k + 1, 8k + 3, 8k + 5, 8k + 7\) gives \(\nu = 2k, 2k + 1, 2k + 1, 2k + 2\). For \(p = 7\): \(2, 4, 6\) gives \(\nu = 2\), and indeed \(3^2 = 9 \equiv 2 \pmod 7\).

Residues by computer

The program lists the residues modulo small primes, checks Euler's criterion and Gauss's lemma against direct computation, verifies both supplementary laws for all primes below 1000, computes square roots modulo primes \(\equiv 3 \pmod 4\) with the formula \(a^{(p+1)/4}\), and writes primes \(\equiv 1 \pmod 4\) as sums of two squares.

import math

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

def residues(p):
    return sorted({x * x % p for x in range(1, p)})

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

def gauss_lemma(a, p):
    nu = sum(1 for k in range(1, (p - 1) // 2 + 1) if a * k % p > p / 2)
    return (-1) ** nu

for p in [11, 13, 17]:
    print(f"residues mod {p}:", residues(p))
print("Euler's criterion matches the list:", all((legendre(a, p) == 1) == (a in set(residues(p))) for p in primes[:40] for a in range(1, p)))
print("Gauss's lemma matches:", all(gauss_lemma(a, p) == legendre(a, p) for p in primes[:40] for a in range(1, p)))
print("(3/101) =", legendre(3, 101), "  (-1/13) =", legendre(12, 13), "  (2/7) =", legendre(2, 7))
print("(-1/p) = (-1)^((p-1)/2) for p < 1000:", all(legendre(p - 1, p) == (-1) ** ((p - 1) // 2) for p in primes))
print("(2/p) = 1 iff p = +-1 mod 8:", all((legendre(2, p) == 1) == (p % 8 in (1, 7)) for p in primes))

def sqrt_3mod4(a, p):
    x = pow(a, (p + 1) // 4, p)
    return x if x * x % p == a % p else None

print("square roots mod 103 of 2, 3, 5:", [sqrt_3mod4(a, 103) for a in (2, 3, 5)])

def two_squares(p):
    for a in range(1, math.isqrt(p) + 1):
        b = math.isqrt(p - a * a)
        if a * a + b * b == p:
            return (a, b)

print("primes 1 mod 4 as sums of two squares:", {p: two_squares(p) for p in primes if p % 4 == 1 and p < 120})
print("primes 3 mod 4 that are sums of two squares:", [p for p in primes if p % 4 == 3 and two_squares(p)])

residues mod 11: [1, 3, 4, 5, 9]
residues mod 13: [1, 3, 4, 9, 10, 12]
residues mod 17: [1, 2, 4, 8, 9, 13, 15, 16]
Euler's criterion matches the list: True
Gauss's lemma matches: True
(3/101) = -1   (-1/13) = 1   (2/7) = 1
(-1/p) = (-1)^((p-1)/2) for p < 1000: True
(2/p) = 1 iff p = +-1 mod 8: True
square roots mod 103 of 2, 3, 5: [38, None, None]
primes 1 mod 4 as sums of two squares: {5: (1, 2), 13: (2, 3), 17: (1, 4), 29: (2, 5), 37: (1, 6), 41: (4, 5), 53: (2, 7), 61: (5, 6), 73: (3, 8), 89: (5, 8), 97: (4, 9), 101: (1, 10), 109: (3, 10), 113: (7, 8)}
primes 3 mod 4 that are sums of two squares: []

The formula \(a^{(p+1)/4}\) works because, for a residue \(a\) and \(p \equiv 3 \pmod 4\), \(\big(a^{(p+1)/4}\big)^2 = a \cdot a^{(p-1)/2} \equiv a\) by Euler's criterion. It finds \(38^2 = 1444 = 14 \cdot 103 + 2\), and returns None for 3 and 5, which are nonresidues modulo 103, as the next lesson will let us predict without any computation. For primes \(\equiv 1 \pmod 4\) square roots are harder to find, but the Tonelli–Shanks algorithm does it efficiently.