Lemma 1   For any integers $a,b,c,d,w,x,y,z$ , \begin{eqnarray*} (a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2) & = & (aw+bx+cy+dz)^2 \\ & + & (ax-bw-cz+dy)^2 \\ & + & (ay+bz-cw-dx)^2 \\ & + & (az-by+cx-dw)^2. \end{eqnarray*}

Lemma 2   If $2m$ is a sum of two squares, then so is $m$ .

Proof. Say $2m=x^2+y^2$ . Then $x$ and $y$ are both even or both odd. Therefore, in the identity $$m=\Big(\frac{x-y}{2}\Big)^2 + \Big(\frac{x+y}{2}\Big)^2,$$ both fractions on the right side are integers.

Lemma 3   If $p$ is an odd prime, then $a^2+b^2+1=kp$ for some integers $a,b,k$ with $0<k<p$ .

Proof. Let $p = 2n + 1$ . Consider the sets $$A:=\lbrace a^2 \mid a=0,1,...,n\rbrace\quad\mbox{ and }\quad B:=\lbrace -b^2-1 \mid b=0,1,...,n \rbrace.$$ We have the following facts:

1. No two elements in $A$ are congruent mod $p$ , for if $a^2\equiv c^2 \pmod p$ , then either $p\mid (a-c)$ or $p\mid (a+c)$ by unique factorization of primes. Since $a-c, a+c \le 2n< p$ , and $0\le a,c$ , we must have $a=c$ .
2. Similarly, no two elements in $B$ are congruent mod $p$ .
3. Furthermore, $A\cap B=\varnothing$ since elements of $A$ are all non-negative, while elements of $B$ are all negative.
4. Therefore, $C:=A\cup B$ has $2n+2$ , or $p+1$ elements.

Therefore, by the pigeonhole principle, two elements in $C$ must be congruent mod $p$ . In addition, by the first two facts, the two elements must come from different sets. As a result, we have the following equation: $$a^2+b^2+1=kp$$ for some $k$ . Clearly $k$ is positive. Also, $p^2 = (2n + 1)^2 > 2n^2 + 1 \ge a^2+b^2+1 = kp$ , so $p > k$ .

Proof. [Proof of Theorem] By Lemma 1 we need only show that an arbitrary prime $p$ is a sum of four squares. Since that is trivial for $p=2$ , suppose $p$ is odd. By Lemma 3, we know $$mp=a^2+b^2+c^2+d^2$$ for some $m,a,b,c,d$ with $0<m<p$ . If $m=1$ , then we are done. To complete the proof, we will show that if $m>1$ then $np$ is a sum of four squares for some $n$ with $1\le n<m$ .

If $m$ is even, then none, two, or all four of $a,b,c,d$ are even; in any of those cases, we may break up $a,b,c,d$ into two groups, each group containing elements of the same parity. Then Lemma 2 allows us to take $n = m/2$ .

Now assume $m$ is odd but $>1$ . Write \begin{eqnarray*} w & \equiv & a\pmod{m} \\ x & \equiv & b\pmod{m} \\ y & \equiv & c\pmod{m} \\ z & \equiv & d\pmod{m} \end{eqnarray*}where $w,x,y,z$ are all in the interval $(-m/2, m/2)$ . We have $$w^2+x^2+y^2+z^2 < 4\cdot \frac{m^2}{4} = m^2$$ $$w^2+x^2+y^2+z^2\equiv 0\pmod{m}.$$ So $w^2+x^2+y^2+z^2 = nm$ for some integer non-negative $n$ . Since $w^2+x^2+y^2+z^2 < m^2$ , $n<m$ . In addition, if $n=0$ , then $w=x=y=z=0$ , so that $a\equiv b\equiv c\equiv d \equiv 0 \pmod m$ , which implies $mp=a^2+b^2+c^2+d^2=m^2q$ , or that $m|p$ . But $p$ is prime, forcing $m=p$ , and contradicting $m<p$ . So $0<n<m$ . Look at the product $(a^2+b^2+c^2+d^2)(w^2+x^2+y^2+z^2)$ and examine Lemma 1. On the left is $nm^2p$ . One the right, we have a sum of four squares. Evidently three of them $$ax-bw-cz+dy=(ax-bw)+(dy-cz)$$ $$ay+bz-cw-dx=(ay-cw)+(bz-dx)$$ $$az-by+cx-dw=(az-dw)+(cx-by)$$ are multiples of $m$ . The same is true of the other sum on the right in Lemma 1: $$aw+bx+cy+dz \equiv w^2+x^2+y^2+z^2 \equiv 0\pmod{m}.$$ The equation in Lemma 1 can therefore be divided through by $m^2$ . The result is an expression for $np$ as a sum of four squares. Since $0<n<m$ , the proof is complete.