56th International Mathematical Olympiad Shortlisted Problems

Answer. $f(x)=ax+b$, where $b$ is an arbitrary integer, and $a$ is an arbitrary positive integer with $\mho (a)=0$.

A straightforward check shows that all the functions listed in the answer satisfy the problem condition. It remains to show the converse.

Assume that $f$ is a function satisfying the problem condition. Notice that the function $g(x)=f(x)-f(0)$ also satisfies this condition. Replacing $f$ by $g$, we assume from now on that $f(0)=0$; then $f(n)>0$ for any positive integer $n$. Thus, we aim to prove that there exists a positive integer $a$ with $\mho (a)=0$ such that $f(n)=an$ for all $n\in \mathbb{Z}$.

We start by introducing some notation. Set $N=10^{100}$. We say that a prime $p$ is large if $p>N$, and $p$ is small otherwise; let $\mathcal{S}$ be the set of all small primes. Next, we say that a positive integer is large or small if all its prime factors are such (thus, the number 1 is the unique number which is both large and small). For a positive integer $k$, we denote the greatest large divisor of $k$ and the greatest small divisor of $k$ by $L(k)$ and $S(k)$, respectively; thus, $k=L(k)S(k)$.

We split the proof into three steps.

Step 1. We prove that for every large $k$, we have $k|f(a)-f(b)⟺k|a-b$. In other words, $L(f(a)-f(b))=L(a-b)$ for all integers $a$ and $b$ with $a>b$.

We use induction on $k$. The base case $k=1$ is trivial. For the induction step, assume that $k_0$ is a large number, and that the statement holds for all large numbers $k$ with $k<k_0$.

Claim 1. For any integers $x$ and $y$ with $0<x-y<k_0$, the number $k_0$ does not divide $f(x)-f(y)$.

Proof. Assume, to the contrary, that $k_0\mid f(x)-f(y)$. Let $\ell =L(x-y)$; then $\ell ⩽x-y<k_0$. By the induction hypothesis, $\ell \mid f(x)-f(y)$, and thus $\mathrm{lcm}\left(k_0,\ell \right)\mid f(x)-f(y)$. Notice that $\mathrm{lcm}\left(k_0,\ell \right)$ is large, and $\mathrm{lcm}\left(k_0,\ell \right)⩾k_0>\ell$. But then $$\mho (f(x)-f(y))⩾\mho \left(\mathrm{lcm}\left(k_0,\ell \right)\right)>\mho (\ell )=\mho (x-y)$$ which is impossible.

Now we complete the induction step. By Claim 1, for every integer $a$ each of the sequences $$f(a),f(a+1),\dots ,f\left(a+k_0-1\right)\text{ and }f(a+1),f(a+2),\dots ,f\left(a+k_0\right)$$ forms a complete residue system modulo $k_0$. This yields $f(a)\equiv f\left(a+k_0\right)\left(\mathrm{mod}{k}_0\right)$. Thus, $f(a)\equiv f(b)\left(\mathrm{mod}{k}_0\right)$ whenever $a\equiv b\left(\mathrm{mod}{k}_0\right)$.

Finally, if $a\not\equiv b\left(\mathrm{mod}{k}_0\right)$ then there exists an integer $b^{\prime }$ such that $b^{\prime }\equiv b\left(\mathrm{mod}{k}_0\right)$ and $\left|a-b^{\prime }\right|<k_0$. Then $f(b)\equiv f\left(b^{\prime }\right)\not\equiv f(a)\left(\mathrm{mod}{k}_0\right)$. The induction step is proved.

Step 2. We prove that for some small integer a there exist infinitely many integers $n$ such that $f(n)=an$. In other words, $f$ is linear on some infinite set.

We start with the following general statement.

Claim 2. There exists a constant $c$ such that $f(t)<ct$ for every positive integer $t>N$.

Proof. Let $d$ be the product of all small primes, and let $\alpha$ be a positive integer such that $2^{\alpha }>f(N)$. Then, for every $p\in \mathcal{S}$ the numbers $f(0),f(1),\dots ,f(N)$ are distinct modulo $p^{\alpha }$. Set $P=d^{\alpha }$ and $c=P+f(N)$.

Choose any integer $t>N$. Due to the choice of $\alpha$, for every $p\in \mathcal{S}$ there exists at most one nonnegative integer $i⩽N$ with $p^{\alpha }\mid f(t)-f(i)$. Since $|\mathcal{S}|<N$, we can choose a nonnegative integer $j⩽N$ such that $p^{\alpha }\nmid f(t)-f(j)$ for all $p\in \mathcal{S}$. Therefore, $S(f(t)-f(j))<P$.

On the other hand, Step 1 shows that $L(f(t)-f(j))=L(t-j)⩽t-j$. Since $0⩽j⩽N$, this yields $$f(t)=f(j)+L(f(t)-f(j))\cdot S(f(t)-f(j))<f(N)+(t-j)P⩽(P+f(N))t=ct$$

Now let $\mathcal{T}$ be the set of large primes. For every $t\in \mathcal{T}$, Step 1 implies $L(f(t))=t$, so the ratio $f(t)/t$ is an integer. Now Claim 2 leaves us with only finitely many choices for this ratio, which means that there exists an infinite subset ${\mathcal{T}}^{\prime }\subseteq \mathcal{T}$ and a positive integer a such that $f(t)=at$ for all $t\in {\mathcal{T}}^{\prime }$, as required.

Since $L(t)=L(f(t))=L(a)L(t)$ for all $t\in {\mathcal{T}}^{\prime }$, we get $L(a)=1$, so the number $a$ is small.

Step 3. We show that $f(x)=ax$ for all $x\in \mathbb{Z}$.

Let $R_i=\{x\in \mathbb{Z}:x\equiv i(\mathrm{mod}N!)\}$ denote the residue class of $i$ modulo $N!$.

Claim 3. Assume that for some $r$, there are infinitely many $n\in R_r$ such that $f(n)=an$. Then $f(x)=ax$ for all $x\in R_{r+1}$.

Proof. Choose any $x\in R_{r+1}$. By our assumption, we can select $n\in R_r$ such that $f(n)=an$ and $|n-x|>|f(x)-ax|$. Since $n-x\equiv r-(r+1)=-1(\mathrm{mod}N!)$, the number $|n-x|$ is large. Therefore, by Step 1 we have $f(x)\equiv f(n)=an\equiv ax(\mathrm{mod}n-x)$, so $n-x\mid f(x)-ax$. Due to the choice of $n$, this yields $f(x)=ax$.

To complete Step 3, notice that the set ${\mathcal{T}}^{\prime }$ found in Step 2 contains infinitely many elements of some residue class $R_i$. Applying Claim 3, we successively obtain that $f(x)=ax$ for all $x\in R_{i+1},R_{i+2},\dots ,R_{i+N!}=R_i$. This finishes the solution.