Sums of Two Squares
Which whole numbers can be written as a^2 + b^2? Some can —
5 = 1^2 + 2^2, 13 = 2^2 + 3^2 — and some
stubbornly cannot, like 3 or 7. The pattern
behind which is which is one of the loveliest results in number theory, and it hinges entirely on
primes modulo 4.
The prime case
An odd prime p is a sum of two squares if and only if
p \equiv 1 \pmod 4.
So 5, 13, 17, 29 all split into two squares, while
3, 7, 11, 19 never do. The "only if" is easy — a square is
0 or 1 \bmod 4, so a sum of two squares is
never 3 \bmod 4. The "if" direction is the deep part, and it leans on the
fact that -1 is a
quadratic residue
precisely when p \equiv 1 \pmod 4.
The full classification
Multiplicativity extends this to all integers. The key is Brahmagupta's identity, which shows sums
of two squares are closed under multiplication:
(a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2.
A positive integer is a sum of two squares if and only if every prime
\equiv 3 \pmod 4 in its factorisation appears to an even
power.
Thus 45 = 3^2 \cdot 5 = 6^2 + 3^2 works (the 3
is squared), but 21 = 3 \cdot 7 fails.
Where this is heading
Brahmagupta's identity looks suspiciously like the rule for multiplying magnitudes of complex
numbers, |z|^2 |w|^2 = |zw|^2 — and that is no accident. Treating
a^2 + b^2 = (a+bi)(a-bi) as a factorisation among
Gaussian integers
explains the whole theorem in one stroke: a prime is a sum of two squares exactly when it
splits in that larger number system.