# document.write (document.title)

 Math Help > Number Theory > Squares > Sums of Squares

# Sums of Squares

## Every positive integer is the sum of four squares

Some of the four squares can be zero, so it's fair to say that the sum of 1, 2, or 3 squares can be expressed as the sum of 4 squares, of which some are zero.

The Quaternion Identity (see below) gives us a way to express the product of two numbers (each of which can be expressed as the sum of 4 squares) as the sum of 4 squares.

Since every number can be expressed as the product of primes, it's enough to show that every prime can be expressed as the sum of 4 squares.

This can be illustrated with the following practical method of expressing any number, n, as the sum of four squares:

First, factor out the largest square factor, s2, leaving only distinct prime factors, p1p2p3...pm. (n=s2p1p2p3...pm)

Then use repeated applications of the Quaternion Identity.  This is a cute trick in which two numbers, each of which are expressed as the sum of four squares, can be multiplied together and expressed as the sum of four squares.  The hard part, which is the bulk of this web page, is finding four squares that add up to a given prime number.  Once that's done for all the prime factors of n, then it's just a matter of multiplying them together, like this:

Let A0=1, and B0=C0=D0=0.

For each k, where k varies from 1 to m, do the following steps, which are repeated applications of the Quaternion Identity:

find four squares ak2, bk2, ck2, dk2 whose sum is pk.
Let Ak=(akAk-1 + bkBk-1 + ckCk-1 + dkDk-1),
Let Bk=(akBk-1 - bkAk-1 + ckDk-1 - dkCk-1),
Let Ck=(akCk-1 - ckAk-1 + dkBk-1 - bkDk-1),
Let Dk=(akDk-1 - dkAk-1 + bkCk-1 - ckBk-1)

Finally, the original number, n, can be expressed as the sum of four squares this way:

n = (sAm)2 + (sBm)2 + (sCm)2 + (sDm)2

Now we know that any composite number can be expressed as the product of primes, so all we need to show is that any prime number can be expressed as the sum of four squares, and we have a method of expressing their products as the sum of four squares, too.  Primes of the form 4k+1 can be expressed as the sum of two squares, as explained immediately below.  Primes of the form 4k+3 can be expressed as the sum of three or four squares, as explained below that.  That leaves only the smallest prime, 2, which can be expressed as 12+12.

Since any prime can be expressed as the sum of four squares, and any product of two sums of four squares can be expressed as the sum of four squares, our proof is not only complete, but constructive as well.

## Primes of the form 4k+1 can be expressed as the sum of two squares

Use the procedure, below, to find a number, a, such that a2 = -1 (mod p).

Then, once you have found a square root of -1, mod p, then the following algorithm will give you a pair of squares whose sum is p.

a2 = -1 (mod p),
so a2+12=kp, and since a < p, a2+12<p2, so k < p.

The following is an iterative procedure which, given a2+b2=kp, finds a new pair of numbers A2+B2=k'p, where k' <= k/2.  By repeating this procedure, we find values of k that are smaller and smaller, eventually reaching 1.  In this way, we find a pair of numbers A and B such that A2+B2=p.

Let A be the absolutely least residue of a mod k --
i.e. the smaller in absolute value of the residue a, mod k, and a-k
let B be the absolutely least residue of b mod k.
Then A and B are in the interval (-k/2,k/2], so
A2+B2 <= (k/2)2+(k/2)2 = k2/2.
Also, since A=a (mod k) and B=b (mod k), A2+B2=a2+b2=0 (mod k), or in other words,
A2+B2=mk, with m<k, and call this equation (2).

Multiplying the left-hand and right-hand sides of equations (1) and (2),
(a2+b2)(A2+B2) = mk2p = (aA+bB)2+(aB-bA)2, from the Complex Product Identity
aA+bB = a2+b2 = 0 (mod k), and aB-bA = ab-ba = 0 (mod k), so we can divide through by k2, giving us
((aA+bB)/k)2+((aB-bA)/k)2 = mp

This algorithm completes in log2p time, resulting in a pair of squares adding up to p.

Example: find two numbers whose squares add up to 53

Start looking for an x such that x26=-1 (mod 53).
226=-1 (mod 53), so let a=213=-23 is a square root of -1, and let b=1...
a2 + b2 = kp.  Filling in the numbers,
(-23)2 + 12 = 53k, so k=10
The absolutely least residue of -23 and 1 mod 10 are A=-3 and B=1.
My new "a" and "b" are (aA+bB)/k and (aB-bA)/k, which are
(-23*(-3)+1*1)/10=7  and  (-23*1-1*(-3))/10=-2.

Starting over, with a=7 and b=-2, we have a2 + b2 = kp:
72 + (-2)2 = 53k, so k=1.  We've found our two numbers whose squares add up to 53.

## Primes of the form 4k+3 can be expressed as the sum of four squares

We begin by finding a solution to y2=-1-x2 (mod p).  (See the proof that there's at least one solution, below.)

Empirically, we just start examining possible values for the right-hand-side: -1-22, -1-32, etc. until we find one that's a quadratic residue (i.e. a perfect square), mod p.  In practice it seldom takes many tries, because about half of all these numbers are quadratic residues.  And luckily, for primes of the form 4k+3, there's an excellent test to see if it's a quadratic residue.

From Fermat's Little Theorem, we know that

cp-1 = 1 (mod p),
so cp+1 = c2 = (-c)2 (mod p),
so c(p+1)/4 is a square root of c (mod p), or c(p+1)/4 is a square root of -c (mod p).

In practice, to see if a number, c, is a quadratic residue, mod p, we set b=c(p+1)/4, and then check whether b2=c.  If it is, then we've found a solution to y2=-1-x2.

The test works by checking successively

Is (-1-12)(p+1)/2 = -1-12 ?
Is (-1-22)(p+1)/2 = -1-22 ?
Is (-1-32)(p+1)/2 = -1-32 ?
...

Until we find a solution such that (-1-x2)(p+1)/2 = -1-x2.
Then, since y2 = -1-x2 = (-1-x2)(p+1)/2, we know that y = (-1-x2)(p+1)/4.

We start by letting a be the absolutely least residue of y, b be the absolutely least residue of x, c=1, and d=0.

|a| < (p-1)/2 and |b| < (p-1)/2, so a2+b2+1 < p2/2, so a2+b2+c2+d2 = kp, with k<p.

Then we follow an iterative procedure similar to that for primes of the form 4k+1, except using the Quaternion Identity (see below) instead of the Complex Product Identity.  In this procedure, given a2+b2+c2+d2=kp, we find a new set of four numbers A2+B2+C2+D2=k'p, where k' <= k/2.

If k is odd...

As before, we start with a2+b2+c2+d2 = kp, and call this equation (1)
Let A, B, C, and D be the absolutely least residues mod k of a, b, c, and d.
Then each of |A|, |B|, |C|, and |D| is <= (k-1)/2, so
A2+B2+C2+D2 <= (k-1)2
A2+B2+C2+D2 = a2+b2+c2+d2 = 0 (mod k), so
A2+B2+C2+D2 = mk, with m<k, and call this equation (2).

As before, we multiply equations (1) and (2) together, giving
(a2+b2+c2+d2)(A2+B2+C2+D2) = mk2p, and from the Quaternion Identity, we get
As before, each of these terms is a multiple of k
Now our four squares are ((aA+bB+cC+dD)/k)2, ((aB-bA+cD-dC)/k)2, ((aC-cA+dB-bD)/k)2, and ((aD-dA+bC-cB)/k)2.

If k is even...

The algorithm, above, fails if A=B=C=D=k/2, because then equation (2) has a right-hand-side of k2, so m is not less than k, and it will just go on forever.  Otherwise, the algorithm, above, could be used for even k as well.  In any case, the following method is a little better, and it works whenever k is even.

Notice that exactly zero, two, or four of a, b, c, d are odd.  Permute the numbers so that a and b are either both even or both odd, and c and d are likewise either both even or both odd.  Then
((a+b)/2)2 + ((a-b)/2)2 + ((c+d)/2)2 + ((c-d)/2)2 = (k/2)p

Example: find two numbers whose squares add up to 31

Start looking for an a such that (-1-a2)16 = -1-a2 (mod 31)

When a=1, -1-a2=-2, and (-1-a2)16=2.  No good.
When a=2, -1-a2=-5, and (-1-a2)16=5.  No good.
When a=3, -1-a2=-10, and (-1-a2)16=10.  No good.
When a=4, -1-a2=14, and (-1-a2)16=14.  Ahah!

Now we let b2 = -1-a2 = (-1-a2)16 (mod 31), so b = (-1-a2)8.

So we start with the absolute least residuals a=4, b=(-1-42)8=13, c=1, and d=0.
42 + 132 + 12 + 02 = 186 = kp = 6*31.
Since k is even, we use the second rule, and permute the numbers so the first two and the last two have the same parity:
4, 0, 13, and 1.
Now calculate the sums and differences, divided by 2:
(4+0)/2, (4-0)/2, (13+1)/2, and (13-1)/2 are 2, 2, 7, and 6.
22 + 22 + 72 + 62 = 93 = kp = 3*31.

Since k is odd, we use the first rule, and calculate the absolutely least residuals of
2, 2, 7, 6 mod 3 -- they are -1, -1, 1, 0.
Now, from the quaternion identity, find
(aA+bB+cC+dD)/k = (2*-1+2*-1+7*1+6*0)/3 = 1
(aB-bA+cD-dC)/k = (2*-1-2*-1+7*0-6*1)/3 = -2
(aC-cA+dB-bD)/k = (2*1-7*-1+6*-1-2*0)/3 = 1
12 + -22 + 12 + 52 = kp = 31, so k=1, and we're done!

## Procedure to find a number, a, such that a2 = -1 (mod p), where p is of the form 4k+1

Existence

if p is a prime of the form 4k+1, then there is a number a such that a2 = -1 (mod p).

Proof:
Let h, which stands for "half", be given by h=(p-1)/2.  E.g. if p=13 then h=6.
Let a be any number not divisible by p, such that ah=-1.  (From the "Polynomial Roots" discussion, below, we see that half of all possible values of a between 0 and p have this property.)
Let b=ah/2, in which case b2=-1 (mod p).

. . . . . . reference Legendre Symbol

Method

To find a number, b, such that b2 = -1 (mod p), follow this procedure:

Test possible values of a to find one such that ah=-1.
Then let b=ah/2.
In practice, the smallest value of a with this property will be a prime, so you can save a little time by making a list of primes, and checking them first.

## Polynomial Roots xp-1 - 1 = 0 (mod p), where p is an odd prime

Consider the polynomial xp-1 - 1 = 0 (mod p).
By Fermat's Little Theorem, this polynomial has p-1 roots, namely {1, 2, 3, ..., p-1}.
Let h, which stands for "half", be given by h=(p-1)/2.  E.g. if p=13 then h=6.
Observe that xp-1-1 can be factored as (xh-1)(xh+1).
The polynomial xh-1=0 (mod p) can have at most h roots, and the other factor of xp-1-1 tells us that
the polynomial xh+1=0 (mod p) can have at most h roots.

For any a, ah=1 or ah=-1.  In fact, for exactly half of the possible choices of a, ah=1, and for the other possible choices of a, ah=-1.

## Fermat's Little Theorem

ap-1 = 1 (mod p), where p is prime and a≠0 (mod p)

Proof: take a to be any number 0 < a < p.
Consider the set {a, 2a, 3a, ..., (p-1)a}.
No two elements of this set are congruent mod p, so their residues mod p must be {1, 2, 3, ..., p-1} in some order.
By taking the products of the numbers in the two sets,
ap-1(p-1)! = (p-1)! (mod p)
Since (p-1)! (mod p) is not zero, we can divide both sides by (p-1)!, proving Fermat's Little Theorem.

## Proof that there is at least one solution to y2=-1-x2 (mod p)

First, let's look at the left side of this equation.
Let a and b be such that 0 <= a <= (p-1)/2, and 0 <= b <= (p-1)/2.
If a2-b2=0 (mod p) then (a-b)(a+b)=0 (mod p).  It's not possible for a+b=0 (mod p) so a=b.
So the squares of {0, 1, ..., (p-1)/2} have (p+1)/2 distinct residues.

Now, for the right side of the equation.
By the similar reasoning, the numbers {-1-02, -1-12, ..., -1-((p-1)/2)2} have (p+1)/2 distinct residues.

Since altogether there can be no more than p distinct residues, the two sets of residues overlap, and there must be one in common between the two sets.

## The Quaternion Identity

So called because if u=a-bi-cj-dk and U=A+Bi+Cj+Dk, |uU| = |u||U|.  Squaring both sides gives:

Thus, the product of any two numbers, each of which can be expressed as the sum of four squares, can also be expressed as the sum of four squares.

## The Complex Product Identity

The product of any two numbers, each of which can be expressed as the sum of two squares, can also be expressed as the sum of two squares:

(a2+b2)(A2+B2) = (aA+bB)2+(aB-bA)2

A variant of the Complex Product Identity shows that the product of two numbers, each of which has the form a2+3b2 can also be expressed in the form a2+3b2.

(a2+3b2)(A2+3B2)=(aA-3bB)2+3(aB+bA)2

This identity is used in the proof of the n=3 case of Fermat's Last Theorem.

### Internet references

Dario Alpern's Four Squares page, which provided most of the information on this page, and in addition hinted that there is a simple proof that -1 isn't a quadratic residue (mod p) when p=4k+3.

Mathpages: The Jewel of Arithmetic: Quadratic Reciprocity  provides an answer to this simple proof.  Euler's Criterion for quadratic residue is that
a is a quadratic residue (mod p) iff a(p-1)/2 = 1 (mod p).
Using the Legendre Symbol (a/p) to denote a(p-1)/2 = 1 (mod p),

1. (a*b/P) = (a/P)*(b/P).
2. (1/P)=1.
3. (-1/P) = (-1)(p-1)/2.

From this, there is a corollary:

1. (-1/P) = 1 if p mod 4 = 1.
2. (-1/P) = -1 if p mod 4 = 3.

### Related Pages in this website

Legendre Symbol - (a/p) = 1 iff a is a quadratic residue, i.e. nonzero square, (mod p), where p is an odd prime

Quadratic Residues - Modular Arithmetic and the Quadratic Equations ax^2+bx+c=0, a(p-1)/2 ≡�1 (mod P), a is a quadratic residue (mod p) iff a^((p-1)/2)≡1 (mod p), Legendre Symbol, Prime of form 4k+1 is a "Pythagorean Prime" because it can be expressed as the sum of two squares, Legendre (2/p) = (p^2-1)/8 (mod p) attributed to Gauss, quadratic reciprocity law, computing sqrt (mod p) using Tonelli-Shanks algorithm

Irrationality Proofs -- Proofs that π and e are irrational.

Pythagorean Theorem

Arithmetic Sequence of Perfect Squares, page 3 -- If a2, b2, c2 are in arithmetic sequence, why is their constant difference a multiple of 24?  Look at the second answer to this question for the relationship between Pythagorean Triples and this arithmetic sequence of squares.

Fermat's Theorems, and, in particular, the n=3 case of Fermat's Last Theorem

Octonion: contains a description of Degen's Eight Square Identity, which is the 8-tuple analog to the quaternion and complex product identities described in this page.

Triangle Area Puzzle - What is the area of triangle whose sides are sqrt(61), sqrt(153), sqrt(388)? 61, 153, 388 are each sum of two squares, so the sides of this triangle can be drawn as the hypotenuses of three right triangles.

The webmaster and author of this Math Help site is Graeme McRae.