Decomposition of Primes as the Sum of Two SquaresDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/