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 :)