Proofs that every natural number is a sum of four squares. I am planning to write a little note detailing several proofs of Lagrange's theorem that every natural number can be written as the sum of four perfect squares. I know of three different proofs so far:


*

*a completely elementary proof by descent. 

*a proof via Minkowski's theorem and lattices. 

*Jacobi's proof via modular forms. 


Can anybody think of any more nice, relatively elementary proofs of this result? Thanks in advance. 
 A: Here's one to add to your list by Andrews, Ekhad and Zeilberger.
A short proof of Jacobi’s formula for the number of representations of an integer as the
sum of four squares.
A: One can easily deduce the four squares theorem from the Gauss-Legendre three squares theorem.  The latter is actually less elementary, but there is a very nice proof using Hasse-Minkowski and the Aubry-Davenport-Cassels Lemma.
This is the approach taken in Serre's A Course in Arithmetic, Appendix to Chapter IV.  Quadratic forms which satisfy the conclusion of the Aubry-Davenport-Cassels Lemma (ADC forms) have been a topic of recent research of mine, so it is fair to say that this is currently my favorite proof.
Note that the quaternionic proof of Chris Card's answer (which is also a very important one) can be understood and, arguably, clarified in these terms.  The sum of four squares form does not itself satisfy the hypotheses of the ADC Lemma.  This is related to the fact that it is the norm form of the nonmaximal order $\mathbb{Z}[i,j,k]$ in the Hamilton quaternion algebra $H = \left(\frac{-1,-1}{\mathbb{Q}} \right)$.  A maximal order containing it is $\mathbb{Z}[i,j,k,\frac{1+i+j+k}{2}]$.  The norm form on this order is the quadratic form
$q = x^2 + y^2 + z^2 + w^2 + xw + yw + zw$.
This form does satisfy the hypothesis of the ADC Lemma (it is Euclidean in my terminology), so it follows immediately from Hasse-Minkowski that it is universal, i.e., represents all positive integers.  Moreover the form $q$ is sufficiently closely
related to the sum of four squares form that a little elementary fiddling around shows that the sum of four squares form is universal as well.  For other examples of this phenomenon, see this recent preprint of R.W. Fitzgerald as well as some papers of J.I. Deutsch that are cited there.
(If you dare, you can take a look at my magnum opus on Euclidean forms and ADC forms.  Caveat emptor: more than being unpolished, there are some unsanded sharp corners here.)
A: There's a proof in Herstein using quaternions.
[See also Hardy and Wright's An Introduction to the Theory of Numbers.  -- PLC.]
A: Perhaps the most beautiful solution is by way of Aubry's lemma - which employs a geometric variant of the Euclidean algorithm to turn a rational represention into an integral representation. This is the same technique that leads to the reflective generation of primitive Pythagorean triples and the associated ternary tree structure. Aubry's results are, in fact, very special cases of general results of Wall, Vinberg, Scharlau et al. on reflective lattices, i.e. arithmetic groups of isometries generated by reflections in hyperplanes. Generally reflections generate the orthogonal group of Lorentzian quadratic forms in dim < 10. See my MO post here for further remarks and references.
In my opinion, the results in this area are some of the most beautiful results in elementary number theory. Strangely enough, for all this beauty they appear to be little known. For example, over a decade ago when I mentioned to John Conway the connection between Aubry's work and Cassels and Pfister he was not aware of this (R.K. Guy told me that the presentation of the PPT ternary tree in their Book of Numbers (1996) is based on a lecture he heard by an undergraduate, Richard Vogeler, at an MAA section at Brigham Young Univ. on 89-04-07.)  Also Pfister apparently was not aware of Aubry's work when he generalized Cassels result to arbitrary quadratic forms, founding the modern algebraic theory of quadratic forms ("Pfister forms"). Someday I hope to write something on the bizarre history of this beautiful circle of ideas so I would be grateful to hear from anyone who may know further details.
