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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum