Decomposition of Primes as the Sum of Two Squares

Date: 12/17/2005 at 12:54:51
From: Geertrui
Subject: uniqueness of p=sum of two squares

I would like to know why, if you write p (prime) as a sum of two 
squares, its decomposition a^2 + b^2 is unique (a,b up to +/- 1).

I was able to prove that you can write a prime p as a sum of two 
squares iff p = -1 mod 4 but in my further work on the issue I have to 
have a unique decomposition for the primes and I can't get it.

Date: 12/17/2005 at 18:08:25
From: Doctor Vogler
Subject: Re: uniqueness of p=sum of two squares

Hi Geertrui,

Thanks for writing to Dr. Math.  That's a very good question.  I
actually ran across this same question very recently in my own work,
and it took a little while to come up with the following answer:  Yes,
the decomposition is unique, because the regular prime numbers can't
factor into more than two primes in the ring of Gaussian integers.

What does that mean?  Well, Gaussian integers are numbers of the form

  a + bi

where a and b are integers (and i is the complex number, a square root
of -1).  It is easy to prove that the sum or product of two Gaussian
integers is also a Gaussian integer.  It takes more work to show that
Gaussian numbers factor into Gaussian primes, where Gaussian primes are

  1 + i (which lies over 2),
  a + bi and a - bi, when a^2 + b^2 is prime (which these lie over),
  p, when p is a prime congruent to 1 mod 4 (which lies over p).

We say that a Gaussian prime "lies over" a normal prime when its norm
is a power of that normal prime.  The norm of a Gaussian number is the
number times its conjugate, so

  norm(a + bi) = (a + bi)(a - bi) = a^2 + b^2,

which is a real integer.  It also takes work to show that there are at
most two Gaussian primes that lie over any normal prime.

Now, when factoring Gaussian integers, you also have to handle units,
which behave somewhat differently than primes.  Units are integers
with multiplicative inverses.  In the regular integers, the only units
are +1 and -1, so every integer is a unit (+1 or -1) times a product
of primes.  Now, we say that 2 is prime, and in some sense -2 is
really the _same_ prime.  We could use -2 instead of 2 and the
statement about prime factorization would still be true.  We just use
2 because we more frequently talk of factoring _positive_ numbers. 
Well, Gaussian integers have four units (+1, -1, +i, and -i).  So that
means that

  1 + i  and  1 - i

are really the same Gaussian prime, since

  1 + i = i*(1 - i),

and we could use either one.  So I just arbitrarily pick the first. 
Similarly,

  a + bi = i*(b - ai)
  a + bi = -i*(-b + ai)
  a + bi = -(-a - bi)

  a - bi = i*(-b - ai)
  a - bi = -i*(b + ai)
  a - bi = -(-a + bi)

so the eight solutions to the equation

  x^2 + y^2 = p,

which are

  (a, b)
  (-a, b)
  (a, -b)
  (-a, -b)
  (b, a)
  (-b, a)
  (b, -a)
  (-b, -a)

only give you two different Gaussian primes.

Now, I said that it takes work to show that Gaussian numbers factor
into Gaussian primes, and it also takes work to show that there are at
most two Gaussian primes that lie over any normal prime.  So I will
try to prove the second without using the first.

Suppose that

  p = a^2 + b^2 = c^2 + d^2

for some prime number congruent to -1 mod 4.  We would like to show
that (c, d) is just the same as (a, b) except for possibly switching
one or both signs, or exchanging a and b.  So what happens if we divide

  a + bi
  ------ ?
  c + di

Well, we might hope to be able to prove that this has to be a unit
Gaussian integer, if the numerator and denominator correspond to the
same Gaussian prime, but remember that there are two Gaussian primes
that lie over p.  So we will try to prove that either

  a + bi   (a + bi)(c - di)   (ac + bd) + (bc - ad)i
  ------ = ---------------- = ----------------------
  c + di   (c + di)(c - di)             p

or

  a + bi   (a + bi)(c + di)   (ac - bd) + (bc + ad)i
  ------ = ---------------- = ----------------------
  c - di   (c - di)(c + di)             p

is a Gaussian unit.  The hardest part is proving that either

  x = (ac + bd)

or

  y = (ac - bd)

is divisible by p.  We could go on to proving that the imaginary part
is also an integer, and that this number also has an inverse that is a
Gaussian integer, so that we have a unit.  Then we show that

  norm(x) * norm(y) = norm(xy)

and therefore units must have norm 1, from which we can prove that all
units are +1, -1, +i, and -i, like I said.  But actually we can stop
after proving that x or y is divisible by p and jump right to our
conclusion.

So here is the proof, which makes no references to Gaussian integers
except to come up with the idea of the proof (which I already explained):

Suppose that

  p = a^2 + b^2 = c^2 + d^2.

As I said before, we would like to show that (c, d) is just the same
as (a, b) except for possibly switching one or both signs, or
exchanging a and b.  So let's fix the signs and order by assuming that

  0 < a < b, and
  0 < c < d.

Notice that we can't have a = 0, because p is not a square, and we
can't have a = b, since p is not even.  Furthermore, we can switch the
solution (a, b) with (c, d), if necessary, in order to have

  a < c.

Notice that if we have a = c, then this also implies that b^2 = d^2
and therefore (since b and d are positive) b = d, and so we just have
two identical solutions.  So now we conclude that

  0 < a < c < d,

and it turns out that we have to have b bigger than d, since

  b^2 = d^2 + (c^2 - a^2),

and c^2 - a^2 is positive.  So we have

  0 < a < c < d < b.

We want to prove that this is impossible.  What's more, since

  a < b

implies that

  a^2 < b^2

and

  a^2 - p/2 < b^2 - p/2,

but

  (a^2 - p/2) + (b^2 - p/2) = 0,

which means that 

  a^2 - p/2 < 0 < b^2 - p/2.

Similarly for c and d.  Also

  b^2 = p - a^2 <= p,

so we may conclude that

  0 < a < c < sqrt(p/2) < d < b < sqrt(p).

Now, let

  x = (ac + bd)
  y = (ac - bd)

Then we have

  xy = (ac)^2 - (bd)^2
     = (a^2)(c^2 + d^2) - (d^2)(a^2 + b^2)
     = (a^2)p - (d^2)p
     = (a^2 - d^2)p

is divisible by p.  Since p is prime, either x or y is divisible by p.
But from

  0 < a < c < sqrt(p/2) < d < b < sqrt(p).

we conclude that

  0 < x < p/2 + p < 2p,

and

  -p < -bd < y < ac < p/2

which means that the only ways that x or y could be divisible by p is if

  x = p

or

  y = 0.

But y = 0 means that

  ac = bd,

but ac < p/2, whereas bd > p/2, so y = 0 is impossible.  The only
possibility left is

  x = ac + bd = p.

Now (recalling that this is supposed to correspond to the Gaussian
unit +1), we would like to show that if this happens, then

  bc - ad = 0.

So we compute

  (bc - ad)^2 + (ac + bd)^2 = (a^2 + b^2)(c^2 + d^2) = p^2,

which means that

  (bc - ad)^2 = p^2 - (ac + bd)^2 = p^2 - x^2 = 0,

and therefore

  bc - ad = 0,

as we wanted to prove.  But if

  ac + bd = p, and
  bc - ad = 0,

then this implies that

  a + bi   (a + bi)(c - di)   (ac + bd) + (bc - ad)i
  ------ = ---------------- = ---------------------- = 1,
  c + di   (c + di)(c - di)             p

and therefore

  a + bi = c + di,

which means

  a = c and b = d.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 12/19/2005 at 09:54:13
From: Geertrui
Subject: uniqueness of p=sum of two squares

First of all, thank you for the quick answer to my question.  I have
generalized it to p^3 = a^2 + b^2 with gcd(a,b) = 1, p prime and the 
proof still works.  What I had to prove was the following: 

Let A be in {1,2,3}, let N be a natural number so that N^3 = a^2 +
Ab^2 with gcd(a,b) = 1. Then N = u^2 + Av^2 with a = u^3 - 3Auv^2 and
b = Av^3 - 3u^2v.  

I already did the descent argument to get N = u^2 + Av^2 in all three
cases.  So the only thing I need is the last part (the a=... and
b=...).  Since you've helped me with the proof that when N is prime
the a^2 + b^2 is unique, that part already works.  But what of the
general case, N any natural number?

Date: 12/20/2005 at 15:59:14
From: Doctor Vogler
Subject: Re: uniqueness of p=sum of two squares

Hi Geertrui,

Well, the numbers a and b are _not_ unique in the general case, or
even in the p^3 case.  For example,

  125 = 11^2 + 2^2 = 10^2 + 5^2,

and

  65^3 = 488^2 + 191^2 = 524^2 + 7^2.

So this means that u and v depend not only on N but also on a and b. 
Therefore, you have to define u and v in such a way that they will
satisfy the equations

  a = u^3 - 3Auv^2,
  b = Av^3 - 3u^2v.

For example,

  65^3 = 488^2 + 191^2

should give

  65 = 8^2 + 1^2

whereas

  65^3 = 524^2 + 7^2

should give

  65 = 4^2 + 7^2.

Also, you'll have to use the fact that a and b are relatively prime
(gcd = 1), since (for example) the numbers

  N = 5,
  a = 10,
  b = 5,

do not give rise to any such u and v.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/