2011 IMO Problems/Problem 5
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 which implies that and therefore .
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 .