Divisibility and Modulo Arithmetic at IMO 2007

Here's Problem 5 from IMO 2007:

  Let a and b be positive integers. Show that if 4ab - 1 divides (4a² - 1)², then a = b.

Solution

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

Copyright © 1996-2017 Alexander Bogomolny

Solution

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 ab. With this symmetry we may assume that b > a. Then

(*)(4a² - 1)² = m(4ab - 1), with m < 4a² - 1.

This is because, with b > a,

 m(4ab - 1)= (4a² - 1)²
  < (4a² - 1)(4ab - 1)

making m < 4a² - 1.

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, ab, 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| |Geometry|

Copyright © 1996-2017 Alexander Bogomolny

 62610383

Search by google: