Integer as Sum of Three Squares

Theorem

Let $r$ be a positive integer.

Then $r$ can be expressed as the sum of three squares iff it is not of the form:

$4^n \left({8 m + 7}\right)$

for some $m, n \in \Z: m \ge 0, n \ge 0$.

Proof

Sufficient Condition

Suppose $r$ is not of the form $4^n \left({8 m + 7}\right)$.

Then we need to show that it can always be expressed as the sum of three squares.

Necessary Condition

From Square Modulo 8, the squares modulo $8$ are $0, 1$ and $4$.

So the sum of three squares can be congruent modulo 8 to any of the values $0, 1, 2, 3, 4, 5$ or $6$, but not $7$.

So no number of the form $8 m + 7$ can be the sum of three squares.

Now, suppose that $\exists n \ge 1, m \ge 0$ such that:

$4^n \left({8 m + 7}\right) = x^2 + y^2 + z^2$.

As the LHS is congruent modulo 4 to $0$, and as squares modulo 4 are either $0$ or $1$, it must be that $x, y$ and $z$ are all even.

Putting $x = 2 x_1, y = 2 y_1, z = 2 z_1$, we get:

$4^{n-1} \left({8 m + 7}\right) = x_1^2 + y_1^2 + z_1^2$

If $n-1 > 1$ then $x_1, y_1$ and $z_1$ are all still even, and the argument can be repeated:

$4^{n-2} \left({8 m + 7}\right) = x_2^2 + y_2^2 + z_2^2$

Thus we descend through all powers of $4$ till $8 m + 7$ itself is expressed as the sum of three squares.

But this is impossible, as we saw above.

So the assumption that $4^n \left({8 m + 7}\right)$ can be expressed as the sum of three squares is false.

$\blacksquare$