Polynomial equation : $P(P(P(n)))=n$ Let $P(x) \in \mathbb{Z}[x]$ for which $S = \{n\in\mathbb{Z} : P(P(P(n)))=n\}$ is nonempty. Prove that $P(n) = n$ for all $n\in S$.
My attempt :
Let $n=k$ for which $P(P(P(k)))=k$, so $P(P(P(k)))-k=0$
Let $Q(x)$ be polynomial such that $Q(Q(Q(x)))=P(P(P(x)))-x$ 
so $Q(Q(Q(x)))=0$ for $x=k$
so $Q(Q(k))$ is one root of the polynomial $Q(x)$.
 A: You can reduce the problem to the case of $n=0$. If $P(P(P(n)))=n$, define $P_0(x)=P(x+n)-n$. Then $P_0(P_0(P_0(0)))=P(P(P(n)))-n$, so, if the theorem is true for $0$, then $P_0(0)=P(n)-n=0$.
Assume $P(0)\neq 0$ and $P(P(P(0)))=0$.
We also know that $P(P(0))\neq 0$ or else $P(P(P(0)))=P(0)\neq 0$. We also have that $P(0)\neq P(P(0))$, because otherwise, $0=P(P(P(0)))=P(P(0))\neq 0$.
We will now use the following standard result:

For $q(x)\in\mathbb Z[x]$ you have that $q(m)\equiv q(n)\pmod{m-n}$ for all integers $m,n$.

We will prove that $P(0)\mid P(P(0))$ and $P(P(0))\mid P(0)$. From this we deduce that $P(P(0))=-P(0)$ and hence that $2P(0)\mid P(P(0))$, which is only possible if $P(0)=P(P(0))=0$.
Proof:
(1) With $q(x)=P(P(x))$ and $m=P(0), n=0$ you get that $$P(0)\mid P(P(0)).$$
(2) With $q=P(x),m=P(P(0)), n=0$ you $$P(P(0))\mid P(0).$$
(3) So $P(0)=\pm P(P(0))$. If $P(P(0))=P(0)$ then $0=P(P(P(0))=P(0)$. So assume $P(0)=-P(P(0))$.
(4) Now, letting $q(x)=P(x), m=P(0), n=P(P(0))=-P(0)$, you get $P(P(0))\equiv 0\pmod{2P(0)}.$
So $2P(0)\mid P(P(0))$ which contradicts $P(0)=\pm P(P(0))$ unless $P(0)= 0$.

This proof shows that this works for any function $f:\mathbb Z\to\mathbb Z$ such that $f(n)\equiv f(m)\pmod{n-m}$ for all integers $n,m$. There are uncountably many non-polynomial $f$, but there are also some polynomials with non-integer coefficients, like $f(x)=\frac{x^4+x^2}{2}$.

So the short proof is (writing $P^2(x)=P(P(x)), P^3(x)=P(P(P(x)))$):
Assume $P^3(n)= n.$ Then:
$$\begin{align}P^2(n)&\equiv P(n)\equiv n\pmod{P(n)-n}\\
n= P^3(n)&\equiv P(n)\pmod{P^2(n)-n}\\
n=P^3(n)&\equiv P^2(n)\pmod{P^2(n)-P(n)}
\end{align}$$
The first two lines mean that $P^2(n)-n=\pm \left(P(n)-n\right).$
If $P^2(n)-n=P(n)-n$, then $P^2(n)=P(n)$ and hence $n=P(P^2(n))=P(P(n))=P(n).$
If $P^2(n)-n=n-P(n)$ then $P^2(n)-P(n)=2(n-P(n))$. So $$n=P(P^2(n))\equiv P(P(n))\pmod{2(n-P(n))}$$
So we get that $2(n-P(n))\mid (n-P^2(n))$. But $n-P^2(n)=\pm (n-P(n))$, contradiction, unless $n-P^2(n)=0$ and hence $P^2(n)=n$ and then $P(n)=P(P^2(n))=n$.
