orl wrote:

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).$

Proposed by Mahyar Sefidgaran, Iran

Nice problem.

We use the facts: $a,b\in\mathbb{N}a|b\implies b\ge a$ and $a|b\pm a\implies a|b$ .

First let's prove that $f$ is an even function.
Set $n=0$ giving that $f(m)|f(m)-f(0)\implies f(m)|f(0)\forall m$ . Setting $m=0$ , we get $f(-n)|f(n)$ and since $f$ is defined for all integers, it is symmetric for $n$ and $-n$ implying $f(-n)=f(n)$
Then expand using $m+n=m-(-n)$ to note that $f(m+n)|f(m)-f(n)$ . Since the co-domain of $f$ is $\mathbb{N}$ we have three cases.

Case 1:
$f(m)-f(n)\ge f(m+n)$ . But we have $f(m)=f(m+n-n)|f(m+n)-f(n)$ giving $f(m)-f(n)\ge f(m+n)\ge f(m)+f(n)$ $\implies f(m)+f(n)\le f(m)-f(n)\implies 2f(n)\le 0$ , contradiction since $f(m)\in\mathbb{N}$ .

Case 2:
$f(m)\le f(n)-f(m+n)$ which is almost similar using the given fact $f(n)\ge f(m)$ and not possible.

Case 3:
$f(m+n)=f(m)$ holds as the only possibility.
Then $f(m)|f(m+n)-f(m)=f(n)-f(m)\implies f(m)|f(n)$ .
We are done.

Edit: Since most solutions use the same idea, I was thinking to solve this using induction. Is it possible with induction? Also, may be in the cases I have reversed the order of $m$ and $n$ .