# IMO 2011: Prove that, for all integers $m$ and $n$ with $f(m)<f(n)$, the number $f(n)$ is divisible by $f(m)$

Problem: 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), the number $$f(n)$$ is divisible by $$f(m).$$ (Resource: IMO $$2011$$)

My method:

$$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z}$$

If $$f(m)=f(n)$$ , $$\frac{f(n)}{f(m)}=1\in \mathbb {Z^{+}}$$

I can accept $$f(n)>f(m)$$.

It is obvious, $$f(n)-f(m)≥f(m-n)$$

$$\begin{cases} m \mapsto m & \\ n \mapsto m-n& \end{cases} \Rightarrow \begin{cases} f(m) \mapsto f(m) & \\ f(n) \mapsto f(m-n) & \end{cases}$$

Now, I will prove that $$f(m-n)=f(m)$$ must be.

It is obvious $$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z} \Rightarrow \frac {f(m)-f(m-n)}{f(n)}\in\mathbb{Z}$$

If $$f(m)≠f(m-n)$$, we can write $$\mid f(m)-f(m-n) \mid ≥f(n)$$. Considering $$f(m)>0 , f(m-n)>0$$ and $$f(n)>f(m)$$ we get $$f(m-n)>f(m)$$ must be.

Case $$1.$$

$$f(m-n)-f(m)≥f(n)$$

Case $$2.$$

$$f(m)=f(m-n)$$

Let $$n=0$$, for Case $$1$$, we can write $$f(n)≤f(m-n)-f(m) \Rightarrow f(0)≤0$$ But, this is a contradiction. Because, $$E(f)>0$$. So, we get, if $$f(n)>f(m)$$ then $$f(m)=f(m-n)$$ must be.

Finally,

$$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z} \Rightarrow \frac {f(m)-f(n)}{f(m)}\in\mathbb{Z} \Rightarrow \frac {f(n)}{f(m)} \in \mathbb{Z^{+}}$$ Q.E.D.

Can You verify my solution? Because, I'm not so sure. I don't have a teacher to approve the solution.

• You are given that $f : \mathbb{Z} \to \mathbb{N}$ is a function such that for any two integers $m$ and $n$, $$\frac{f(m)−f(n)}{f(m−n)} \in \mathbb{Z}\tag{1}$$ What does this imply about $f(0)$? About $f(1)$? About $f(2)$? About the relationship between $f(k)$ and $f(-k)$? Are there any functions $f: \mathbb{Z} \to \mathbb{N}$ that satisfy $(1)$ that are not constant? Oct 13, 2018 at 17:24
• @Zubin Mukerjee There is not a problem in the question. But, maybe there is a problem in my solution. Oct 13, 2018 at 17:33

Your proof looks correct to me.

Now, I will prove that $$f(m-n)≥f(m)$$ must be.

I think that you have a typo here. It should be $$f(m-n)=f(m)$$.

It is obvious $$\frac {f(m)-f(n)}{f(m-n)}\in\mathbb{Z} \Rightarrow \frac {f(m)-f(m-n)}{f(n)}\in\mathbb{Z}$$

Yes, $$f(m)-f(m-n)$$ is divisible by $$f(m-(m-n))=f(n)$$.

If $$f(m)≠f(m-n)$$, we can write $$\mid f(m)-f(m-n) \mid ≥f(n)$$. Considering $$f(m)>0$$ and $$f(m-n)>0$$, we get $$f(m-n)>f(m)$$ must be. Because, $$f(n)>f(m).$$

Case $$1.$$

$$f(m-n)-f(m)≥f(n)$$

Case $$2.$$

$$f(m)=f(m-n)$$ Let $$n=0$$, for Case $$1$$, we can write $$f(n)≤f(m-n)-f(m) \Rightarrow f(0)≤0$$ But, this is a contradiction. Because, $$E(f)>0$$. So, case $$1$$ is impossible.

I think there is no need to separate it into cases as follows :

"Suppose that $$f(m)\not =f(m-n)$$. Then, we can write $$\mid f(m)-f(m-n) \mid \ge f(n)$$. Considering $$f(m)>0$$ and $$f(m-n)>0$$, we get $$f(m-n)>f(m)$$ because $$f(n)>f(m).$$ It follows that $$f(m-n)-f(m)\ge f(n)$$. Let $$n=0$$. Then, we can write $$f(n)≤f(m-n)-f(m) \implies f(0)≤0$$ which contradicts $$f(0)\gt 0$$. So, we have $$f(m)=f(m-n)$$."

Another way to prove $$f(m-n)=f(m)$$.

We have $$-f(n)\lt f(m)-f(n)\le -f(m-n)\lt 0$$ from which $$0\lt f(m-n)\lt f(n)$$ follows.

From $$f(m)-f(m-n)\lt f(m)+f(m-n)\le f(n)$$ and $$f(m-n)\lt f(n)\lt f(n)+f(m)\implies -f(n)\lt f(m)-f(m-n)$$ we get $$-f(n)\lt f(m)-f(m-n)\lt f(n)$$

Since $$f(m)-f(m-n)$$ is divisible by $$f(m-(m-n))=f(n)$$, we get $$f(m)-f(m-n)=0$$.