Sunday, March 5, 2006

When, Oh When, Is It Divisible? Topic: Number Theory. Level: Olympiad.

Problem: (1998 IMO - #4) Determine all pairs $(x,y)$ of positive integers such that $x^{2}y+x+y$ is divisible by $xy^{2}+y+7$.

Solution: At first glance, this is a rather ugly problem... but the solution turns out to be not so bad. A little tedious, but that's ok!

If $ (xy^2+y+7)|(x^2y+x+y) $, then there exists a positive integer $ k $ such that $ k(xy^2+y+7) = x^2y+x+y $, or

$ 7k-y = (xy+1)(x-ky) $.

This form seems a little more useful, as factorizations usually are in divisibility problems. First we claim that all solutions have both sides nonnegative.

Suppose $ 7k-y < 0 $. But then we have

$ |7k-y| < |y| < |xy+1| < |xy+1||x-ky| $,

which is a contradiction. So both sides are nonnegative. Now consider the two cases: (1) both sides are zero, and (2) both sides are positive.

Case 1: Both sides are zero.

Then we have $ 7k-y = 0 \Rightarrow y = 7k $. And also $ (xy+1)(x-ky) = 0 $, but since $ xy+1 > 0 $ we know $ x-ky = 0 \Rightarrow x = ky = 7k^2 $. So we have all solutions of the form $ (x,y) = (7k^2, 7k) $.

Case 2: Both sides are positive.

Then $ x > ky $ so the RHS is positive. So we have

$ 7k > 7k-y = (xy+1)(x-ky) > (xy+1) > y^2k+1 $.

Hence $ y < 3 $. So we check $ y = 1, 2 $.

For $ y = 1 $, we have $ (x+8)|(x^2+x+1) $. Since

$ \frac{x^2+x+1}{x+8} = x-7+\frac{57}{x+8} $,

we have $ (x+8)|57 \Rightarrow x = 11, 49 $, giving the solutions $ (11,1) $ and $ (49,1) $.

For $ y = 2 $, we have $ (4x+9)|(2x^2+x+2) \Rightarrow (4x+9)|(4x^2+2x+4) $. Since

$ \frac{4x^2+2x+4}{4x+9} = x-\frac{7x-4}{4x+9} $,

so $ (4x+9)|(7x-4) $. But since $ 2(4x+9) > 7x-4 $, we must have $ 4x+9 = 7x-4 $, which does not have an integer solution.

Hence our only solutions are $ (x,y) = (11,1); (49,1); (7k^2, 7k) $ for positive integers $ k $. QED.

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

Comment: Again, another divisibility problem in which it is very easy to overlook some solutions because they are very strange. But working through every case gives the desired solution.

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

Practice Problem: (2003 IMO - #2) Determine all pairs of positive integers $(a,b)$ such that

$\frac{a^2}{2ab^2-b^3+1}$

is a positive integer.

1 comment:

  1. Well one set of solutions is (2k,1)... :)

    ReplyDelete