The Theorem of Lagrange

Regrettably, the famous theorem of Joseph-Louis Lagrange (1736-1813), that every positive integer may be represented as sum of at most four squares (see Wikipedia), did not yet find its way into Proofs from the BOOK  [Aigner, Ziegler 2014]. Because it's one of my favourite theorems, I will present a proof on this page, and I will do it with the ambition to keep the proof comprehensible for high-school students, using only basic facts about divisibility and some computations with congruence classes. Furthermore, I try to leave no gaps, hence I will prove every intermediate step, which would usually be replaced by the verbiage it's easily seen.

Theorem of Lagrange
Every positive integer can be represented as sum of at most four squares. In other words: Let $n \in \mathbb{N}$ be an arbitrary positive integer, then there exist $x, y, z, w \in \mathbb{N}_0$ with \[n = x^2 + y^2 +z^2 + w^2\].

Take $17 = 4^2 + 1^2$ as an example, or $7 = 2^2 +1^2 + 1^2 + 1^2.$ The latter demonstrates that you really need four squares.

We start with the aforesaid considerations about divisibility, namely with Euclid's lemma: If a prime $p$ divides a product, in symbols $p \mid ab,$ then $p$ divides at least one of the factors, $p \mid a$ or $p \mid b.$ If you think that this is a trivial consequence of the uniqueness of integer factorization, remember that Euclid's Lemma is used to prove just this uniqueness.

The standard way to prove Euclid's lemma uses Bézout's identity, so we start with the proof of the latter:

Bézout's identity
If $a$ and $b$ are elements of  $\mathbb{Z}$ and $d$ the greatest common divisor (gcd)  of $a$ and $b.$ Then there exist $s$ and $t$ elements of  $\mathbb{Z}$ with \[d = sa + tb\].

Proof:
Among all numbers of the form $sa + tb$ with $s, t \in \mathbb{Z}$ there are clearly some, which are greater 0. Let $x$ be the smallest of these. Because $d$ divedes both $a$ and $b,$ it must also divide $x.$ If $x = 1,$ then $d = 1$ and we are done. If $x \gt 1$ Euclidean division yields $a = qx +r$ with $0 \leq r \lt x.$ Replacing $x$ by $sa + tb,$ one has: $$ \begin{align*} a &= q(sa + tb) + r \\ r &= (1-qs)a + (-qt)b \\ \end{align*} $$ So $r$ is also of the form $s'a + t'b$ and at the same time it is smaller than $x.$ Because $x$ has been chosen to be minimal, it follows $r = 0.$ Hence $x$ divides $a,$ in other words $x \mid a.$ By the same argument it can be shown that $x \mid b.$ Hence we have $x \mid d.$ Because we already know $d \mid x,$ it follows $x = d.$  ∎

Euclid's Lemma
Let $p$ be prime and $p \mid ab$ with $a, b \in \mathbb{Z},$ then $p \mid a$ or $p\mid b.$

Proof:
It sufices to show the following: If $p \mid ab$ and $p \nmid a,$ then it follows $p \mid b.$ So let's assume $p \nmid a.$ It follows that $p$ and $a$ are relatively prime, in other words that the gcd of $a$ and $p$ is 1. By Bézout's identity we have \[1 = sa + tp\] with $s, t \in \mathbb{Z}.$ Multiplying with $b$ yields \[b = s(ab) + tbp\] Because each of the summands is divisible by $p,$ this holds for the sum $b$ as well, thus establishing $p \mid b.$  ∎

The following identity, discovered by Euler, allows to restrict our considerations to prime numbers. It will be shown that the product of two sums of four squares is again a sum of four squares. Because every positive integer greater than 1 is a product of primes, the general theorem of Lagrange follows from its restriction to primes by multiplication and applying the aforesaid identity together with the trivial representation $1 = 1^2 + 0^2 +0^2 +0^2$ of the 1, which is neither prime nor composite. The name Euler's identity  for the following lemma is ambiguous, because Euler discovered a lot of identities. But the name is unique within this article.

Euler's identity
If two positive integers can be represented as a sum of four squares, the same holds for their product.

Proof:
Recalculate the following formula: $$ \begin{multline*} (x^2 + y^2 + z^2 + w^2)(x_1^2 + y_1^2 + z_1^2 + w_1^2) \\ = (xx_1 + yy_1 + zz_1 + ww_1)^2 + (xy_1 -yx_1 + wz_1 - zw_1)^2 \\ +(xz_1 - zx_1 + yw_1 - wy_1)^2 + (xw_1 - wx_1 + zy_1 - yz_1)^2  ∎ \end{multline*} $$

Because with $2 = 1^2 + 1^2 + 0^2 + 0^2$ we have a trivial representation of the number $2$ as sum of four squares, it is sufficient to prove Lagrange's theorem for odd primes $p,$ in other words for primes $p \gt 2.$

This proof applies the method of infinite descent, which has been introduced by Fermat, and which is used with many number theoretical proofs. In a first step we will prove that every product $mp$ with an odd prime $p$ and some factor $m$ with $1 \leq m \lt p$ is a sum of four squares. The descent  consists in the fact, that from the equation \[x^2 +y^2 + z^2 + w^2 = mp\] with $m \gt 1$ there can be deduced another equation \[x'^2 +y'^2 + z'^2 + w'^2 = m'p\] with $m' \lt m.$ Because one can repeat this construction again and again until one reaches $m' = 1,$ Lagrange's theorem for odd primes follows.

To find the entrance to our descent we need the following

Lemma
For every odd prime $p$ and all $x$ with $0 \leq x \leq (p-1)/2$ the squares $x^2$ belong to different congruence classes mod $p.$

Proof:
Assume there would exist $x \neq y$ with $0 \leq x \lt y \leq (p-1)/2,$ with their squares leaving the same remainder when divided by $p.$ Then $p$ would divide the difference of the squares: $$ \begin{align*} p {}& \mid y^2 - x^2 \\ p {}& \mid (y+x)(y-x) \end{align*} $$ By Euclid's lemma it follows that $p \mid (y+x)$ or $p \mid (y-x).$ Assume $p \mid (y-x),$ then $x$ and $y$ are in the same congruence class mod $p.$ Because both numbers are between $0$ and $(p-1)/2,$ we could conclude $y = x,$ contradicting $x \neq y$. On the other hand we have $0 \lt y+x \leq p -1 \lt p,$ in other words $p \nmid (y + x).$ Hence the assumption, that $x^2$ and $y^2$ belong to the same congruence class mod $p,$ leads to a contradiction. ∎

The following lemma by Euler gives the entrance for the descent:

Lemma (Euler)
For every odd prime $p$ there exist $x, y \in \mathbb{Z},$ with $0 \leq x,y \leq (p-1)/2$ so that \[ x^2 + y^2 + 1^2 \equiv 0 \pmod{p} \] holds.

Proof:
We have seen that the $(p+1)/2$ squares $x^2$ with $0 \leq x \leq (p-1)/2$ all belong to different congruence classes mod $p.$ It follows immediately that also the $(p+1)/2$ expressions $-1-y^2$ with $0 \leq y \leq (p-1)/2$ all belong to different congruence classes mod $p.$ If none of the congruence classes, taken by the $x^2,$ would be identical with some congruence class, taken by the $-1-y^2,$ there would be $p+1$ different congruence classes mod $p$ in summary. But there exist only $p$ different congruence classes mod $p.$ Hence there is at least one $x^2$ and one $-1-y^2,$ belonging to the same congruence class. By definition of congruence their difference $x^2 + y^2 + 1$ is divisible by $p$ and that is exactly the statement, we had to prove. ∎

Now we start the descent:

Proof of Lagrange's Theorem

By choice of the $x$ and $y$ as in the above lemma, the following inequality holds:

The result of the lemma can be rewritten as follows: \[x^2 + y^2 + 1^2 + 0^2 = mp\] where $m$ satisfies $1 \leq m \lt p,$ because of the above inequality. Hence we have shown that for every odd prime there exists a representation of the form \[x^2 + y^2 + z^2 + w^2 = mp\] with $1 \leq m \lt p.$ That is the starting point for the descent.

If $m = 1,$ we are done. So let $m \gt 1.$ We carry out the descent for even and odd $m$ separately.

Let $m \gt 1$ be even. Then $mp$ is also even. If a sum is even, the number of odd summands must be even (or zero). Hence the summands may be grouped into pairs, whose sum and difference is even. Without loss of generality we can assume that $x^2, y^2$ and $z^2, w^2$ are such pairs. That's not only true for the squares but also for the numbers $x, y, z$ and $w$ themselves. It follows that $(x \pm y)/2$ and $(z \pm w)/2$ are whole numbers, and we calculate $$ \begin{align*} {}& \left(\dfrac{ x+y}{ 2}\right)^2 + \left(\dfrac{ x-y}{ 2}\right)^2 + \left(\dfrac{ z+w}{ 2}\right)^2 + \left(\dfrac{ z-w}{ 2}\right)^2 \\[6pt] &= \dfrac{ 2x^2 + 2y^2}{ 4} + \dfrac{ 2z^2 + 2w^2}{ 4} \\[6pt] &= \dfrac{1}{2}(x^2 + y^2 + z^2 + w^2) \\[6pt] &= \dfrac{m}{2}p \end{align*} $$

With $x' = (x+y)/2$, $y' = (x-y)/2,$ $z' = (z+w)/2, w' = (z-w)/2$ and $m' = m/2$ the descent to a representation with smaller $m' \lt m$ has been done.

Now let $m \gt 1$ be odd. Take $x_1 \equiv x \pmod{m},$ $y_1 \equiv y \pmod{m},$ $z_1 \equiv z \pmod{m},$ and $w_1 \equiv w \pmod{m}$ with $|x_1|, |y_1|, |z_1|, |w_1| \lt m/2.$ That is always possible, because with $b = m - a$ it holds $a \equiv -b \pmod{m}$ and one of the values $|a|, |b|$ is less $m/2,$ because $m$ is odd.

Now we have \[x_1^2 + y_1^2 + z_1^2 + w_1^2 \equiv x^2 + y^2 + z^2 + w^2 \equiv 0 \pmod{m}\] Hence there is a $m' \in \mathbb{Z}$ with \[x_1^2 + y_1^2 + z_1^2 + w_1^2 = m'm\] On the other hand we have \[x_1^2 + y_1^2 + z_1^2 + w_1^2 \lt 4(m/2)^2 = m^2\] from which follows $1 \leq m' \lt m.$ Now we apply Euler's identity to the sums of squares $mp$ and $m'm$: $$ \begin{align*} m^2m'p &= (x^2 + y^2 + z^2 + w^2)(x_1^2 + y_1^2 + z_1^2 + w_1^2) \\[10pt] &= a^2 + b^2 + c^2 + d^2 \end{align*} $$ with suitable $a, b, c, d$ as stated by Euler's identity.

Inserting the values from this identity we get the following congruences mod $m$: $$ \begin{align*} a {}& \equiv xx_1 + yy_1 + zz_1 + ww_1 \equiv x^2 + y^2 + z^2 + w^2 \equiv 0 \pmod{m}\\ b {}& \equiv xy_1 -yx_1 + wz_1 - zw_1 \equiv xy -yx + wz -zw \equiv 0 \pmod{m} \\ c {}& \equiv xz_1 - zx_1 + yw_1 - wy_1 \equiv xz -zx + yw - wy \equiv 0 \pmod{m}\\ d {}& \equiv xw_1 - wx_1 + zy_1 - yz_1 \equiv xw -wx + zy -yz \equiv 0 \pmod{m} \end{align*} $$ Hence the $a, b, c, d$ are divisible by $m.$ So we have whole numbers $x' = a/m, y' = b/m, z' = c/m$ and $w' = d/m$ and get \[x'^2 + y'^2 +z'^2 +w'^2 = \tfrac{1}{m^2}(a^2 +b^2 + c^2 + d^2) = m'p\] with $1 \leq m' \lt m,$ whereby the descent has been done in case of odd $m$ and Lagrange's theorem has been completely proved. ∎

The proof is quite constructive, by the way. You may compute the sum of squares of a prime number, if you know the sum of a multiple of this prime. Of course, that's not the easiest way to find four squares summing up to a given number, but let's try it anyway with the example 95.

Let's assume, we know one representation of 95: \[ 95 = 9^2 + 3^2 + 2^2 + 1^2 = 5 \cdot 19\] We want to find the representation of the prime factor 19, so we compute the congruence classes of the summands mod 5 (which is our $m$): $$ \begin{align*} 9 {}& \equiv 4 \equiv -1 \pmod{5}\\ 3 {}& \equiv -2 \pmod{5} \\ 2 {}& \equiv 2 \pmod{5} \\ 1 {}& \equiv 1 \pmod{5} \end{align*} $$ Then we have $(-1)^2 + (-2)^2 + 2^2 + 1^2 = 10 = 2 \cdot 5,$ hence our $m'$ equals 2.

Now we compute $a, b, c, d$ applying Euler's identity: $$ \begin{align*} a &= xx_1 + yy_1 + zz_1 + ww_1 = -9 - 6 + 4 + 1 = -10 \\ b &= xy_1 -yx_1 + wz_1 - zw_1 = -18 -(-3) + 2 - 2 = -15 \\ c &= xz_1 - zx_1 + yw_1 - wy_1 = 18 -(-2) + 3 -(-2) = 25 \\ d &= xw_1 - wx_1 + zy_1 - yz_1 = 9 -(-1) + (-4) - 6 = 0 \\ \end{align*} $$ divide each of the $a, b, c, d$ by 5 and sum up: \[(a/5)^2 + (b/5)^2 + (c/5)^2 + (d/5)^2 = 2^2 + 3^2 + 5^2 + 0^2 = 38 = 2 \cdot 19\] So we got a representation of $m'p = 2 \cdot 19$ and can apply the method of descent for even $m,$ taking the two odd numbers as a pair: \[ \left(\frac{ 5+3}{ 2}\right)^2 + \left(\frac{ 5-3}{ 2}\right)^2 + \left(\frac{ 2+0}{ 2}\right)^2 + \left(\frac{ 2-0}{ 2}\right)^2 \\ = 4^2 + 1^2 + 1^2 + 1^2 = 19 \] whereby a decomposition of 19 into four squares has been found.