## Divisibility and Modulo Arithmetic at IMO 2007

Here's Problem 5 from IMO 2007:

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

|Contact| |Front page| |Contents| |Store| |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 *ab* - 1*a*² - 1)²*a* - *b*)².*a*² - 1)²*b*², which is prime to *ab* - 1.*ab* - 1*a*²*b* - *b*)²,*a* - *b*)²*ab* - 1.*a*²*b* - *b* = *a*(4*ab* - 1) + (*a* - *b*).)

Now, since (*a* - *b*)² is symmetric in *a* and *b*, it follows that if *a*² - 1)²*ab* - 1*b*² - 1)²,*a* and *b*.

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

(*) | (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* < 4*a*² - 1.

Consider (*) modulo 4*a*: (-1)² = *m*(-1) (mod 4*a*), i.e., *m* = -1 (mod 4*a*).*m* = 4*ab*' - 1,*b*' such that *b*' < *a**b*' cannot be 0 because then *m* = -1*a*² - 1)² < 0.)*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*,*a* + *b* for which 4*ab* - 1 divides *a*² - 1)²

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

Copyright © 1996-2017 Alexander Bogomolny62055885 |