Problem 1086

Let $n \geqslant 1$. For any integer $m \geqslant 1$, each of the two sets

$$\{f(m+1), \ldots, f(m+f(n))\} \text { and }\{f(m+2), \ldots, f(m+1+f(n))\}$$

contains exactly one integer divisible by $n$. Thus, if $n \mid f(m+1)$, none of the integers $f(m+2), \ldots, f(m+f(n))$ is divisible by $n$, so $n$ divides $f(m+1+f(n))$. Similarly, if $n$ does not divide $f(m+1)$, $n$ divides one of the integers $f(m+2), \ldots, f(m+f(n))$, so $n$ does not divide $f(m+1+f(n))$. In conclusion, for any integer $m \geqslant 2$, $n$ divides $f(m)$ if and only if $n$ divides $f(m+f(n))$. This means that for any pair of integers $(x, y)$ greater than or equal to $2$, $n$ divides $f(x)$ and $f(y)$ if and only if $f(n)$ divides $x-y$.

Now let $k \geqslant 1$ be an integer and $x$ an integer such that $k n \mid f(x)$. Then $k n$ also divides $f(x+f(k n))$, so $n$ divides $f(x)$ and $f(x+f(k n))$. It follows that $f(n)$ divides $f(k n)$ for any integer $k \geqslant 1$.

In particular, $f(n)$ divides $f(n)$ and $f(2 n)$, so $f(f(n))$ divides $2 n - n = n$. Notice that if $n$ divides $f(n)$, then there exists an integer $k$ such that $f(n) = k n$. But then $f(k n) = f(f(n)) \mid n \mid f(n) \mid f(k n)$, so $f(k n) = f(n)$, hence $n \mid f(n) = f(k n) = f(f(n)) \mid n$ and $f(n) = n$. Thus, it suffices to find integers $n$ such that $f(n) = n$.

On the other hand, since $f(f(n))$ divides $n$, we have in particular for any prime number, $f(f(p))$ divides $p$, so $f(f(p)) \in \{1, p\}$. Suppose $x$ is such that $f(x) = 1$. Then for any integer $m \geqslant 1$, the set $\{f(m+1), \ldots, f(m+f(x))\}$ is reduced to $\{f(m+1)\}$, so $x$ divides $f(m+1)$ for all $m$. In particular, $x$ divides $f(x) = 1$, so $x = 1$. Thus, $f(p) \neq 1$ and $f(f(p)) \neq 1$, so $f(f(p)) = p$ for all prime numbers $p$.

If $p$ divides $f(p)$ for infinitely many prime numbers $p$, then according to the previous discussion, $f(p) = p$ for infinitely many prime numbers, which gives the desired result. Otherwise, for all sufficiently large prime numbers $p$, $f(p)$ and $p$ are coprime. We then have $f(p) \mid f(p f(p))$ and $p = f(f(p)) \mid f(p f(p))$, so $p f(p) \mid f(p f(p))$ and $f(p f(p)) = p f(p)$.

It remains to see that $p f(p)$ can take infinitely many different values. For this, we assume that we have constructed $k$ different integers of the form $p f(p)$ and we choose $q$ a prime number strictly larger than these $k$ integers. Then $q f(q)$ is indeed a distinct integer from the previous $k$.

Thus, $f$ has infinitely many fixed points.