wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Sum of two squares - elementary number theory
        
(Message started by: Pietro K.C. on May 25th, 2004, 6:04pm)
Title: Sum of two squares - elementary number theory
Post by Pietro K.C. on May 25th, 2004, 6:04pm
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! :P
Title: Re: Sum of two squares - elementary number theory
Post by Sir Col on May 26th, 2004, 4:30am
But it isn't true, is it?!  ???

I thought...
::[hide]
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.
[/hide]::
Title: Re: Sum of two squares - elementary number theory
Post by grimbal on May 26th, 2004, 6:17am
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.
Title: Re: Sum of two squares - elementary number theory
Post by Sir Col on May 26th, 2004, 4:00pm
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 05/26/04 at 06:17:34, 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.
Title: Re: Sum of two squares - elementary number theory
Post by Icarus on May 26th, 2004, 7:29pm
That seems to tie in rather well with what Pietro said:


on 05/25/04 at 18:04:05, 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! :P
Title: Re: Sum of two squares - elementary number theory
Post by Pietro K.C. on May 27th, 2004, 7:32am
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! :)
Title: Re: Sum of two squares - elementary number theory
Post by Sir Col on May 27th, 2004, 11:43am
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.   ???
Title: Re: Sum of two squares - elementary number theory
Post by grimbal on May 27th, 2004, 4:37pm
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?
Title: Re: Sum of two squares - elementary number theory
Post by Pietro K.C. on May 28th, 2004, 5:14am

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.)
Title: Re: Sum of two squares - elementary number theory
Post by Barukh on May 28th, 2004, 5:38am
This kind of problems are always interesting, Pietro!  :D

So let's see what do we have:


on 05/27/04 at 07:32:30, 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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1078017611;start=0 ) and here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1085419493).
Title: Re: Sum of two squares - elementary number theory
Post by Eigenray on May 28th, 2004, 11:04pm

on 05/28/04 at 05:14:07, 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.
Title: Re: Sum of two squares - elementary number theory
Post by Pietro K.C. on May 29th, 2004, 1:39pm
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? :)
Title: Re: Sum of two squares - elementary number theory
Post by Barukh on May 30th, 2004, 6:44am

on 05/29/04 at 13:39:51, 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?  ;)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board