- Electronics
- Mathematics
- Programs
- Contact
- ESP

*by Michael Barr*

The theorem of the title has been known for centuries, perhaps longer, but I believe that Lagrange gave the first proof. When I was a student, I saw a very different (and, in my opinion, harder) proof from the one given here. I don't know who discovered this proof, but I saw it in Alan Baker's little book on number theory.

There is yet another proof that proves and uses unique factorization in
the non-commutative ring of quaternionic integers. Warning: the
quaternionic integers include **(1+i+j+k)/2** and in fact is the ring of
all polynomials in that number.

All proofs that I have seen use the identity

**(a ^{2}+b^{2}+c^{2}+d^{2}) (A^{2}+B^{2}+C^{2}+D^{2}) =
(aA+bB+cC+dD)^{2} + (aB-bA+cD-dC)^{2} + (aC-bD-cA+dB)^{2} + (aD-dA+bC-cB)^{2}**

which implies that the product of two numbers, each of which is a sum
of four squares, is also a sum of four squares. Although this identity
can be verified directly it is worth pointing out that by taking
**u=a-bi-cj-dk** and **U=A+Bi+Cj+Dk**, this is simply the square of the
identity that says that **|uU|=|u||U|**. That is why I often refer to it
as the quaternionic product identity. Anyway the conclusion is that it
suffices to prove for primes. Since every power of 2 is obviously
either a square or a sum of two squares, it suffices to prove that every
odd prime is a sum of four squares.

For later use, we also mention what might be called the complex product identity:

**(a ^{2}+b^{2}) (A^{2}+B^{2}) =
(aA+bB)^{2} + (aB-bA)^{2}**

We give here a proof that has the added advantage not only of being
constructive, but actually quite easily implemented as an algorithm. It
is not deterministic in the sense that there are trials, but it is
arranged so that each trial has at least a 50% chance of success. I
assume that the reader is familiar with modular arithmetic, although I
may add an introduction to that in the future. If **a** and **n** are
numbers, we say that the remainder **r** when **a** is divided by **n** is the
**residue** of **a** mod **n** (residue was the old word for what we now
call remainder, but the old usage has hung on in number theory).
Clearly, **a = r (mod p)** and **r** is the smallest non-negative number
with that property. Closely related is the **absolutely least
residue** defined as whichever of **r** and **r-n** is smaller in
absolute value. If **n** happens to be even and **r=n/2**, then **|r|=|r-n|** and you
can take either one, but in order for the phrase to have an unambiguous
meaning, we will take **r**.

So we wish to show that every odd prime is a sum of four squares. Actually, we give two separate arguments, the first that every prime congruent to 1 mod 4 is a sum of two squares and then that every prime congruent to 3 mod 4 is a sum of four squares.

We begin by showing that if **p** is a prime and **p = 1 (mod 4)**, then
there is a number **a** such that **a ^{2} = -1 (mod p)**. We say that

Next we note that for any **a** not divisible by **p**, if we
let **b=a ^{(p-1)/2}**, then

Can **a ^{(p-1)/2}=1** for all

If **a ^{(p-1)/2} = -1 (mod p)** and we let

So the first step of the process is to find a square root of **-1** mod
**p**. We have shown, in fact, that exactly half of the numbers
**1**, ..., **p-1** have the desired property. I do not know a deterministic
process for finding such a number, but they appear to be distributed
randomly so you can just try numbers at random until you find one and
each trial has a 50% chance of success. It is not hard to show that
the smallest solution must be a prime so that you can just try primes
2, 3, 5, 7, 11,... until you succeed. Even if you are trying 1000 digit
numbers it is unlikely that you will not find a solution before the
2000th prime, so for computational purposes, it is probably worth
keeping a list of the first 2000 or so primes.

Actually, you can do better than that if a higher power of 2 divides
**p-1**. If **2 ^{k}** divides

Now **a ^{2}+1^{2}** is a multiple of

Thus **a' ^{2}+b'^{2}=mk** with

**(a ^{2}+b^{2})(a'^{2}+b'^{2}) =
(aa'+bb')^{2}+(ab'-ba')^{2} (*)**

Since **aa'+bb' = a ^{2}+b^{2} = 0 (mod k)** and

**((aa'+bb')/k) ^{2} + ((ab'-ba')/k)^{2} = mp**

and **m < k**. It can be shown that the number of reduction steps is
bounded above by **log _{2} p**.

In this case, we begin by finding numbers **a** and **b** such that
**a ^{2}+b^{2}+1 = 0 (mod p)**. This is the same as

For our purposes, however, it is not enough to find **x**, you also need
**y**. Fortunately, there is for primes that are congruent to 3 mod 4,
there is a very simple way of constructing a square root of any number
that is a quadratic residue. There is, to my knowledge, no
correspondingly easy way of doing this for primes congruent to 1 mod 4.
Consider a number **a**, not divisible by **p**. Suppose that **a =
b ^{2} (mod p)**. Then

**a ^{(p+1)/2} = b^{p+1} = b^{2}b^{p-1} = b^{2} = a (mod p)**

from which we see that **(a ^{(p+1)/4})^{2} = a (mod p)** and hence

One we have found **x** and **y** so that **x ^{2}+y^{2}+1 = 0 (mod p)**, we can
replace them by absolutely least residues and suppose that

We will show how, if **k > 1**, to find a new solution with a smaller
value of **k**. The argument is similar to, but harder than, the
previous case of two squares. We consider the case of **k** odd and even
separately, for reasons we make clear. Suppose **k** is odd. In that
case, let **a', b',c'**, and **d'** be the
absolutely least residues of **a**, **b**, **c**, and **d** mod **k**.
Then each of **|a'|**, **|b'|**, **|c'|** and
**|d'|** is ** <= (k-1)/2** so that

**a' ^{2}+b'^{2}+c'^{2}+d'^{2} <= (k-1)^{2}**

while

**a' ^{2}+b'^{2}+c'^{2}+d'^{2} = a^{2}+b^{2}+c^{2}+d^{2} = 0 (mod k)**

Hence **a' ^{2}+b'^{2}+c'^{2}+d'^{2} = mk**
with

**mk ^{2}p = (a^{2}+b^{2}+c^{2}+d^{2}) (a'^{2}+b'^{2}+c'^{2}+d'^{2}) = (aa'+bb'+cc'+dd')^{2}
+ (ab'-ba'+dc'-cd')^{2} + (ac'-ca'+bd'-db')^{2} + (ad'-a'd+cb'-bc')^{2}**
and, in a way similar to the first case, each term is divisible by

**mp = ((aa'+bb'+cc'+dd')/k) ^{2} + ((ab'-ba'+dc'-cd')/k))^{2}
+ ((ac'-ca'+bd'-db')/k)^{2} + ((ad'-a'd+cb'-bc')/k)^{2}**

which completes the construction.

When **k** is even, this argument fails specifically in the case that
**a'=b'=c'=d'=k/2** since then **a' ^{2}+b'^{2}+c'^{2}+d'^{2} = k^{2}**. Although we
could give a proof that works just in that case, it is just as easy and
computationally better to give an argument that halves

**((a+b)/2) ^{2} + ((a-b)/2)^{2} + ((c+d)/2)^{2} + ((c-d)/2)^{2} = (k/2)p**

which completes the proof.

Reproduced here with permission of the author.

Click here to open an applet that finds the decomposition of positive integer numbers as a sum of up to four squares using this method.

*by Dario Alejandro Alpern*

The methods shown above work only when the complete prime factorization of the number is known. If this is not the case a modification is required.

Since it is much easier to test whether a number is prime than factoring it, the following method suggests itself:

If the number does not have the form **4 ^{r} (8k+7)** it can be expressed as a sum of three squares. In this case subtract a square to the original number such that the difference is a prime of the form

Unluckily this simple method does not work: when a number is multiple of 4, we cannot find a difference of the form **4k+1** by subtracting one or two squares.
Also, when the number has the form **8k+3** it can be expressed as a sum of three squares, but subtracting a square we cannot obtain a number of the form **4k+1**.
It is not difficult to change the idea so it works.

The method can be stated as follows:

- Express the original number in the form
**n = 4**where^{r}s**s**is not multiple of 4. - Compute the square root of
**s**. If this number squared equals**s**, the original number is a perfect square, so skip the following two steps. - If
**s < 7 (mod 8)**the number can be expressed as a sum of three squares. Subtract a square and check whether the result has the form**2**where^{m}(4k+1)**m**is a non-negative integer. If not, select another square and repeat. Finally check if the number**4k+1**is prime. If not, select another square and repeat. The resulting difference,**2**, can be expressed as a sum of two squares as explained above. In the sequence of squares, the first attempt should be zero in order to minimize the number of summands in the decomposition.^{m}(4k+1) - Otherwise, the number must be expressed as a sum of four squares. Subtract two perfect squares from
**s**such that the difference has the form**2**and proceed as in the previous step.^{m}(4k+1) - At this moment
**s = a**, where some variables can be equal to zero. Multiply by^{2}+ b^{2}+ c^{2}+ d^{2}**4**to get^{r}**n = (2**.^{r}a)^{2}+ (2^{r}b)^{2}+ (2^{r}c)^{2}+ (2^{r}d)^{2}

It is not necessary to use a certified-prime test in the loop used in the method. This is because we are satisfied if we find a number **q** such that **q ^{2} = -1 (mod (4k+1))**.
This number

A disadvantage of this method is that a number that is a product of big primes of the form **4k+1** will be expressed as a sum of three squares instead of two.

Click here to open an applet that finds the decomposition of positive integer numbers as a sum of up to four squares using this method.

Last updated February 19th, 2003.