IMO 2011 · 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)\le f(n)\), the number \(f(n)\) is divisible by \(f(m)\).

Official text of the problem. Official problem paper (PDF)

Solution

Fix integers \(m,n\) with \(f(m)\le f(n)\). If \(f(m)=f(n)\), the conclusion is immediate. Otherwise, write \[ a=f(m),\qquad b=f(n),\qquad d=f(m-n), \] so that \(0<a<b\).

The hypothesis gives \(d\mid b-a\). Since \(b-a\) is positive, \[ 0<d\le b-a<b. \] Applying the hypothesis to the two integers \(m\) and \(m-n\), we also obtain \[ f\bigl(m-(m-n)\bigr)\mid f(m)-f(m-n), \] that is, \[ b\mid a-d. \] But \(0<a<b\) and \(0<d<b\), so \(\lvert a-d\rvert<b\). The only multiple of \(b\) with absolute value less than \(b\) is zero; hence \(a=d\).

Therefore \(a\mid b-a\), which implies \(a\mid b\). Thus \(f(m)\mid f(n)\), as required. \(\square\)

The solution was checked against the official IMO shortlist solutions.