Friday, August 11, 2006

Solutions? I Think Not. Topic: Number Theory. Level: AIME.

Problem: Prove that there are no positive integer solutions to $ x^2+y^2 = 3z^2 $.

Solution: Let's use our favorite tool - mods. Suppose there exists a solution $ (x,y,z) $; if they share a common factor, we can divide it out, so we can assume WLOG that they do not.

Taking modulo $ 3 $, we get

$ x^2+y^2 \equiv 0 \pmod{3} $.

We can easily see that this requires both $ x $ and $ y $ to be divisible by $ 3 $. Let $ x = 3x_0 $ and $ y = 3y_0 $. Using our original equation,

$ 9x_0^2+9y_0^2 = 3z^2 $

$ 3(x_0^2+y_0^2) = z^2 $.

Modulo $ 3 $ again,

$ z^2 \equiv 0 \pmod{3} \Rightarrow z \equiv 0 \pmod{3} $.

But then $ 3 $ divides each of $ x,y,z $, contradicting our assumption that they do not have a common factor. Hence no solution exists. QED.


Comment: More elementary number theory and work with mods; this uses the idea of infinite descent implicitly as well (i.e. we can show that $ x, y, z $ are infinitely divisible by $ 3 $). Diophantine equations are often simplified greatly through mods.


Practice Problem: What positive integers can we replace $ 3 $ with such that the problem statement still holds?


  1. Any number whose prime factorization contains a prime congruent to 3 mod 4, and does not contain the square of that prime.

  2. Sorry, I should be a bit more general than that. Precisely the numbers whose prime factorization contains a prime congruent to 3 mod 4 raised to an odd power. This is easy to deduce using the arithmetic of the Gaussian integers.

  3. I believe that simplifies to all numbers that are not the sum of two squares :)

  4. This kinda reminds me of the question, prove that there are no rational solutions to x^2 + y^2 = 3. Fun stuff.