APMO, 2025

Let $a_{0}=P(0) \neq 0$ be the independent coefficient, i.e., the constant term of $P(x)$. Then there are infinitely many primes $p$ such that $p$ divides $P(k)$ but $p$ does not divide $k$. In fact, since $P(k)-a_{0}$ is a multiple of $k$, $\operatorname{gcd}(P(k), k)=\operatorname{gcd}\left(k, a_{0}\right) \leq a_{0}$ is bounded, so pick, say, $k$ with prime factors each larger than $a_{0}$.

Since $P(k)$ divides $a_{i+k}-a_{i}$, $p$ divides $a_{i+k}-a_{i}$. Moreover, since $P(k+p) \equiv P(k) \equiv 0 (\bmod p)$, $p$ also divides $a_{i+k+p}-a_{i}$. Therefore, $a_{i} \bmod p$ is periodic with periods $k+p$ and $k$. By Bezout's theorem, $\operatorname{gcd}(k+p, k)=1$ is also a period, that is, $p$ divides $a_{i+1}-a_{i}$ for all $i$ and $p$ such that $p \mid P(k)$ and $p \nmid k$ for some $k$. Since there are infinitely many such primes $p$, $a_{i+1}-a_{i}$ is divisible by infinitely many primes, which implies $a_{i+1}=a_{i}$, that is, the sequence is constant.