USA Team Selection Test

Let $P$ be a polynomial with integer coefficients such that $P(0) = 0$ and
$$\gcd(P(0), P(1), P(2), \ldots ) = 1.$$
We need to show that there are infinitely many $n$ such that
$$\gcd(P(n) - P(0), P(n+1) - P(1), P(n+2) - P(2), \ldots) = n.$$

Consider the polynomial $P(x) = x^k Q(x)$, where $Q(0) \neq 0$. We claim that if $n = p^k$ for any prime $p$ not dividing $k Q(1) + Q'(1)$, then $n$ will satisfy the conditions of the problem.

It is clear that $p^k \mid P(p^k + i) - P(i)$ for all $i$, hence $p^k \mid \gcd(P(p^k + i) - P(0), P(p^k + 1) - P(1), P(p^k + 2) - P(2), \ldots)$. We now claim that $p^{k+1} \nmid P(p^k + 1) - P(1)$. Let $Q(x) = \sum_{i=0}^m c_i x^i$, then
$$\begin{align*} P(p^k + 1) - P(1) &= (p^k + 1)^k Q(p^k + 1) - Q(1) \\ &= \left( \sum_{i=0}^k \binom{k}{i} (p^k)^i \right) Q(p^k + 1) - Q(1) \\ &\equiv (k p^k + 1) Q(p^k + 1) - Q(1) \\ &= k p^k Q(p^k + 1) + (Q(p^k + 1) - Q(1)) \\ &= k p^k Q(p^k + 1) + \sum_{i=0}^m c_i ((p^k + 1)^i - 1^i) \\ &= k p^k Q(p^k + 1) + \sum_{i=0}^m c_i \left(-1 + \sum_{j=0}^i \binom{i}{j} (p^k)^j \right) \\ &\equiv k p^k Q(p^k + 1) + \sum_{i=0}^m i c_i p^k \\ &= p^k (k Q(p^k + 1) + Q'(1)) \pmod{p^{k+1}}. \end{align*}$$
Thus,
$$\frac{P(p^k + 1) - P(1)}{p^k} = k Q(p^k + 1) + Q'(1) \equiv k Q(1) + Q'(1) \not\equiv 0 \pmod{p},$$
so $p^k$ fully divides $\gcd(P(p^k + i) - P(0), P(p^k + 1) - P(1), P(p^k + 2) - P(2), \ldots)$.

To show that no other prime $q \neq p$ divides each of $P(p^k) - P(0), P(p^k + 1) - P(1), P(p^k + 2) - P(2), \ldots$, suppose for contradiction that $q \mid P(p^k + i) - P(i)$ for all positive integers $i$. Observing that $q \mid P(q + i) - P(i)$, we find that $P(i + ap^k + bq) \equiv P(i) \pmod{q}$ for all integers $a$ and $b$. Since $\gcd(p^k, q) = 1$, we can choose $a$ and $b$ such that $ap^k + bq = 1$, yielding $q \mid P(i + 1) - P(i)$ for all $i$. But $q \mid P(0) = 0$, so $q \mid P(i)$ for all nonnegative $i$, which contradicts the hypothesis.

Therefore, there are infinitely many $n$ such that
$$\gcd(P(n) - P(0), P(n + 1) - P(1), P(n + 2) - P(2), \ldots) = n.$$

The answer is: $\boxed{\text{infinitely}}$ many } n}.