, 2022

We prove first that $P$ has rational coefficients. Let $d$ be the degree of $P$. Consider the numbers $a_i = P(i)$ for $i = 1, 2, \dots, d+1$. Let
$$Q(x) = \sum_{l=1}^{d+1} a_l \prod_{i \neq l, 1 \le i \le d+1} \frac{x-i}{l-i}.$$
Then the degree of $Q$ is at most $d$ and $Q(i) = a_i$ for $1 \le i \le d+1$ and since $a_l \in \mathbb{Z}$ for all $l$ we have that $Q$ has rational coefficients. Since $P(i) = Q(i)$ for $i \in \{1, 2, \dots, d+1\}$ we conclude that any of $1, 2, \dots, d+1$ is a root of the polynomial $P(x) - Q(x)$ which is of degree at most $d$. This implies that $P(x) = Q(x)$ thus $P \in \mathbb{Q}[X]$.

Choose a positive integer $N$ such that $NP(x) = R(x)$ is a polynomial of integer coefficients and let $N = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ be where $(N, p_1p_2 \cdots p_k) = 1$. Assume that there exist positive integers $x_1, x_2, \dots, x_k$, such that $P(x_1)$ is not divisible by $p_l$ for all $l \in \{1, 2, \dots, k\}$. It follows from Chinese remainder theorem that there exists a positive integer $x$ such that $x \equiv x_i \pmod{p_i^{\alpha_i+1}}$ for $i = 1, 2, \dots, k$. Therefore for any $l \in \{1, 2, \dots, k\}$ we have that $R(x) \equiv R(x_l) \pmod{p_l^{\alpha_l+1}}$, i.e. $R(x)$ is divisible by $p_l^{\alpha_l}$ but is not divisible by $p_l^{\alpha_l+1}$. The latter implies that $P(x) = R(x)/N$ is not divisible by $p_l$ for all $l \in \{1, 2, \dots, k\}$, a contradiction with the condition of the problem. We conclude that there exists $m$ such that $p_m|P(n)$ for all $n \in \mathbb{N}$.