From: David Madore <madore@clipper.ens.fr>
Newsgroups: sci.math
Subject: Re: proof: n = sum of 4 squares
Date: Wed, 30 Apr 1997 12:07:29 +0200
Organization: Ecole Normale Superieure, Paris, France
Lines: 60
To: slither@worldnet.att.net

Jan Lewis wrote:
> 
> i think fermat proved that any number can be
> written as the sum of four squares.  if i'm
> wrong, please correct me. if i'm right and you
> know where i can find an online proof, please
> let me know. i've searched for an hour or more
> and can't find it.

1.First note that it is sufficient to prove the theorem for n=prime.
Indeed, the product of two integers which are sums of 4 squares
is also a sum of four squares (to prove that, use the equality
giving the norm of the product of two quaternions). So we let p
be a prime and we wish to show that p is sum of four squares.
Obviously we can take p odd (that is, p>2).

2.Now note that the (p+1)/2 numbers 0^2, 1^2..., ((p-1)/2)^2 are
pairwise non-congruent mod p (this is easy because x^2=x'^2 mod
p iff x=x' or x=-x' mod p). The same applies to the (p+1)/2 numbers
-1-0^2, -1-1^2..., -1-((p-1)/2)^2. Since (p+1)/2 + (p+1)/2 > p,
one number of the first list must be congruent to one number of the
second list, that is, there must be x and y such that x^2+y^2+1=0
mod p. We now know that there exists -((p-1)/2)<=x,y,z,t<=((p-1)/2)
and 0<l<p such that x^2+y^2+z^2+t^2=lp. We let l be the smallest
such l (you see what I mean). Ad absurdum, suppose l>1.

3.We now prove that l must be odd. Indeed, if l is even, then we
can assume without loss of generality that x and y on the one hand,
z and t on the other, are of the same parity. But then
((x+y)/2)^2+((x-y)/2)^2+((z+t)/2)^2+((z-t)/2)^2=(l/2)p
which contradicts the minimality of l.

4.Let x',y',z',t' be the least residues of x,y,z,t mod l in absolute
value (that is, -((l-1)/2)<=x',y',z',t'<=((l-1)/2)). Now
x'^2+y'^2+z'^2+t'^2 is congruent to 0 mod l since x^2+y^2+z^2+t^2 is.
Let x'^2+y'^2+z'^2+t'^2=ml with 0<m<l. So the numbers ml and lp
are both sums of four squares; multiplying them by the aforementioned
equality (norm of the product of two quaternions) one finds that
mpl^2 is the sum of four squares, say mpl^2=x''^2+y''^2+z''^2+t''^2,
with moreover x'',y'',z'' and t'' all multiples of l. Cancelling
the l's, one gets mp=X^2+Y^2+Z^2+T^2, with
-((p-2)/2)<=X,Y,Z,Y<=((p-1)/2).
This is a contradiction since 0<m<l<p. [The fact that l was odd was
used in writing ((l-1)/2)...]

Note that the reduction process, once one has x^2+y^2+z^2+t^2=lp,
is completely effective. The same proof carries over, mutatis mutandis,
to the "sum of 2 squares" theorem (a positive integer is sum of
two squares iff each prime factor of the form 4k+3 has an even
exponent in its DPF) - just replace step 2 by the classical
argument showing that -1 is a square mod p iff p=1 mod 4, and
replace "quaternion" by "complex" thoughout.

This proof is taken from Alan Baker's remarkable book "A concise
introduction to the theory of numbers". It took me _quite a while_
remembering it, by the way.

     David A. Madore
    (david.madore@ens.fr,
     http://www.eleves.ens.fr:8080/home/madore/index.html.en)