## Tuesday, August 15, 2006

### Why Do You Exist? Topic: Number Theory. Level: AIME.

Problem: (1997 India National Olympiad - #2) Show that there do not exist positive integers $m$ and $n$ such that

$\frac{m}{n}+\frac{n+1}{m} = 4$.

Solution: Well, multiply through by $mn$ and rearrange as a quadratic in $m$. This is a good idea when you're looking at squares in diophantine equations. We get

$m^2-4nm+n(n+1) = 0$.

But for an integer solution to exist, the discriminant must be a square. So

$16n^2-4n(n+1) = 12n^2-4n = 4n(3n-1)$

must be square. However, since $(n, 3n-1) = 1$ (prove this!), they must both be squares themselves. But $3n-1 \equiv 2 \pmod{3}$, which is not a quadratic residue modulo $3$ so there are no solutions, as desired. QED.

--------------------

Comment: Diophantine equations are a favorite of olympiad test writers. Knowing how to handle them can be very beneficial for your next olympiad test...

--------------------

Practice Problem: Determine all integers $k$ such that the equation $x^2+y^2 = kxy$ has a solution in the positive integers.

1. We can assume WLOG that (x, y) = 1, since the equation is homogeneous and we can divide out by the gcd.

But then y | x^2 and x | y^2. For x, y > 1 this implies common factors. Then x = y = 1, giving k = 2 as expected.

2. We can also take the discriminant as a quadratic in x and get that (k^2-4)y^2 must be a square, so k = 2.

3. "But 3n-1 \equiv 2 \pmod{3} , which is not a quadratic residue modulo 3 so there are no solutions"

That's so complicated-sounding. Why don't you just say that 2 isn't a square mod 3 to be simple?

4. Well, square mod 3 isn't really well defined... on the other hand, quadratic residue is.

5. All the cool PROMYS kids say quadratic residue :)