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