United States — Team Selection Test, 2010

Write
$$P(x) = a_{r}x^{r} + a_{r-1}x^{r-1} + \dots + a_{1}x,$$
and consider its formal derivative
$$Q(x) = r a_{r} x^{r-1} + (r-1) a_{r-1} x^{r-2} + \dots + a_{1}.$$
Since $P$ is not identically zero, neither is $Q$, so we may choose some positive integer $m$ such that $Q(m) \neq 0$. We claim that we may take $n$ to be any prime that does not divide $Q(m)$.
Let $n$ be such a prime, and put
$$d = \text{gcd}(P(n) - P(0), P(n+1) - P(1), P(n+2) - P(2), \dots).$$
Certainly we have $n \mid d$. On the other hand, if $q$ is any prime distinct from $n$, then we cannot have $q \mid d$. For suppose that $q \mid d$. Since $q$ and $n$ are relatively prime, there are integers $k, l > 0$ such that $kn - lq = 1$. Then, notice that
$$P(m) \equiv P(m+n) \equiv P(m+2n) \equiv \dots \equiv P(m+kn) \equiv P(m+1) \pmod{q}$$
for every nonnegative integer $m$. By induction, then, $q$ divides all of $P(0), P(1), P(2), \dots$, contradicting the given.
Also, we cannot have $n^2 \mid d$. Indeed,
$$\begin{aligned} P(m+n) - P(m) &= \sum_{i=1}^{r} a_i [(m+n)^i - m^i] \\ &= \sum_{i=1}^{r} a_i [m^i + i m^{i-1} n + (\text{terms divisible by } n^2) - m^i] \\ &= \sum_{i=1}^{r} a_i [i m^{i-1} n + (\text{terms divisible by } n^2)] \\ &\equiv n \cdot Q(m) \pmod{n^2}. \end{aligned}$$
Therefore, $P(m+n) - P(m)$ cannot be divisible by $n^2$ since $Q(m)$ is not divisible by $n$.

So $d$ is divisible by $n$, but not by any other prime or by $n^2$; hence $d = n$, as required.