Legendre's three-square theorem

Statement

Let $n$ be a natural number. Then $n = x^2 + y^2 + z^2$ for some integers $x$, $y$ and $z$ if and only if $n \neq 4^a (8b + 7)$ for all natural numbers $a$ and $b$.

Remarks

The "only if" part is easy: a square is $0$, $1$ or $4$ modulo $8$, so no sum of three squares is $7$ modulo $8$. The first numbers that are not sums of three squares are $7$, $15$, $23$, $28$ and $31$. The theorem implies Lagrange's four-square theorem in a few lines.

History

Legendre gave the first proof in 1797 or 1798. Gauss proved a more general result in 1801.

Explanations

L1 human

Most numbers are sums of three squares, for example $6 = 4 + 1 + 1$. The exceptions are $7, 15, 23, \dots$, the numbers that leave remainder $7$ on division by $8$, and these numbers times powers of $4$.