IMO Problem Shortlist

Assume that there are only finitely many primes $p_1,p_2,\dots ,p_m$ that divide some function value produced of $f$. There are infinitely many positive integers $a$ such that $v_{p_i}(a)>v_{p_i}(f(1))$ for all $i=1,2,\dots ,m$, e.g. $a={\left(p_1{p}_2\dots p_m\right)}^{\alpha }$ with $\alpha$ sufficiently large. Pick any such $a$. The condition of the problem then yields $a\mid (f(a+1)-f(1))$. Assume $f(a+1)\ne f(1)$. Then we must have $v_{p_i}(f(a+1))\ne v_{p_i}(f(1))$ for at least one $i$. This yields $v_{p_i}(f(a+1)-f(1))=\min \left\{v_{p_i}(f(a+1)),v_{p_i}(f(1))\right\}\le v_{p_1}(f(1))<v_{p_i}(a)$. But this contradicts the fact that $a\mid (f(a+1)-f(1))$. Hence we must have $f(a+1)=f(1)$ for all such $a$. Now, for any positive integer $b$ and all such $a$, we have $(a+1-b)\mid (f(a+1)-f(b))$, i.e., $(a+1-b)\mid (f(1)-f(b))$. Since this is true for infinitely many positive integers $a$ we must have $f(b)=f(1)$. Hence $f$ is a constant function, a contradiction. Therefore, our initial assumption was false and there are indeed infinitely many primes $p$ dividing $f(c)$ for some positive integer $c$.

---

Alternative solution.

Assume that there are only finitely many primes $p_1,p_2,\dots ,p_m$ that divide some function value of $f$. Since $f$ is not identically $1$, we must have $m\ge 1$. Then there exist non-negative integers ${\alpha }_1,\dots ,{\alpha }_m$ such that $$f(1)=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_m^{{\alpha }_m}$$ We can pick a positive integer $r$ such that $f(r)\ne f(1)$. Let $$M=1+p_1^{{\alpha }_1+1}{p}_2^{{\alpha }_2+1}\dots p_m^{{\alpha }_m+1}\cdot (f(r)+r)$$ Then for all $i\in \{1,\dots ,m\}$ we have that $p_i^{{\alpha }_i+1}$ divides $M-1$ and hence by the condition of the problem also $f(M)-f(1)$. This implies that $f(M)$ is divisible by $p_i^{{\alpha }_i}$ but not by $p_i^{{\alpha }_i+1}$ for all $i$ and therefore $f(M)=f(1)$. Hence $$\begin{array}{rl}M-r& >p_1^{{\alpha }_1+1}{p}_2^{{\alpha }_2+1}\dots p_m^{{\alpha }_m+1}\cdot (f(r)+r)-r\\ & \ge p_1^{{\alpha }_1+1}{p}_2^{{\alpha }_2+1}\dots p_m^{{\alpha }_m+1}+(f(r)+r)-r\\ & >p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_m^{{\alpha }_m}+f(r)\\ & \ge |f(M)-f(r)|\end{array}$$ But since $M-r$ divides $f(M)-f(r)$ this can only be true if $f(r)=f(M)=f(1)$, which contradicts the choice of $r$.