## 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.