2009 IMO Problems/Problem 1
Contents
Problem
Let be a positive integer and let
be distinct integers in the set
such that
divides
for
. Prove that
doesn't divide
.
Author: Ross Atkins, Australia
Solution
Let such that
and
. Suppose
divides
.
Note
implies
and hence
. Similarly one has
for all
's, in particular,
and
force
. Now
gives
, similarly one has
for all
's, that is
's satisfy
and
, but there should be at most one such integer satisfies them within the range of
for
and
. A contradiction!!!
Solution 2
Let . Then after toying around with the
and what they divide, we have that
, and so in particular,
.
Assume by way of contradiction that . Then
. Now we shift our view towards the
. Here each
divides
. Hence we have the chain of equivalences
. Now we also have that
. Thus
. Now plugging this value of
modulo
, we obtain that
. Hence this chain of congruences is also true for
as
was arbitrary. However as all the
we have that not all the
are distinct, and so this is a contradiction.
See Also
2009 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |