Difference between revisions of "2011 IMO Problems/Problem 5"
(→See Also) |
|||
Line 46: | Line 46: | ||
==See Also== | ==See Also== | ||
*[[2011 IMO Problems]] | *[[2011 IMO Problems]] | ||
+ | |||
+ | {{IMO box|year=2011|num-b=4|num-a=6}} |
Latest revision as of 01:21, 19 November 2023
Let be a function from the set of integers to the set of positive integers. Suppose that, for any two integers
and
, the difference
is divisible by
. Prove that, for all integers
and
with
, the number
is divisible by
.
Solution
Solution 1
Let be a function from the set of integers to the set of positive integers. Suppose that, for any two integers
and
, the difference
is divisible by
. Prove that, for all integers
and
with
, the number
is divisible by
.
Solution 2
We first note the following facts:
for all
: Since
.
for all
: Since
, we get
from above. This holds for all
, so
for all
.
for all
. Because of the the above observations, we need to show this only for
. When
, this is clearly true. We now use induction, along with the observation that
, so that
.
- If
, then
. We have from the hypotheses that
which implies that
and therefore
(here we used the last observation).
From the first three observations, we get the following lemma:
Lemma 1: Suppose , and
. If
divides
, then
.
Proof: Let . Using the second observation above, we get that
Now, since
, we get that
(from the third observation above), and hence
. Since
as well, and the range of
is positive integers, equation (1) can hold only if
. But
, so
, as required.
We can now complete the proof. Notice that because of the first and
second observations above, we can assume without loss of generality
that . So, let
be positive integers, and let
. We now show that if
then
, and hence
.
By the Euclidean algorithm, there exist positive
integers and
such that
. Notice that
divides both
and
. We now have two cases:
Case 1: . In this case, by Lemma 1,
, and hence by the third and fourth observations above,
which implies that
. This immediately implies
by the third observation above, since
.
Case 2: . In this case, by Lemma 1,
, and hence by the third and fourth observations above
. However,
divides both
and
, so by the third observation above, we get that
and
. Thus, using the fact that
, we get
and hence
.
--Mahamaya 20:05, 21 May 2012 (EDT)
See Also
2011 IMO (Problems) • Resources | ||
Preceded by Problem 4 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 6 |
All IMO Problems and Solutions |