1983 IMO Problems/Problem 3
Problem
Let ,
and
be positive integers, no two of which have a common divisor greater than
. Show that
is the largest integer which cannot be expressed in the form
, where
,
and
are non-negative integers.
Solution 1
First off, I prove is un-achievable. Also, assume WLOG
.
Assume , then take the equation
to give us
. By CRT and
, we take this equation mod a and mod b to give us
, and
(and using all numbers are relatively prime pairwise). Substituting this back into the original equation gives us
, contradiction (this is where the
part comes in).
Now, let , and if a solution exists where
then we are done because we can add
to
always.
Consider the set , where
and
where
.
Therefore, we get . This is the same as
after doing some simplifying. By CRT, this must hold mod a and mod b and because
. Mod
gives us
, for which a value of
obviously exists mod
, which can be chosen from the set of values we have assigned for
. Similar method shows a value of
exists mod
from the set we have given to
.
Now, we already know that . Also, the LHS of the equation
is at least
, therefore
and we are done.
This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [1]
Solution 2
First we will prove is unattainable, as such:
Suppose
. Then, taking this mod
, we have that
, so
, and
. Similarly,
, and
, so
,
, and
. Thus,
, so
, which is a contradiction.
Now we will prove all is attainable, as such: consider the integer
such that
and
. Rearranging the equation
yields
, so set
. We see that
, so
is a positive integer (obviously
. Now, note that since
, we have that
, so
. Thus,
so
, so by Chicken Mc-Nugget theorem, there exist
that satisfy the equation and are now done.
This solution was posted and copyrighted by Stormersyle. The original thread for this problem can be found here: [2]
1983 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |