Lemma $a-b \mid P(a)-P(b)$ Proof Obvious. (Constant term gets cancelled) Thus, for $a=X+P(X)$ and $b=X$ we get that $P(X) \mid P(X+P(X))$ Thus, $P(n)$ is a factor of $P(n+P(n))$ and so, since for all sufficiently large $n$, $P(n+P(n))>>>>P(n)$ we have that either $P(n)=+1$ or $P(n)=-1$ for infinitely many $n$ which gives a contradiction. This was done under the assumption that $P$ has a degree larger than zero. Thus, the only solutions are the constant polynomials $P(X)=q$ where $q$ is a fixed prime number. These, indeed, work. Oops, edit, this is wrong as pointed below. (I was hasty ) I think some adjustments will correct this, since I hastily assumed that the leading coefficient is positive causing this to fail.

anantmudgal09 wrote: Lemma $a-b \mid P(a)-P(b)$ Proof Obvious. (Constant term gets cancelled) Thus, for $a=X+P(X)$ and $b=P(X)$ we get that $P(X) \mid P(X+P(X))$ Thus, $P(n)$ is a factor of $P(n+P(n))$ and so, since for all sufficiently large $n$, $P(n+P(n))>>>>P(n)$ we have that either $P(n)=+1$ or $P(n)=-1$ for infinitely many $n$ which gives a contradiction. This was done under the assumption that $P$ has a degree larger than zero. Thus, the only solutions are the constant polynomials $P(X)=q$ where $q$ is a fixed prime number. These, indeed, work. This is false. You are missing the solution $P(x)=-2x+a$ where $a$ is any odd integer. Note that $P(n)+n=-n+a$, so $P(P(n)+n)=P(-n+a)=-2(-n+a)+a=2n-a$ which is indeed prime for infinitely many $n$. By the way, that is the only solution for degree 1 polynomials.

anantmudgal09 wrote: Lemma $a-b \mid P(a)-P(b)$ Proof Obvious. (Constant term gets cancelled) Thus, for $a=X+P(X)$ and $b=P(X)$ we get that $P(X) \mid P(X+P(X))$ Thus, $P(n)$ is a factor of $P(n+P(n))$ and so, since for all sufficiently large $n$, $P(n+P(n))>>>>P(n)$ we have that either $P(n)=+1$ or $P(n)=-1$ for infinitely many $n$ which gives a contradiction. This was done under the assumption that $P$ has a degree larger than zero. Thus, the only solutions are the constant polynomials $P(X)=q$ where $q$ is a fixed prime number. These, indeed, work. Oops, edit, this is wrong as pointed below. (I was hasty ) I think some adjustments will correct this, since I hastily assumed that the leading coefficient is positive causing this to fail. I believe you mean , for $a=X+P(X)$ and $b=X$. Of course you still get get that $P(X) \mid P(X+P(X))$

The correct conclusion is $P(n)$ equals $1$ OR $-1$ OR $P(n+P(n))$ OR $-P(n+P(n))$ for infinitely many $n$. Of course, If $P$ is plus/minus $1$ for infinitely many $n$, then $P$ is constant. The other two cases are slightly harder. I could post them if you want.

No, it's okay, I will try them myself now that I know the fatal error.

Why other linear solutions don't exist?!

So obviously we have $P(n)|P(P(n)+n)$ for all $n$ - this forces $P(P(n)+n) = P(n)Q(n)$ for some polynomial $Q$. Clearly, $Q$ has integer coefficients so $Q(n) \in \mathbb{Z}$. Since $P(n)=\pm 1$ has finite solutions, there are infinitely many $n$ where $P(P(n)+n)$ is a prime number and $P(n) \not= \pm 1$. Therefore, we have $Q(n) = \pm 1$ for infinitely many $n$, so $Q$ is a constant polynomial. This forces $deg(P(P(n)+n)) = deg(P(n))$. Let $deg(P)=k$. If $k \ge 2$, this forces $deg(P(P(n)+n))=k^2$ because the $x^k$ term does not disappear in $P(n)+n$. Since $k^2 \not= k$, we have $k \le 1$. Case 1. $k=0$. Clearly $P$ is a constant function - a prime number. Case 2. $k=1$. Let $P(n)=an+b$. $P(P(n)+n)=a(an+b+n)+b=a(a+1)n+b(a+1)=(a+1)(an+b)$. This must be prime for infinitely many $n$, so $|a+1|=1$. Since $a \not= 0$, we have $a=-2$. Now $2n-b$ must be prime for infinitely many $n$, so clearly $b$ can be/must be all odd numbers. Therefore we get $P(n)=-2n+c$ where $c$ is all odd numbers.

Can anyone give a correct proof for this problem?

@above rkm0959's solution is correct just read it

We utilize the well known fact that for integers $x, y$ we always have $x - y\mid P(x) - P(y)$. Let $x = P(n) + n$ and $y = n$. We get that $P(n) \mid P(P(n) + n) - P(n) \implies P(n) \mid P(P(n) + n)$. If $P(P(n) + n)$ is to be prime, we must have $|P(n)| = 1$ or $|P(n)| = |P(P(n) + n)|$. Suppose that there are finitely many $n$ satisfying the latter case. Then there are infinitely name $n$ satisfying the former case, hence infinitely many $n$ such that $P(n) = 1$ or $P(n) = -1$, implying that either $P = 1$ or $P = -1$ for all reals, a contradiction. Hence, $|P(n)| = |P(P(n) + n)|$ must hold for infinitely many integers $n$. We split into cases. If $P(n) = P(P(n) + n)$ for infinitely many integers $n$, it must hold for all integers $n$. Hence they must be the same polynomial and must have the same degree $k$. We see hat $k = k^2$ so either $k = 1$ or $0$. Either way we assume $P$ is linear. Plugging in $P(x) = ax + b$, we see that $a = 0$. Hence only constant prime functions work. Our answer in this case is all $P(x) = c$ for some prime constant $p$. If $P(n) = -P(P(n) + n)$, we use a similar argument to obtain degree is either $0$ or $1$. Plugging in $P(x) = ax + b$, we get that $a = -2$ or $a, b$ are both $0$. The latter case is impossible. We check to see that all $P(x) = -2x + c$ for odd integers $c$ all work, which is our answer in this case. Combining two cases, we have all our answers, as desired. $\blacksquare$

Let $P(x)=c_yx^y+c_{y-1}x^{y-1}+\dots+c_1x+c_0$. This also means that $\deg{P}=y$. First, we start with the following rather well-known lemma: Lemma: For integer coefficient polynomials, $a-b \mid P(a)-P(b)$, where $a$ and $b$ are integers. Proof: We have $P(a)-P(b)=c_ya^y+c_{y-1}a^{y-1}+\dots+c_1a+c_0-c_yb^y-c_{y-1}b^{y-1}-\dots-c_1b-c_0=c_y(a^y-b^y)+c_{y-1}(a^{y-1}-b^{y-1})+\dots+c_2(a^2-b^2)+c_1(a-b)$. Now, note that $a-b \mid a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\dots+b^{k-1})$ for all $k \geq 2$. This implies $a-b \mid P(a)-P(b)$, since every term of this expression is a multiple of $a-b$. Now, we move on to the main claim. Claim: $P(n) \mid P(P(n)+n)$. Proof: Plugging in $a=P(n)+n$ and $b=n$ in our lemma, we have $a-b \mid P(a)-P(b) \rightarrow P(n)+n-n \mid P(P(n)+n)-P(n) \rightarrow P(n) \mid P(P(n)+n)-P(n)$. Since $P(n) \mid P(n)$, it follows that $P(n) \mid P(P(n)+n)$. Since $P(P(n)+n)$ is prime for infinitely many $n$, this means we must have $P(n)=\pm1$ or $P(n)=\pm{P(P(n)+n)}$ for infinitely many $n$. Now we proceed with casework. Case 1: $P(n)=\pm1$ for infinitely many $n$ Since $P$ is a polynomial, and there are infinitely many values of $n$ for which $P(n)=\pm1$, it follows that $P(x)=1$ or $P(x)=-1$, and clearly $1$ and $-1$ are not primes, so this case is impossible. Case 2: $P(n)=\pm{P(P(n)+n)}$ for infinitely many $n$ Since $P$ is a polynomial, by the same logic as above, it follows that $P(n)=\pm{P(P(n)+n)}$ for all values of $n$. This means we have $\deg{(P(n))}=\deg{(\pm{P(P(n)+n}))}$. As defined at the start, $\deg{P}=y$. The highest power, or degree of $P(P(n)+n)$ will be $(n^y)^y=n^{y^2}$, so we have $y=y^2$, so $y=0,1$. The case $y=0$, so when $P$ is a constant, is obvious; it's just $P(x)=p$ where $p$ is a prime. Now we will look at when $y=1$. This means $P$ is linear, and we can rewrite $P(x)=mx+k$. Plugging this in our equality $P(n)=\pm{P(P(n)+n)}$ and matching coefficients, we obtain that $m=0,-2$. $m=0$ yields the constant solution we found earlier and $m=-2$ means $P(n)=-2n+k$. If we want this to be prime for some values of $n$, then $k$ must be odd. Therefore, our solutions are $\boxed{P(x)=p \text{ where p is a prime, and } P(x)=-2x+k \text{ where k is an odd integer.}}$ $\blacksquare$ Remark: Oops negatives exist

It was nice but a bit easy for it's position - Lemma: $P(n) \mid P(n + kP(n))$ for any integer polynomial $P$ and an integer $k$. Proof- Note that $n+ kP(n) \equiv n mod P(n)$ so applying $P$ on both sides we get desired thing. Now note that we can WLOG assume that leading coefficient of $P$ is positive , then from our lemma above we should have $P(n) = 1$ for infinite $n's$ or for infinite $n's$ $P(n+P(n) = P(n)$ , but first one gives $P \equiv 1$ which is impposible , so for infinite $n's$ $P(n+P(n)) = P(n)$ , but if we let deg$P$ = $d$ , then $P(n+P(n)) = \mathcal{O}(n^{d^2})$ but $P(n) = \mathcal{O}(n^{d})$ , this is a contradiction unless $d^2 = d$ i.e $d = 0,1$. So rest is easy. $\blacksquare$

Since $a-b|P(a)-P(b)$, $P(n)|P(n+P(n))$ as $n+P(n)$ is congruent to $n$ mod $P(n)$. Thus,for infinitely many $n$,$|P(n)|=1$ or $|P(n+P(n))|=|P(n)|$. If there are infinitely many $n$,satisfying the former then $P(x)=1$ or $-1$,which doesn't work. So there are infinitely many satisfying the latter. Now,if for infinitely many $n$ $P(n+P(n))=P(n)$,then due to degree reasons $P$ is linear.Assume it to be $ax+b$,Putting it back yields $a=0$. Thus $P$ is constant in this case ,which only works if the $P(x)=p$ for a prime $p$. Now,if there are infinitely $n$,$-P(n+P(n))=P(n)$,then again due to degree reasons ,$P$ has to be linear. Again substituting of that form,we have $(ax+b)(a+2)=0$,which gives $P$ zero(doesn't work) or $a=-2$,Then $P(x)=-2x+b$ ,but is composite if $b$ is even.Thus $b$ is odd,which clealry works.

If $P$ is constant, only $\boxed{P(n)=p}$ for prime $p$ work. Now assume $P$ is nonconstant. Note that: $$(P(n)+n)-n\mid P(P(n)+n)-P(n)\Rightarrow P(n)\mid P(P(n)+n).$$Taking $n$ such that $P(P(n)+n)$ is prime, we have that $P(n)\in\{-P(P(n)+n),-1,1,P(P(n)+n)\}$ for infinitely many $n$. If there are infinitely many $n$ with $P(n)=-1$, $P$ is constant. Similarly, we can't have $P(n)=1$ for infinitely many $n$. So $P(n)\in\{-P(P(n)+n),P(P(n)+n)\}$ for infinitely many $n$. Suppose $P(n)=P(P(n)+n)$ for infinitely many $n$. By comparing the degrees of each side, we must have $\deg P=\deg P\cdot\max\{\deg P,1)\}$, so $\deg P=1$. Letting $P(n)=an+b$ with $a\ne0$, we have $an+b=0$ after substituting into $P(n)=P(P(n)+n)$, a contradiction. Suppose $-P(n)=P(P(n)+n)$ for infinitely many $n$. As before, $P$ must be linear, so upon setting $P(n)=an+b$ we obtain $a(a+2)n+(a+2)b=0$, leading to the solution $P(n)=-2n+b$. Note that $P(P(n)+n)=2n-b$, so $b$ must be odd. When $b$ is odd, $-2n+b$ is a solution.

If polynomial $P$ is constant, then it is easy to see that only $P(n)=p$, where $p$ is an arbitrary prime, works. If polynomial $P$ has degree $1$, then we can express it in the form $P(x)=ax+b$, where $a,b$ are some integers. Observe that: $$ P(P(n)+n) =P(an+b+n) = a(a+1)n+b(a+1) = (a+1)(an+b) $$If the last expression is equal to some prime infinitely many times, then it is easy to see that $a=-2$ and $2n-b$ must be prime. Obviously $b$ must be odd, but by Diriclet's theorem there are infinitely many primes of the form $2n-b$, where $b$ is odd; therefore polynomial $P(n)=-2n+b$ works. Now suppose that $\deg(P) =k>1$. We use well - known lemma that $a-b \mid P(a-b)$. This means the following: $$ P(n) =(P(n)+n)-P(n) \mid P(P(n)+n)-P(n) $$Thus $P(n) \mid P(P(n)+n)$. Note that $P(n) = \pm 1$ only for finitely many values ( in fact no more than $2\deg(P)$ times ). This allows us to conclude that $P(P(n)+n) = | P(n) |$ for infinitely many values of $n$. We split this in $2$ possible cases. If $P(P(n)+n)=P(n)$ and it holds for infinitely many values of $n$, then these $2$ polynomials must be the same. On the other hand $\deg(P(P(n)+n))=k^2$, whereas $\deg(P(n)=k$, which is contradiction for $k>1$. If f $P(P(n)+n)=-P(n)$ and it holds for infinitely many values of $n$, then these $2$ polynomials must be the same. On the other hand $\deg(P(P(n)+n))=k^2$, whereas $\deg(P(n)=k$, which is contradiction for $k>1$. With all cases being exhausted we conclude that the only possible polynomials are $P(n)=p$, where $p$ is prime and $P(n)=-2n+b$, where $b$ is an odd integer.

Note that $P(P(n)+n) \equiv P(n) \equiv 0 \pmod{P(n)}$, so $P(n)$ divides the quantity in question, which is a prime. $P(n)$ cannot be $1$ identically since $1$ is not a prime (if u disagree then cry about it). So, either $P(P(n)+n) = P(n)$ or $P(P(n)+n) = -P(n)$ is indentically true. If its the former, then we can do degree comparison to conclude $P$ is linear at which point only solution which works is $P(n) = p$ for some prime number $p$. If $P(P(n)+n) = -P(n)$ again degree comparison leads to linear, so plugging in $P(n) = an+b$, we get $P(n) = a-2n$ for odd $a$.

If $P$ is constant, it can only be any fixed prime, suppose $P$ is non-constant. Having in mind the classical lemma $A-B \mid P(A) - P(B)$ for any integers $A$ and $B$, setting $A=P(n) + n$ and $B=n$ in it yields that $P(n)$ divides $P(P(n)+n) - P(n)$, i.e. $P(n)$ divides $P(P(n)+n)$. Therefore (as $P(n) = \pm 1$ for finitely many $n$, since a non-zero polynomial has finitely many roots) $P(P(n) + n) = \pm P(n)$ for infinitely many $n$ and hence at least one of $P(P(n) + n) = P(n)$ and $P(P(n) + n) = -P(n)$ holds for infinitely many $n$. If $\deg P = k \geq 1$, then supposing $k\geq 2$ would yield $\deg (P(n) + n) = k$, $\deg P(P(n) + n) = k^2$ and so $k^2 = k$, contradiction. Finally, if $k=1$, i.e. $P(n) = an+b$ with $a\neq 0$, then going back to the problem condition $P(P(n) +n) = P((a+1)n + b) = a(a+1)n + ab + b = (a+1)(an+b)$. Since $|an+b| > 1$ when $n$ is large, we must have $a+1 = \pm 1$, thus $a=-2$ (as $a\neq 0$); conversely, if $P(n) = -2n+b$, then $P(P(n)+n) = -2n+b$ and this is prime infinitely often only when $b$ is odd (the equality $-2n+b = -p$ for a large prime $p$ is achievable by $n = \frac{b+p}{2}$).