, 2011

For the sake of contradiction suppose that $P(x)$ is not constant and consider the case when $P(x)$ is a linear polynomial. It means that $P(x) = a x + b$ for some $a, b \in \mathbb{Z}$, where $a \neq 0$. Let $Q(x) = a x^2 + (b+1)x$. Then
$$P(Q(x)) = a(a x^2 + (b+1)x) + b = a^2 x^2 + a(b+1)x + b = (a x + b)(a x + 1)$$
but polynomials $a x + b$ and $a x + 1$ are not constant, a contradiction.

Now suppose that $\deg P = n > 1$. Suppose also that
$$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0,$$
where $a_n \neq 0$. Consider a polynomial $Q(x) = P(x) + x$. Clearly it has integer coefficients. Moreover,
$$P(Q(x)) - P(x) = P(P(x) + x) - P(x) = \sum_{i=0}^{n} a_i ((P(x) + x)^i - x^i)$$
From the formula
$$a^i - b^i = (a-b)(a^{i-1} + a^{i-2}b + \dots + b^{i-1})$$
it follows that the polynomial $(P(x) + x)^i - x^i$ is divisible by the polynomial $P(x)$. So $P(Q(x))$ is divisible by $P(x)$ as well. But this is a contradiction, since $\deg P > 1$ implies that the degree of $P(Q(x))$ is greater than the degree of $P(x)$, which means that $P(x)$ is a non-trivial divisor of $P(Q(x))$. Conclusion follows. $\square$