NMO Selection Tests for the Balkan and International Mathematical Olympiads

We claim that for every prime $p$, $f(p)=p^m$, where $m$ is a positive integer which (possibly) depends on $p$. Assume the claim for the time being. Since the degree $n$ of $f$ is positive, the claim forces $f(p)=p^n$ for sufficiently large primes $p$. Consequently, the polynomials $f$ and $X^n$ agree infinitely many times, so $f=X^n$.

Back to the claim, suppose that $f(p)=q^m$ for some distinct primes $p$ and $q$ and some positive integer $m$. Since $q^{m+1}$ divides the difference $f(p+k{q}^{m+1})-f(p)$, $k=1,2,3,\dots$, and $q^m$ divides $f(p)$ but $q^{m+1}$ does not, it follows that $q$ divides $f(p+k{q}^{m+1})$ but $q^{m+1}$ does not. Use Dirichlet's theorem to choose $k$ so large that $p+k{q}^{m+1}$ be prime and $f(p+k{q}^{m+1})>q^m$. By hypothesis, $f(p+k{q}^{m+1})$ is a power of a prime. Recall that $q$ divides $f(p+k{q}^{m+1})$ to deduce that $f(p+k{q}^{m+1})=q^r$ for some positive integer $r$. Finally, $f(p+k{q}^{m+1})>q^m$ implies $r>m$, so $q^{m+1}$ divides $f(p+k{q}^{m+1})$ – a contradiction.