Problem 1647

Solution:
Note that if $P(n)=0$ then $P(P(n)+n)=P(n)=0$ which is not prime. Let $P(x)$ be a degree $k$ polynomial of the form $P(x)=a_{k} x^{k}+a_{k-1} x^{k-1}+\cdots+a_{0}$ and note that if $P(n) \neq 0$ then
$$\begin{aligned} & P(P(n)+n)-P(n)= \\ & \quad a_{k}\left[(P(n)+n)^{k}-n^{k}\right]+a_{k-1}\left[(P(n)+n)^{k-1}-n^{k-1}\right]+\cdots+a_{1} P(n) \end{aligned}$$
which is divisible by $(P(n)+n)-n=P(n)$. Therefore if $P(P(n)+n)$ is prime then either $P(n)= \pm 1$ or $P(P(n)+n)= \pm P(n)=p$ for some prime number $p$. Since $P(x)$ is a polynomial, it follows that $P(n)= \pm 1$ for only finitely many integers $n$. Therefore either $P(n)=P(P(n)+n)$ for infinitely many integers $n$ or $P(n)=-P(P(n)+n)$ for infinitely many integers $n$.

Suppose that $P(n)=P(P(n)+n)$ for infinitely many integers $n$. This implies that the polynomial $P(P(x)+x)-P(x)$ has infinitely many roots and thus is identically zero. Therefore $P(P(x)+x)=P(x)$ holds identically. Now note that if $k \geq 2$ then $P(P(x)+x)$ has degree $k^{2}$ while $P(x)$ has degree $k$, which is not possible. Therefore $P(x)$ is at most linear with $P(x)=a x+b$ for some integers $a$ and $b$. Now note that
$$P(P(x)+x)=a(a+1) x+a b+b$$
and thus $a=a(a+1)$ and $a b+b=b$. It follows that $a=0$ which leads to the solution $P(n)=p$ where $p$ is a prime number.

By the same argument if $P(n)=-P(P(n)+n)$ for infinitely many integers $n$ then $P(x)=-P(P(x)+x)$ holds identically and $P(x)$ is linear with $P(x)=a x+b$. In this case it follows that $a=-a(a+1)$ and $a b+b=-b$. This implies that either $a=0$ or $a=-2$. If $a=-2$ then $P(n)=-2 n+b$ which is prime for some integers $n$ only if $b$ is odd. Note that in this case $P(P(n)+n)=2 n-b$ which is indeed prime for infinitely many integers $n$ as long as $b$ is odd.