Difference between revisions of "2011 IMO Problems/Problem 5"
(Added Solution) |
(Removed typos) |
||
Line 12: | Line 12: | ||
# <math>f(m) = f(-m)</math> for all <math>m \in \mathbb{Z}</math>: Since <math>f(m) | (f(0) - f(-m))</math>, we get <math>f(m) | f(-m)</math> from above. This holds for all <math>m</math>, so <math>f(m) = f(-m)</math> for all <math>m</math>. | # <math>f(m) = f(-m)</math> for all <math>m \in \mathbb{Z}</math>: Since <math>f(m) | (f(0) - f(-m))</math>, we get <math>f(m) | f(-m)</math> from above. This holds for all <math>m</math>, so <math>f(m) = f(-m)</math> for all <math>m</math>. | ||
# <math>f(m)|f(km)</math> for all <math>k \in \mathbb{Z}</math>. Because of the the above observations, we need to show this only for <math>k > 0</math>. When <math>k = 1</math>, this is clearly true. We now use induction, along with the observation that <math>f(m)|(f((k+1)m) - f(km))</math>, so that <math>f(m)|f(km) \implies f(m)|f((k+1)m)</math>. | # <math>f(m)|f(km)</math> for all <math>k \in \mathbb{Z}</math>. Because of the the above observations, we need to show this only for <math>k > 0</math>. When <math>k = 1</math>, this is clearly true. We now use induction, along with the observation that <math>f(m)|(f((k+1)m) - f(km))</math>, so that <math>f(m)|f(km) \implies f(m)|f((k+1)m)</math>. | ||
− | # If <math>f(a) | f(ax + b)</math>, then <math>f(a) | f(b)</math>. We have <math>f(ax)| | + | # If <math>f(a) | f(ax + b)</math>, then <math>f(a) | f(b)</math>. We have from the hypotheses that <math>f(ax)|(f(ax+b)-f(b))</math> which implies that <math>f(a)|(f(ax + b) - f(b))</math> and therefore <math>f(a) | f(b)</math> (here we used the last observation). |
Line 25: | Line 25: | ||
second observations above, we can assume without loss of generality | second observations above, we can assume without loss of generality | ||
that <math>m, n > 0</math>. So, let <math>m,n</math> be positive integers, and let <math>g = | that <math>m, n > 0</math>. So, let <math>m,n</math> be positive integers, and let <math>g = | ||
− | {\rm gcd n, m}</math>. We now show that if <math>f(m) \leq f(n)</math> then | + | {\rm gcd (n, m)}</math>. We now show that if <math>f(m) \leq f(n)</math> then |
<math>f(m)|f(g)</math>, and hence <math>f(m) | f(n)</math>. | <math>f(m)|f(g)</math>, and hence <math>f(m) | f(n)</math>. | ||
Revision as of 18:39, 21 May 2012
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
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
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
.