Lesson 05 · Gaussian integers and characters · 50–65 minutes
Sums of Two Squares
13 = 32 + 22, 29 = 52 + 22, 37 = 62 + 12, but 7, 11 and 19 are not sums of two squares. Fermat claimed that an odd prime is a sum of two squares exactly when p ≡ 1 (mod 4). You will prove it twice: once by a pigeonhole argument that turns the square root of −1 into a small solution, and once by the Euclidean algorithm in ℤ[i], which also computes it. Then you will prove the representation is unique.
Where this lesson is headed
p = a2 + b2 ⇔ p = 2 or p ≡ 1 (mod 4), and then p = (a + bi)(a − bi) in exactly one way
In words: a prime p ≡ 1 (mod 4) is the norm of a Gaussian integer, uniquely up to order and signs. Equivalently p splits in ℤ[i] into two conjugate Gaussian primes, and the circle x2 + y2 = p passes through exactly 8 lattice points.
p: an odd prime
u: a solution of u2 ≡ −1 (mod p)
representation: p = a2 + b2 with integers a, b
Gaussian prime: a non-unit π ∈ ℤ[i] whose only factorizations are π = unit × associate of π
r2(n): #{(x, y) ∈ ℤ2 : x2 + y2 = n}
01. Which primes are sums of two squares?
Start with p = 13. The search table subtracts x2 from p and checks whether what is left is a square. The circle x2 + y2 = p shows every lattice point on it. The grid on the right turns the square root u of −1 into a small solution without any search.
Guided experiments
Do these in order. "Set this up" chooses p.
All primes below 200
| p | p mod 4 | a2 + b2 | r2(p) |
|---|
Every p ≡ 1 (mod 4) has exactly one representation with 0 < b < a, and 8 lattice points; no p ≡ 3 (mod 4) has any.
02. Existence, an algorithm, and uniqueness
Each step has the general argument on the left and your p from Stage 01 on the right.
1
Why p ≡ 3 (mod 4) is impossible
Every square is 0 or 1 mod 4 (even numbers square to 0, odd to 1). So a2 + b2 is 0, 1 or 2 mod 4, never 3. An odd prime that is a sum of two squares must be ≡ 1 (mod 4). (And 2 = 12 + 12.)
2
Start from a square root of −1
For p ≡ 1 (mod 4) there is u with u2 ≡ −1, so p divides u2 + 1 = N(u + i). The goal is to trade the big solution (u, 1) of a2 + b2 ≡ 0 (mod p) for a small one.
3
Thue's pigeonhole argument
Let m = ⌊√p⌋, so m2 < p < (m + 1)2 (p is not a square). There are (m + 1)2 > p pairs (x, y) with 0 ≤ x, y ≤ m, but only p residues, so two different pairs give the same value of x − uy mod p. Subtracting them gives (a, b) ≠ (0, 0) with
a ≡ ub (mod p), |a|, |b| ≤ m < √p
4
The small solution is exact
From a ≡ ub: a2 + b2 ≡ (u2 + 1)b2 ≡ 0 (mod p). And 0 < a2 + b2 < p + p = 2p. The only multiple of p strictly between 0 and 2p is p itself:
a2 + b2 = p
5
An algorithm: gcd(p, u + i) in ℤ[i]
Run the Euclidean algorithm of Lesson 04 on p and u + i; call the last nonzero remainder δ. It divides both, and δ = αp + β(u + i) for some α, β ∈ ℤ[i]. Then:
δ is not a unit. The map x + yi ↦ x − yu (mod p) respects sums and products (−u also squares to −1) and sends both p and u + i to 0, so it sends δ to 0. A unit cannot go to 0, since its image times the image of its inverse is 1.
δ is not an associate of p. Otherwise p would divide u + i in ℤ[i], and (u + i)/p would have imaginary part 1/p, not an integer.
Since N(δ) divides N(p) = p2 and lies strictly between 1 and p2, N(δ) = p: δ = a + bi gives the representation.
6
Uniqueness
Suppose p = a2 + b2 = c2 + d2 with a, b, c, d > 0. Expanding,
(ac + bd)(ad + bc) = cd(a2 + b2) + ab(c2 + d2) = p(ab + cd)
so, because p is prime, p divides ac + bd or ad + bc. Say p | ac + bd. By the two-squares identity, p2 = (ac + bd)2 + (ad − bc)2, and 0 < ac + bd, so ac + bd = p and ad = bc. As gcd(a, b) = 1 (a common factor would divide p), a | c and then (a, b) = (c, d). The other case gives (a, b) = (d, c).
7
How p splits in ℤ[i], and the 8 lattice points
π = a + bi has prime norm p, so it is a Gaussian prime: if π = στ, then N(σ)N(τ) = p forces one factor to have norm 1, a unit. So
p = π π̄ = (a + bi)(a − bi)
and p itself is not a Gaussian prime. The lattice points on x2 + y2 = p are the 4 associates of π and the 4 of π̄: by uniqueness, r2(p) = 8. (π and π̄ are not associates, since a ≠ b for p odd.)
03. Fermat's two-squares theorem
Assemble the argument, then test it on every prime below 10,000.
Theorem (Fermat). An odd prime p is a sum of two squares if and only if p ≡ 1 (mod 4). In that case the representation p = a2 + b2 is unique up to order and signs, p = (a + bi)(a − bi) with both factors Gaussian primes, and r2(p) = 8.
Complete proof
Necessity. Squares are 0 or 1 mod 4, so an odd sum of two squares is 1 mod 4.
Existence. For p ≡ 1 (mod 4) take u with u2 ≡ −1 (Lesson 03). Among the (⌊√p⌋ + 1)2 > p values x − uy (0 ≤ x, y ≤ ⌊√p⌋) two coincide mod p; their difference (a, b) ≠ (0, 0) has a ≡ ub and |a|, |b| < √p. Then p | a2 + b2 and 0 < a2 + b2 < 2p, so a2 + b2 = p. (Alternatively, δ = gcd(p, u + i) in ℤ[i] has norm p.)
Uniqueness. If p = a2 + b2 = c2 + d2 with positive entries, (ac + bd)(ad + bc) = p(ab + cd), so p divides a factor. If p | ac + bd, then p2 = (ac + bd)2 + (ad − bc)2 forces ac + bd = p and ad = bc, and coprimality of a, b gives (c, d) = (a, b); the other case gives (c, d) = (b, a).
Splitting. N(a + bi) = p is prime, so a + bi is a Gaussian prime and p = (a + bi)(a − bi). The integer solutions of x2 + y2 = p are the 8 points (±a, ±b), (±b, ±a). ∎
Computer check
For every odd prime below 10,000: counts all integer solutions of x2 + y2 = p directly (8 if p ≡ 1 mod 4, else 0), and checks that both Thue's pigeonhole method and the Gaussian gcd return a valid representation.
Not run yet.