Perfect Square

Date: 07/23/2001 at 22:44:32
From: Lory
Subject: Perfect square

If  g.c.d.(x, 3) = 1  and  g.c.d.(y, 3) = 1, show that  x^2 + y^2  
cannot be a perfect square.

What I tried:  

Since gcd(x, 3) = 1,  x = 1(mod3) or x = 2(mod3). So, x - 1 = 3k  for 
some integer k (as well, I would later have to consider the case where  
x - 2 = 3m  for some m). So, I could then try using 3k + 1 in place of 
x, and similarly  y = 3a + 1 (same reasoning).  

But when I worked out (3k+1)^2 + (3a+1)^2, I couldn't get the result 
to look as if it might or might not be a perfect square. Anyway, after 
this, do I have to try all combinations of x and y? (There would be 
4.) And would I also have to go backward and show that if x^2 + y^2 is 
not a perfect square, then gcd(3, x) = gcd(3, y) = 1? I don't think 
so, since it doesn't say "prove... iff...", right?

Please help!

Date: 07/24/2001 at 14:02:23
From: Doctor Paul
Subject: Re: Perfect square

What you've done here is okay, but you're taking the wrong approach.  
You need to work more with modular arithmetic. Here's the idea:

x = 1 mod 3 or 2 mod 3

y = 1 mod 3 or 2 mod 3

Then x^2 + y^2 is one of these four possibilities:

Case 1: x^2 + y^2 = 1^2 mod 3 + 1^2 mod 3 = 2 mod 3

Case 2: x^2 + y^2 = 1^2 mod 3 + 2^2 mod 3 = 2 mod 3

Case 3: x^2 + y^2 = 2^2 mod 3 + 1^2 mod 3 = 2 mod 3

Case 4: x^2 + y^2 = 2^2 mod 3 + 2^2 mod 3 = 2 mod 3

So if (x,3) = 1 and (y,3) = 1, then x^2 + y^2 must be two more than a 
multiple of three.

Can you show that there is no perfect square which is two more than a 
multiple of three? If you can, then you're done.

To do that, just consider all possible cases - there are only three of 
them: if z is some integer, then either 

  z = 0 mod 3, 
  z = 1 mod 3, or 
  z = 2 mod 3

In no case is z^2 2 mod 3. Thus no perfect square is two more than a 
multiple of three, and so x^2 + y^2 (which is always 2 mod 3 in our 
cases above) therefore cannot be a perfect square.

That completes the proof.

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