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.
We start with a2+b2=kp, and call this equation (1).
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
(aA+bB+cC+dD)2+(aB-bA+cD-dC)2+(aC-cA+dB-bD)2+(aD-dA+bC-cB)2
= mk2p.
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
(aD-dA+bC-cB)/k = (2*0-6*-1+2*1-7*-1)/3 = 5
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).
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:
(a2+b2+c2+d2)(A2+B2+C2+D2) = (aA+bB+cC+dD)2+(aB-bA+cD-dC)2+(aC-cA+dB-bD)2+(aD-dA+bC-cB)2
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),
- (a*b/P) = (a/P)*(b/P).
- (1/P)=1.
- (-1/P) = (-1)(p-1)/2.
From this, there is a corollary:
- (-1/P) = 1 if p mod 4 = 1.
- (-1/P) = -1 if p mod 4 = 3.
Related Pages in this website
Quadratic Residues
Irrationality Proofs --
Proofs that p and e are irrational.
Pythagorean Theorem
Prove that the area
of a right triangle with integer sides is not a perfect square.
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
|
