2016 Canada MO 3. Find all polynomials $P(x)$ with integer coefficients such that $P(P(n) + n)$ is a prime number for infinitely many integers $n$.

Hint 1: Work out the cases where the degree of the polynomial $P$ is 0 or 1. Are there any solutions here?

Scroll down for hint 2…

Hint 2: Use the lemma $a - b \mid P(a) - P(b)$ to show that $P(P(n) + n)$ always has a factor.