$5 = 1^{2} + 2^{2}$ and $13 = 2^{2} + 3^{2}$, but no matter how you try, $7$ and $21$ are not sums of two squares. Fermat found the pattern, and the supplementary law for $-1$ is the key to it.
Theorem (Fermat; proved by Euler). An odd prime $p$ is a sum of two squares exactly when $p \equiv 1 \pmod{4}$. More generally, a positive integer $n$ is a sum of two squares of integers exactly when every prime $q \equiv 3 \pmod{4}$ appears in the prime factorization of $n$ to an even power.
Why it works
Products of sums are sums. $(a^{2} + b^{2})(c^{2} + d^{2}) = (ac - bd)^{2} + (ad + bc)^{2}$, an identity you can check by expanding.
Primes $\equiv 1 \bmod 4$ succeed. Here $-1$ is a square mod $p$: some $x$ has $p \mid x^{2} + 1$, a sum of two squares divisible by $p$. A short argument (Thue's lemma, or Fermat's "descent") shrinks this to $p$ itself.
Why even powers. If $q \equiv 3 \pmod{4}$ divides $a^{2} + b^{2}$, then $q$ divides both $a$ and $b$ (otherwise $-1 \equiv (a b^{-1})^{2}$ would be a square mod $q$). So $q^{2}$ divides the sum, and dividing it out leaves a smaller sum of two squares.
Worked example: Primes
- $13 \equiv 1$ and $29 \equiv 1 \pmod{4}$. Search: $13 - 2^{2} = 9 = 3^{2}$, and $29 - 2^{2} = 25 = 5^{2}$.
- $23 \equiv 3 \pmod{4}$, and a sum of two squares is never $3 \bmod 4$.
Answer: $13 = 3^{2} + 2^{2}$, $29 = 5^{2} + 2^{2}$; $23$ is impossible.
Worked example: A prime 3 mod 4, squared
- $45 = 3^{2} \cdot 5$: the prime $3 \equiv 3 \pmod{4}$ appears to an even power, so yes.
- Take $5 = 2^{2} + 1^{2}$ and multiply by $9 = 3^{2}$: $45 = 6^{2} + 3^{2}$.
Answer: Yes: $45 = 36 + 9$.
Worked example: Multiplying representations
- $5 = 2^{2} + 1^{2}$ and $13 = 3^{2} + 2^{2}$.
- $(ac - bd)^{2} + (ad + bc)^{2}$ with $(a, b, c, d) = (2, 1, 3, 2)$: $(6 - 2)^{2} + (4 + 3)^{2} = 16 + 49$.
- Swapping the roles of $c$ and $d$ gives $(4 - 3)^{2} + (6 + 2)^{2} = 1 + 64$.
Answer: $65 = 4^{2} + 7^{2} = 1^{2} + 8^{2}$.
Common mistake
Key idea