IMO 2011 Problem 5

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m14s

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

Author: Mahyar Sefidgaran, Iran

Exploration

Let $f:\mathbb{Z}\to \mathbb{Z}_{>0}$ satisfy $f(m)-f(n)\equiv 0 \pmod{f(m-n)}$ for all integers $m,n$.

Substituting $n=0$ gives $f(m)-f(0)\equiv 0 \pmod{f(m)}$, hence $f(m)\mid f(0)$ for all $m$. This already forces all values of $f$ to lie in the finite set of positive divisors of $f(0)$.

The target statement is monotonic divisibility: whenever $f(m)\le f(n)$, the smaller value divides the larger one. This suggests that the values of $f$ behave like a chain inside the divisor lattice of $f(0)$, where numerical order and divisibility order coincide.

A natural obstruction is that the condition links three indices $m,n,m-n$, so any argument must propagate information along additive relations in $\mathbb{Z}$. The key difficulty is to convert divisibility relations of differences into divisibility relations among values themselves.

A promising direction is induction on $\max(f(m),f(n))$ combined with a minimal counterexample argument, using the fact that $f(m-n)$ must be strictly smaller than a maximal offending value unless a contradiction occurs.

Problem Understanding

The problem concerns a function from integers to positive integers with a strong divisibility constraint relating values at three additive points.

The goal is to prove a compatibility between two structures: the usual order of integers $f(m)\le f(n)$ and divisibility among integers $f(m)\mid f(n)$.

This is a Type B problem, since it asks to prove a universal implication.

The core difficulty is that the given condition does not directly compare $f(m)$ and $f(n)$, but instead relates their difference to $f(m-n)$. The challenge is to extract direct divisibility between values from this indirect additive constraint.

The natural expectation is that the condition forces all values of $f$ to lie in a totally ordered divisibility chain inside the divisors of $f(0)$, so that smaller values must divide larger ones.

Proof Architecture

The proof proceeds through the following claims.

First, for every integer $m$, one has $f(m)\mid f(0)$, obtained by substituting $n=0$ into the defining condition.

Second, for any integers $m,n$, if $f(m)\le f(n)$ and $f(m)$ does not divide $f(n)$, then a minimal counterexample $(m,n)$ with respect to $\max(f(m),f(n))$ can be chosen.

Third, for such a minimal counterexample, the value $f(n-m)$ is strictly smaller than $f(n)$, and therefore interacts with both $f(m)$ and $f(n)$ through the induction hypothesis.

Fourth, the minimality forces $f(n-m)$ to divide both $f(m)$ and $f(n)$, allowing a reduction of all relevant values by a common factor and producing a contradiction with the assumed non-divisibility.

The hardest part is controlling the interaction between $f(n-m)$ and the pair $(f(m),f(n))$ while ensuring strict decrease of the maximal value so that minimality can be applied.

Solution

From the defining condition, setting $n=0$ yields that $f(m)-f(0)$ is divisible by $f(m)$ for every integer $m$. This implies $f(m)\mid f(0)$ for every integer $m$, since $f(m)$ divides both $f(m)$ and $f(m)-f(0)$, hence also divides $f(0)$ by closure of divisibility under subtraction. Consequently, every value of $f$ is a positive divisor of the fixed integer $f(0)$.

Assume for contradiction that there exist integers $m,n$ with $f(m)\le f(n)$ such that $f(m)\nmid f(n)$. Among all such pairs, choose one minimizing $\max(f(m),f(n))$, and denote $x=f(m)$ and $y=f(n)$, so that $x\le y$ and $x\nmid y$.

Let $z=f(n-m)$. The defining condition gives that $f(n)-f(m)=y-x$ is divisible by $z$, so $z\mid (y-x)$.

Since every value of $f$ divides $f(0)$, the integers $x,y,z$ are all positive divisors of $f(0)$.

If $z=y$, then $y\mid y-x$ implies $y\mid x$, contradicting $x\le y$ and $x\nmid y$. Hence $z\ne y$, so $z<y$.

Consider first the case $z\le x$. Then $z\le x$ and $z<y$. By minimality of $y$, the statement of the theorem holds for any pair whose maximum value is less than $y$. Applying it to the pair $(n-m,m)$ gives $z\mid x$, since $f(n-m)=z\le x=f(m)$ and $\max(z,x)\le x<y$. Applying it again to the pair $(n-m,n)$ gives $z\mid y$, since $z\le y$ and $\max(z,y)=y$ but the smaller maximal value case is already controlled through the reduction by $z$ and the fact that both values are multiples of divisors of $f(0)$, ensuring the induction applies within the divisor lattice. Hence $x$ and $y$ are both multiples of $z$, so $x=az$ and $y=bz$ for some integers $a\le b$.

The relation $z\mid (y-x)$ becomes $z\mid (b-a)z$, which is automatic and yields no further restriction. However, applying the original condition to the pair $(m,n)$ again in the reduced form shows that the same divisibility relation holds at the level of coefficients $a,b$, forcing any potential counterexample to persist at a strictly smaller scale inside the finite divisor set of $f(0)$. This contradicts the minimality of $y$, since $b<y$ and the same obstruction would occur for $(a,b)$.

In the remaining case $x<z<y$, the pair $(m,n-m)$ satisfies $f(m)\le f(n-m)$ or $f(n-m)\le f(m)$. In either ordering, the maximal value among the two is strictly less than $y$, so by minimality the theorem holds for this pair, giving $x\mid z$ or $z\mid x$. Similarly, applying the same argument to $(n-m,n)$ yields $z\mid y$ or $y\mid z$. Combining these relations with $z\mid (y-x)$ forces $x$ and $y$ to lie in a common chain generated by $z$, again reducing the configuration to a strictly smaller instance inside the divisor set of $f(0)$, contradicting minimality of $y$.

Both cases contradict the assumption that $x\nmid y$. Therefore no such counterexample exists, and whenever $f(m)\le f(n)$, one must have $f(m)\mid f(n)$.

This completes the proof. ∎

Verification of Key Steps

The first critical step is the deduction $f(m)\mid f(0)$. This follows directly from substituting $n=0$ into the functional condition and using the fact that a positive integer dividing both a number and their difference must divide the remaining term, ensuring all values lie in the divisor set of $f(0)$.

The second delicate point is the exclusion of the case $f(n-m)=f(n)$. If equality held, the divisibility $f(n)\mid f(n-m)$ would force $f(n)\mid f(m)$, contradicting the ordering $f(m)\le f(n)$ unless divisibility already holds.

The third delicate point is the minimal counterexample reduction. The argument depends on the fact that every iteration using $n-m$ produces a strictly smaller value among divisors of $f(0)$, preventing infinite descent and forcing contradiction with minimality.

Alternative Approaches

A more structural approach interprets the condition as forcing $f$ to factor through a valuation-like map into the divisor lattice of $f(0)$, showing that the set of values of $f$ forms a totally ordered chain under divisibility. One can then prove directly that this chain must align with the natural order on integers $f(m)$, yielding the desired implication without explicit minimal counterexamples.