Divisibility and Modulo Arithmetic at IMO 2007

Here's Problem 5 from IMO 2007:

Solution

|Contact| |Front page| |Contents| |Store| |Geometry|

The problem was discussed at the wu:forums where one participant came up with a surprising symmetry implicit in the problem that led another forum member - Aryabhatta, who I heard was referred to as the Michael Phelps of math Olympiads - to a short and engaging solution.

First, let's show that the assumption that 4ab - 1 divides (4a² - 1)² implies that it also divides (a - b)². Multiply (4a² - 1)² by b², which is prime to 4ab - 1. Hence 4ab - 1 divides (4a²b - b)², which is congruent to (a - b)² modulo 4ab - 1. (Indeed, 4a²b - b = a(4ab - 1) + (a - b).)

Now, since (a - b)² is symmetric in a and b, it follows that if (4a² - 1)² is divisible by 4ab - 1 so is (4b² - 1)², rendering the problem symmetric in a and b.

Suppose that a ≠ b. With this symmetry we may assume that b > a. Then

Consider (*) modulo 4a: (-1)² = m(-1) (mod 4a), i.e., m = -1 (mod 4a). Thus m = 4ab' - 1, for some integer b' such that 0 < b' < a (b' cannot be 0 because then m = -1 implying (4a² - 1)² < 0.) Hence we have the same problem with b' playing the role of a and a playing the role of b. This leads to an infinite decreasing sequence of positive integers satisfying the same problem, contradiction. Therefore, a = b.

The descending sequence argument can be simplified by choosing a and b, a ≠ b, with the least sum a + b for which 4ab - 1 divides (4a² - 1)². Since the above argument leads to the existence of another pair with a smaller sum, the contradiction follows in an apparently more traditional manner.

|Contact| |Front page| |Contents| |Store| |Geometry|