2007 IMO Problems/Problem 5
Contents
Problem
(Kevin Buzzard and Edward Crane, United Kingdom)
Let and
be positive integers. Show that if
divides
, then
.
Solution
Lemma. If there is a counterexample for some value of , then there is a counterexample
for this value of
such that
.
Proof. Suppose that . Note that
, but
. It follows that
. Since
it follows that
can be written as
, with
. Then
is a counterexample for which
.
Now, suppose a counterexample exists. Let be a counterexample for which
is minimal and
. We note that
and
Now,
Thus
is a counterexample. But
, which contradicts the minimality of
. Therefore no counterexample exists.
(Sean Yu, US)
Second Solution
As , since
, we only need to show that
. We will use the Vieta Jumping technique to solve it.
Suppose there exist counterexamples, which means the set is not empty. Then there exists a pair
such that
has the minimum sum among all pairs in
. Without loss of generality, we assume
. Let
. Then
is a positive integer and
. So
is a root for the quadratic equation
. Using the Vieta Lemma, we know the equation has another root
and from
we know it is an integer. Note that since
and
, we have
, which implies
. Also
, thus
, and we get another pair
, but
, which contradicts assumption that
has the minimum sum.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
2007 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |
- <url>viewtopic.php?p=894656#p894656 Discussion on AoPS/MathLinks</url>