Author |
Topic: Sum of two squares - elementary number theory (Read 2634 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Sum of two squares - elementary number theory
« on: May 25th, 2004, 6:04pm » |
 Quote  Modify
|
This one was on a problem set for arithmetic number theory. I'll give two versions.
Easier) Suppose q is a prime number such that q [equiv] 3 (mod 4). Prove that the equation
X2 + Y2 = qZ
has a solution (X,Y,Z) [in] [bbz]3 with [lnot] ( XY [equiv] 0 (mod q) ) if and only if the equation
X2 + Y2 = q2Z
has such a solution.
Harder) Suppose q is an odd prime. Show the same.
Note: the 'easier' part was on the problem set, but is only easier if you know a certain number-theoretic lemma; then it becomes almost trivial. I didn't know it, so I ended up proving (harder), comparatively with a lot of effort! 
|
| « Last Edit: May 27th, 2004, 7:33am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum of two squares - elementary number theory
« Reply #1 on: May 26th, 2004, 4:30am » |
Quote Modify
|
But it isn't true, is it?! 
I thought...
::
Fermat proved that a number, N, is expressible as the sum of two squares iff, in the prime factoring of N, there are an even number of primes of the form 4k+3. If x2+y2=q2Z, and q is a prime of the form 4k+3, the prime factoring of Z must contain an even number of such primes. In which case, qZ will contain an odd number of such primes and, as a result, cannot be expressed as the sum of two squares.
::
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sum of two squares - elementary number theory
« Reply #2 on: May 26th, 2004, 6:17am » |
Quote Modify
|
It is not necessarily the same Z
If X2+Y2 = q2Z
then X2+Y2 = qZ' where Z' = qZ.
The question is to prove it the other way round.
PS: Actually it seems that
If X2+Y2 = qZ
then X'2+Y'2 = q2Z'
where X' = qX, Y' = qY, Z'=qZ.
I must miss something.
|
| « Last Edit: May 26th, 2004, 6:22am by Grimbal » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum of two squares - elementary number theory
« Reply #3 on: May 26th, 2004, 4:00pm » |
Quote Modify
|
Grimbal, it's not asking to prove it the other way round. It is asking to prove (i) IF q2Z can be written as the sum of two squares, qZ can be too, AND, (ii) qZ can ONLY be written as the sum of two squares IF q2Z can: IF AND ONLY IF.
on May 26th, 2004, 6:17am, grimbal wrote:| It is not necessarily the same Z. |
|
It's funny how I was willing to allow the X and Y to be different, but considered the Z to be the same?! 
Doesn't the problem becomes trivial now?
According to Fermat's result, X2+Y2=q2Z, where q[equiv]3 mod 4, always has a solution if Z has an even number of primes of the form 4k+3 in its prime factorisation.
Similarly, X'2+Y'2=qZ' always has a solution, if we let Z'=qZ.
As for the harder part, a corollary of Fermat's result is that the only other possibility, primes of the form 4k+1, can always be written as the sum of two squares.
Pietro K.C., are we being asked, effectively, to prove a version of Fermat's result? Because without this result the problem is indeed very challenging.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Sum of two squares - elementary number theory
« Reply #4 on: May 26th, 2004, 7:29pm » |
Quote Modify
|
That seems to tie in rather well with what Pietro said:
on May 25th, 2004, 6:04pm, Pietro K.C. wrote:| Note: the 'easier' part was on the problem set, but is only easier if you know a certain number-theoretic lemma; then it becomes almost trivial. I didn't know it, so I ended up proving (harder), comparatively with a lot of effort! |
|
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Sum of two squares - elementary number theory
« Reply #5 on: May 27th, 2004, 7:32am » |
Quote Modify
|
Hi folks!
My bad, I posted the problem with slightly wrong wording. I've fixed it now.
As grimbal pointed out, both equations
X2 + Y2 = qZ (1)
X2 + Y2 = q2Z (2)
always have solutions, namely (q,q,2q) for (1) and (q,q,2) for (2), hence the IFF statement is trivially true. The correction I made is meant to prevent us from 'cheating' like this: I've replaced
XY [ne] 0 with [lnot]( XY [equiv] 0 (mod q) ).
Sir Col also misstates Fermat's criterion a bit: the result is more restrictive than that. As a counterexample to your version, take 21 = 3[cdot]7. There is certainly an even number of prime factors that are [equiv] 3 (mod 4), but it is not possible to write 21 as a sum of two squares (try it out).
Fermat's criterion states that a number n can be written as a sum of two squares iff n is the product of:
1. any power of 2;
2. any number of primes [equiv] 1 (mod 4), each with any multiplicity;
3. any number of primes [equiv] 3 (mod 4), each with even multiplicity.
Assuming that any prime [equiv] 1 (mod 4) can be written as the sum of two squares, and in possession of the lemma I mentioned, it is not that hard to show Fermat's criterion. (So no, the lemma is not Fermat's result - it's rather more obscure.)
Using this lemma, in part (easier) it's possible to show that X and Y in (1) can be the same as X and Y in (2) - my proof for the general case gives no such guarantee, and indeed none is possible.
Good luck! 
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum of two squares - elementary number theory
« Reply #6 on: May 27th, 2004, 11:43am » |
Quote Modify
|
Sorry, I wasn't clear.
I was only stating a consequence of Fermat's result, which is why I ask if we were being asked to prove a "version" of the result. When I stated, "Z has an even number of primes of the form 4k+3 in its prime factorisation," I meant exclusively, as I was looking for the simplest possible Z; that is, Z=(4k+3)2n. However, upon reflection my suggestion was wrong anyway. If we're looking for q2Z (where Z is the form I mentioned), that is equal to the sum of two squares, then the only solution is trivial: one of X or Y will be zero, and you had not permitted that. As you correctly pointed out, the number would need to contain a factor of the form, 2k.
Thanks for clarifying and ensuring that no one else would misunderstand an important result in number theory. There is such a responsibility in posting in forums like this, as we all do so much learning from the posts that are made.
However, I don't quite follow the problem now. If XY is not allowed to be divisible by q, then I don't think there are any solutions.
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sum of two squares - elementary number theory
« Reply #7 on: May 27th, 2004, 4:37pm » |
Quote Modify
|
Wasn't there this theorem that for primes p such that p [equiv] 3 (mod 4) the values [1..p-1] are partitionned evenly into values that are a square mod p and those that are minus a square mod p?
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Sum of two squares - elementary number theory
« Reply #8 on: May 28th, 2004, 5:14am » |
Quote Modify
|
Quote:| I don't think there are any solutions. |
|
Argh! Of course there aren't. It falls right out of Fermat's criterion.
OK, I'll try to salvage the problem. Define a triple (X,Y,Z) [in] [bbn]3 to be an interesting solution to
X2 + Y2 = qZ (1)
iff X,Y are not divisible by q.
(Easier) Suppose q is a prime number such that q [equiv] 3 (mod 4). Prove that if (X,Y,Z) is any solution to (1), then Z is divisible by q. (Fermat's criterion for this kind of prime factor falls right out of this result.)
(Harder) Suppose q is an odd prime. Prove that if (X,Y,Z) is an interesting solution to (1), then there exists an interesting solution (U,V,W) such that q divides W. (Fermat's criterion implies that there are no interesting solutions for primes [equiv] 3 (mod 4), but notice you only need to prove an IF statement.)
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum of two squares - elementary number theory
« Reply #9 on: May 28th, 2004, 5:38am » |
Quote Modify
|
This kind of problems are always interesting, Pietro! 
So let's see what do we have:
on May 27th, 2004, 7:32am, Pietro K.C. wrote:Fermat's criterion states that a number n can be written as a sum of two squares iff n is the product of:
1. any power of 2;
2. any number of primes [equiv] 1 (mod 4), each with any multiplicity;
3. any number of primes [equiv] 3 (mod 4), each with even multiplicity.
|
|
Even this needs a clarification: in #2, "any number" should be changed to "at least one" (try to express 9 as a sum of two squares). Also important is the fact the two squares are co-prime iff n factors into primes of type #2, which is also partially stated here:
Quote:| Assuming that any prime [equiv] 1 (mod 4) can be written as the sum of two squares |
|
Here's the proof of the "harder" part when q [equiv] 1 (mod 4). In that case, we may put Z=1.
If (1) holds for some (X,Y), then (2) will hold for (X2-Y2, 2XY).
If (2) holds, (X,Y,q) is a primitive Pythagorean triple. As we know, the general form of such a triple has q = m2+n2, for some m, n co-prime. But this is (1).
P.S. I began to prepare the answer before the last Pietro's post, but I think it's stll relevant.
P.S. There are more threads on this site where representing a number as a sum of two squares plays central role, for instance, here and here.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum of two squares - elementary number theory
« Reply #10 on: May 28th, 2004, 11:04pm » |
Quote Modify
|
on May 28th, 2004, 5:14am, Pietro K.C. wrote:| (Easier) Suppose q is a prime number such that q [equiv] 3 (mod 4). Prove that if (X,Y,Z) is any solution to (1), then Z is divisible by q. |
|
Suppose X2 + Y2 = qZ, and that Y is not divisible by q. Then, mod q, (XY-1)2 = -1, which means XY-1 has order 4, which doesn't divide (q-1), the order of [bbz]q. Therefore q | Y, so we need q | X also, but then q2 | (X2+Y2), so q | Z.
Quote:| (Harder) Suppose q is an odd prime. Prove that if (X,Y,Z) is an interesting solution to (1), then there exists an interesting solution (U,V,W) such that q divides W. |
|
If (X,Y,Z) is an interesting solution, then as Barukh mentioned, (U,V,W) := (X2-Y2, 2XY, qZ2) is also a solution. If we had q | (X2-Y2), then, mod q,
0 = qZ = X2+Y2 = 2X2,
which means q|X, which contradicts the interest of (X,Y,Z). Similarly, we can't have q|2XY, so the new solution is interesting, and clearly q|W.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Sum of two squares - elementary number theory
« Reply #11 on: May 29th, 2004, 1:39pm » |
Quote Modify
|
Nice ones, Barukh and Eigenray!
The number-theoretic lemma I was referring to was the one Eigenray showed: if q [equiv] 3 (mod 4) is a prime number, and there are a,b [in] [bbn] such that q divides a2 + b2, then q divides both a and b.
One gripe I have is that the transition (X,Y) [smiley=longrightarrow.gif] (X2-Y2,2XY) feels very ad hoc. How did you folks come up with that? Do you just look at the problem and see it? What did you do?
A follow-up: suppose q [equiv] 1 (mod 4) is a prime and consider the equation
X2 + Y2 = qkZ (1)
Define a solution (x,y,z) [in] [bbn]3 to be k-tight iff q does not divide z.
Show that if there is at least one k-tight solution to (1), then there are l-tight solutions for all l > k.
Note: no need for Fermat's criterion here... what's the fun in using the stronger result to show the weaker?
|
| « Last Edit: May 29th, 2004, 1:41pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum of two squares - elementary number theory
« Reply #12 on: May 30th, 2004, 6:44am » |
Quote Modify
|
on May 29th, 2004, 1:39pm, Pietro K.C. wrote:| One gripe I have is that the transition (X,Y) [smiley=longrightarrow.gif] (X2-Y2,2XY) feels very ad hoc. How did you folks come up with that? Do you just look at the problem and see it? What did you do? |
|
I (eventually) saw it: as I already mentioned in my previous post, the general form of the Pythagorean triple is (m2-n2, 2mn, m2+n2) for every pair of co-prime m, n. The last term has form (1), and as a Pythagorean triple it’s (2).
BTW, this form is not too difficult to derive (it was known already to ancient Greeks). Want to try? 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print