Sum of Two Squares Theorem — Mathematics Knowledge System

Overview

Fermat's theorem on sums of two squares (stated by Fermat in 1640, first published proof by Euler) answers a deceptively simple question: which primes can be written as a² + b² for integers a, b? The answer is exactly the primes p ≡ 1 (mod 4), plus the special case p = 2 = 1² + 1²; primes p ≡ 3 (mod 4) can NEVER be written as a sum of two squares. This single fact about primes controls which integers overall are expressible: a positive integer n is a sum of two squares if and only if every prime factor of n congruent to 3 mod 4 appears to an even power in its factorization. The theorem is a cornerstone of the arithmetic of Gaussian integers ℤ[i], where a prime p ≡ 1 (mod 4) factors as p = (a+bi)(a−bi), while primes p ≡ 3 (mod 4) stay prime (inert) in that ring.

Intuition

Working modulo 4, every square is either 0 or 1 (0²≡0, 1²≡1, 2²≡0, 3²≡1). So a sum of two squares mod 4 can only be 0, 1, or 2 — never 3. That immediately rules out any prime p ≡ 3 (mod 4) from being a sum of two squares. The deeper (and harder) half of the theorem is that this obstruction is the ONLY one: every prime p ≡ 1 (mod 4) genuinely IS expressible, which follows from the fact that −1 is a quadratic residue mod p exactly when p ≡ 1 (mod 4) — that residue condition is what lets you factor p in the Gaussian integers.

Formal Definition

Definition

For an odd prime p:

p = a^2 + b^2 \text{ for some integers } a, b \iff p \equiv 1 \pmod 4

Fermat's theorem on sums of two squares (odd primes)

2 = 1^2 + 1^2

Special case p = 2

n \text{ is a sum of two squares} \iff \text{every prime } p \equiv 3 \!\!\pmod 4 \text{ dividing } n \text{ appears to an even power}

General characterization for any positive integer n

Worked Examples

13 ≡ 1 (mod 4), so it should be expressible; check 2² + 3².
$2^2 + 3^2 = 4 + 9 = 13$
29 ≡ 1 (mod 4); check 2² + 5².
$2^2 + 5^2 = 4 + 25 = 29$
3 ≡ 3 (mod 4) and 7 ≡ 3 (mod 4), so by the theorem neither can be written as a sum of two squares.
$3 \bmod 4 = 3, \quad 7 \bmod 4 = 3$

Answer: 13 = 2²+3², 29 = 2²+5²; 3 and 7 are not expressible since both are ≡ 3 (mod 4).

Practice Problems

Difficulty 2/10

Compute 29 mod 4.

Difficulty 5/10

Explain why 21 cannot be written as a sum of two squares.

Difficulty 6/10

65 = 5 × 13, with both 5 and 13 primes ≡ 1 (mod 4). Show 65 has TWO distinct representations as a sum of two squares.

Quiz

Summary

An odd prime p is a sum of two squares (p = a²+b²) if and only if p ≡ 1 (mod 4); p ≡ 3 (mod 4) primes never are.
The mod-4 obstruction is simple: squares are only 0 or 1 mod 4, so their sum is never ≡ 3 (mod 4).
General n is expressible as a sum of two squares iff every prime factor ≡ 3 (mod 4) occurs to an even power — this connects to factorization in the Gaussian integers ℤ[i].

References

WebsiteWikipedia — Fermat's theorem on sums of two squares