The '*Four square theorem* states that every positive integer can be expressed as the sum of four squares. (Some of the squares may be zero.)

## Proof outlineEdit

Let *n* be a positive integer. We'll prove that

- n=a
^{2}+b^{2}+c^{2}+d^{2}, for integers*a, b, c, d*.

We see that 1 can be expressed as the sum of four squares, namely 1+0+0+0, and 2 can be expressed as 1+1+0+0. We shall see that primes of the form 4k+1 can be expressed as the sum of two squares, *i.e.* a^{2}+b^{2}+0+0. And we shall see that all primes of the form 4k+3 can be expressed as the sum of four squares. Finally, we know from the Quaternion identity that the product of two numbers, each of which can be expressed as the sum of four squares, can be expressed as the sum of four squares. By repeated application of the Quaternion identity, we have a way to express as the sum of four squares any nonempty finite product of numbers, each expressed as the sum of four squares. Since n can be decomposed as the product of 1 and a bunch of primes, n can be expressed as the sum of four squares.

## Constructive proofEdit

The proof presented here will be constructive. MathHelp has taken up the task of writing algorithms, which can be done by hand, or written as VBA programs that actually find the four squares whose sum is any given number, *n*. To be as helpful as possible, we will make some observations that simplify the task. We'll follow that by the identities and lemmas we'll need for the proof itself.

## Some observationsEdit

If *n* has a square factor, that is, if the prime factorization of n includes any primes raised to an exponent of 2 or larger, then all of these even-exponent primes can be gathered together to find the largest square factor of *n*, which we can then divide out. Let *s*^{2} be this large square factor, with *n*=*ms*^{2}, and so *m* is squarefree. Then

*m*=a^{2}+b^{2}+c^{2}+d^{2}implies*n*=(sa)^{2}+(sb)^{2}+(sc)^{2}+(sd)^{2}.

If *n* is even, n=2m, and

*m*=a^{2}+b^{2}+c^{2}+d^{2}implies

*n*=2*m*=(a+b)^{2}+(a-b)^{2}+(c+d)^{2}+(c-d)^{2}

WLOG, for our proof, we'll assume *n* is squarefree and odd. For the algorithm to actually find the four squares, we'll start by factoring out the largest square, and any remaining factor of two, and hold those factors aside until the end.

## IdentitiesEdit

*Main article: Complex product identity*- (a
^{2}+b^{2})(A^{2}+B^{2}) = (aA+bB)^{2}+(aB−bA)^{2}

*Main article: Quaternion 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-bC+cB-dA)^{2}

## Lemma 1: square root of -1 (mod p); p is of the form 4k+1Edit

*Main article: Square root of -1 (mod p)*

We shall see that the square root of -1 (mod p) exists, as long as p is of the form 4k+1. Fermat's little theorem tells us that all the elements of {1, 2, ..., *p*-1} are roots of the polynomial x^{p-1}−1 = 0 (mod p). We can factor

- x
^{p-1}−1 = (x^{(p-1)/2}+1)(x^{(p-1)/2}−1),

each factor of which has at most (p-1)/2 roots, and together having exactly p-1 roots, so each factor has exactly (p-1)/2 roots, assuring not just the existence but the plentiful supply of such an *x* where x^{(p-1)/2}=-1, so the square roots of -1 are ±*x*^{(p-1)/4}.