# Difference between revisions of "2011 IMO Problems/Problem 5"

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m - n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$.

## Solution

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m - n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$.

## Solution

We first note the following facts:

1. $f(m)|f(0)$ for all $m \in \mathbb{Z}$: Since $f(m) |( f(m) - f(0))$.
2. $f(m) = f(-m)$ for all $m \in \mathbb{Z}$: Since $f(m) | (f(0) - f(-m))$, we get $f(m) | f(-m)$ from above. This holds for all $m$, so $f(m) = f(-m)$ for all $m$.
3. $f(m)|f(km)$ for all $k \in \mathbb{Z}$. Because of the the above observations, we need to show this only for $k > 0$. When $k = 1$, this is clearly true. We now use induction, along with the observation that $f(m)|(f((k+1)m) - f(km))$, so that $f(m)|f(km) \implies f(m)|f((k+1)m)$.
4. If $f(a) | f(ax + b)$, then $f(a) | f(b)$. We have from the hypotheses that $f(ax)|(f(ax+b)-f(b))$ which implies that $f(a)|(f(ax + b) - f(b))$ and therefore $f(a) | f(b)$ (here we used the last observation).

From the first three observations, we get the following lemma:

Lemma 1: Suppose $m \neq n$, and $f(m) \leq f(n)$. If $|n-m|$ divides $n$, then $f(m) | f(n)$.

Proof: Let $d = |n-m|$. Using the second observation above, we get that $$f(n)|(f(d) - f(m))\;\;\;\;\;\;(1)$$. Now, since $d|n$, we get that $f(d) | f(n)$ (from the third observation above), and hence $f(d) \leq f(n)$. Since $f(m) \leq f(n)$ as well, and the range of $f$ is positive integers, equation (1) can hold only if $f(m) = f(d)$. But $f(d) | f(n)$, so $f(m) | f(n)$, 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 $m, n > 0$. So, let $m,n$ be positive integers, and let $g = {\rm gcd (n, m)}$. We now show that if $f(m) \leq f(n)$ then $f(m)|f(g)$, and hence $f(m) | f(n)$.

By the Euclidean algorithm, there exist positive integers $x$ and $y$ such that $mx = ny + g$. Notice that $g = mx - ny$ divides both $mx$ and $ny$. We now have two cases:

Case 1: $f(mx) \leq f(ny)$. In this case, by Lemma 1, $f(mx) | f(ny)$, and hence by the third and fourth observations above, $f(m) | f(mx - g)$ which implies that $f(m) | f(g)$. This immediately implies $f(m) | f(n)$ by the third observation above, since $g | n$.

Case 2: $f(mx) > f(ny)$. In this case, by Lemma 1, $f(ny) | f(mx)$, and hence by the third and fourth observations above $f(n) | f(g)$. However, $g$ divides both $m$ and $n$, so by the third observation above, we get that $f(g)|f(n)$ and $f(g)|f(m)$. Thus, using the fact that $f(m) \leq f(n)$, we get $f(g) = f(m) = g(n)$ and hence $f(m) | f(n)$.