Which primes are sums of two squares
Tonight's idea
Every integer is 0, 1, 2 or 3 mod 4, and squaring those gives 0, 1, 0, 1. So every square is 0 or 1 mod 4. (\(a \equiv b \pmod 4\): same remainder on division by 4.) Two squares add to 0, 1 or 2 mod 4, never 3. So nothing that is 3 mod 4, prime or not, is a sum of two squares. That is the easy half, fully proved.
The hard half is the converse: every prime \(p \equiv 1 \pmod 4\) is a sum of two squares. Fermat stated it; Euler proved it. The reason lives in the Gaussian integers \(a + bi\) (\(a, b\) integers), whose norm \(N(a + bi) = a^2 + b^2\) multiplies: \(N(\alpha\beta) = N(\alpha)N(\beta)\). So \(p = a^2 + b^2\) says exactly that \(p = (a + bi)(a - bi)\) splits.
Two facts make it split. When \(p \equiv 1 \pmod 4\) there is an \(x\) with \(x^2 \equiv -1 \pmod p\) (the stretch), so \(p\) divides \((x + i)(x - i)\) without dividing either factor. And Gaussian integers have division with remainder, so Euclid's lemma (a prime dividing a product divides a factor) holds for them too. So \(p\) is not a Gaussian prime: \(p = \alpha\beta\), and taking norms, \(N(\alpha) = p\).
Watch one: 13 from \(5^2 \equiv -1\)
\(5^2 = 25 = 2 \cdot 13 - 1\), so 13 divides \(5^2 + 1 = (5 + i)(5 - i)\). Divide 13 by \(5 + i\) as Gaussian integers:
\[\frac{13}{5 + i} = \frac{13(5 - i)}{26} = \frac{5 - i}{2} = 2.5 - 0.5i.\]
Round to a nearest Gaussian integer, say \(2 - i\); the remainder is \(13 - (5 + i)(2 - i) = 13 - (11 - 3i) = 2 + 3i\), of norm \(4 + 9 = 13\). Euclid's algorithm continues with \(5 + i\) and \(2 + 3i\), and stops at once:
\[\frac{5 + i}{2 + 3i} = \frac{(5 + i)(2 - 3i)}{13} = \frac{13 - 13i}{13} = 1 - i.\]
So \(2 + 3i\) is a common divisor of 13 and \(5 + i\), and \(13 = (2 + 3i)(2 - 3i) = 2^2 + 3^2\). No searching was needed.
Your turn
- Write 17, 37, 41 and 53 as sums of two squares. Check that each is \(1 \pmod 4\).
- (a) Explain, without searching, why 2023 is not a sum of two squares. (b) \(21 \equiv 1 \pmod 4\). Is 21 a sum of two squares? What does that say about the rule?
- Multiply out \((1 + 2i)(2 + 3i)\) and \((1 + 2i)(2 - 3i)\) and take norms. Hence write \(65 = 5 \times 13\) as a sum of two squares in two ways. Then expand \((a + bi)(c + di)\) and take norms: what identity appears?
- \(12^2 = 144 \equiv -1 \pmod{29}\). Divide 29 by \(12 + i\), round to a nearest Gaussian integer, find the remainder and its norm, and read off 29 as a sum of two squares. Why did one step suffice?
Stretch: the missing fact
Wilson's theorem says \((p - 1)! \equiv -1 \pmod p\) for every prime \(p\); take it as given. Pair each \(k \le \tfrac{p-1}{2}\) with \(p - k \equiv -k\) to show that when \(p \equiv 1 \pmod 4\), \(x = \left(\tfrac{p-1}{2}\right)!\) satisfies \(x^2 \equiv -1 \pmod p\). Check \(p = 13\).
Answers
- \(17 = 16 + 1\), \(37 = 36 + 1\), \(41 = 25 + 16\), \(53 = 49 + 4\). Remainders mod 4: all 1.
- (a) \(2023 = 4 \cdot 505 + 3\), so \(2023 \equiv 3 \pmod 4\) and no sum of two squares can equal it. (b) \(21 - 1\), \(21 - 4\), \(21 - 9\), \(21 - 16\) are 20, 17, 12, 5, none a square, so no. The mod-4 test is a theorem about primes. For composites the full rule is: \(n\) is a sum of two squares exactly when every prime \(\equiv 3 \pmod 4\) in its factorisation appears to an even power. \(21 = 3 \cdot 7\) fails; \(9 = 3^2 = 9 + 0\) and \(45 = 3^2 \cdot 5 = 36 + 9\) pass.
- \((1 + 2i)(2 + 3i) = -4 + 7i\) and \((1 + 2i)(2 - 3i) = 8 + i\). Norms: \(16 + 49 = 65 = 64 + 1\). In general \((a + bi)(c + di) = (ac - bd) + (ad + bc)i\), and taking norms gives \((a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2\): the right side is visibly a sum of two squares.
- \(\dfrac{29}{12 + i} = \dfrac{29(12 - i)}{145} = \dfrac{12 - i}{5} = 2.4 - 0.2i\), nearest Gaussian integer 2. Remainder \(29 - 2(12 + i) = 5 - 2i\), norm \(25 + 4 = 29\). So \(29 = 5^2 + 2^2\). The remainder already has norm 29, a prime, so it cannot be split further; the algorithm has found the Gaussian prime factor of 29 in one step.
Stretch. Group the factors of \((p-1)!\) in pairs \(k\) and \(p - k\) for \(k = 1, \dots, \tfrac{p-1}{2}\). Since \(p - k \equiv -k\), each pair contributes \(k \cdot (-k) = -k^2\), and \((p - 1)! \equiv (-1)^{(p-1)/2}\left(\tfrac{p-1}{2}\right)!^2\). When \(p \equiv 1 \pmod 4\), \(\tfrac{p-1}{2}\) is even, the sign is \(+\), and Wilson gives \(x^2 \equiv -1\). For \(p = 13\): \(6! = 720 = 55 \cdot 13 + 5\), so \(x \equiv 5\), and \(25 \equiv -1 \pmod{13}\), the very number the example began with.