Divisibility and Modulo Arithmetic at IMO 2007
Here's Problem 5 from IMO 2007:
Let a and b be positive integers. Show that if |
|Contact| |Front page| |Contents| |Geometry|
Copyright © 1996-2018 Alexander BogomolnySolution
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
Now, since (a - b)² is symmetric in a and b, it follows that if
Suppose that a ≠ b. With this symmetry we may assume that
(*) | (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.,
The descending sequence argument can be simplified by choosing a and b,
|Contact| |Front page| |Contents| |Geometry|
Copyright © 1996-2018 Alexander Bogomolny71493507