Choose a prime $p\nmid P(0)$ and plug in $(m,n)=(p,0)$ to get $p\cdot P^p(0)$ is a perfect square, so $p\mid P^p(0)$. Consider the orbit $$0\to P(0)\to P(P(0))\to\cdots$$in $\bmod\ p$. Clearly it is periodic, and we know that its period is not $1$, but must divides $p$, so it is precisely $p$. Therefore every $p$ consecutive numbers in the orbit of $0$ forms a complete residue system $\bmod\ p$. Now consider any $t\in\mathbb Z$. We know that $P^k(0)\equiv t\pmod{p}$ for exactly one value of $0\leqslant k\leqslant p-1$. Therefore, $$\{t,P(t),P(P(t)),\ldots,P^{p-1}(t)\}\equiv \{P^k(0),P^{k+1}(0),\ldots, P^{k+p-1}(0)\}\pmod{p}$$is also a CRS $\bmod\ p$ If $P(n)$ is not of the form $n+c$, then by Schur, $\{P(n)-n\mid n\in\mathbb Z\}$ has infinitely many prime divisors, so for some prime $q\nmid P(0)$ and $n_0\in\mathbb Z$, $q\mid P(n_0)-n_0$, contradicting the previous paragraph. Therefore $P(n) = n+c$ for some constant $c$. The problem now reduces to finding all $c\in\mathbb Z$ such that $$(m+cn)(n+cm)$$is always a perfect square, and this is easy: - If $c<0$, when $(m,n)=(1,1-c)$ we have $(m+cn)(n+cm) = 1+(1-c)c<0$ which is obviously not a perfect square. - If $c=0$ then it's obvious that $c$ doesn't work, and if $c=1$ it's obvious that $c$ works. - Finally, if $c\geqslant 2$, choose a prime $p>c^2$ and plug in $(m,n)=(p-c,1)$ to get $(m+cn)(n+cm)=p(1+pc-c^2)$ which is divisible by $p$ but not $p^2$, and so is not a perfect square. Therefore, the only such $P$ is $\boxed{P(n)=n+1}$

Does this problem help ? https://artofproblemsolving.com/community/c6h6448p22328

using equivalence relations it becomes 2010 IMO #3 hint: let f(n)=P^{n}(0) and a~b iff ab is a square.

Note that, if $m=0$, we get $P^n(0)n$ is a perfect square, and $n=1$ gives $P(0)$ is a square. Considering the sequence $a_i=P^i(0)$, note that $a_{i}-a_{i-1}|a_{i+1}-a_i$ since $P$ is an integer polynomial. This implies that $P(0)|a_i$. Also, $a_{i+1}\equiv P(0)\pmod {a_i}$, since $a_{i+1}=P(a_i)$. Now, I will inductively show that $a_i=iP(0)$. Clearly, the base case is true, so suppose $a_k=kP(0)$. Note that $a_{k+1}-a_k$ must be of the form $(1+nk)P(0)$ for $n\ge 0$. Note that as all future partial differences are divisible by this, $a_i\equiv kP(0)\pmod{(1+nk)P(0)}\forall i>k$. So, this means that $\gcd(a_i/P(0),(1+nk))=1\forall i>k$. Now, if $n>1$, consider a squarefree factor, $f>1$, of $1+nk$, and a very large squarefree multiple of $f$, $F$. Of course, we want $P^F(0)F$ to be a perfect square. However, as $P(0)$ is a square, we need $F|\frac{a_F}{P(0)}$, which is a contradiction, since $f\not\arrowvert \frac{a_F}{P(0)}$. Therefore, we must have $n=0$ and $a_{k+1}=(k+1)P(0)$, as desired. Now, as $P(x)-(x+P(0))$ has infinite roots, located at all $a_i$, we must have that $P(x)=x+P(0)$. Denoting $P(0)$ as $c^2$, $(n+mc^2)(m+nc^2)$ is always a perfect square. Now, if $c>1$, choose $(m,n)$ with the following properties: $n=c^2n'$, $m+n'$ is squarefree, $\gcd(m,n)=1$, and $\gcd(m+n',c^4-1)=1$. Then, this becomes $c^2(m+n')(m+n'c^4)$. So, we must have $m+n'|m+n'c^4$. However, $\gcd(m+n',m+n'c^4)=\gcd(m+n',n'(c^4-1))=1$, which is a contradiction. Therefore, $c=1$ and $P(x)=x+1$ is the only solution.

Nice! Here's my solution (which is heavily dependent on induction): Define the sequence $(x_j)_{j \geq 0}$ with $x_0=0$ and $x_j=P(x_{j-1})$ for all $j \in \mathbb{N}$. Then the given condition states that $nx_n$ is a perfect square for all $n \in \mathbb{N}$. We first prove some claims which will help us strengthen our foothold over the sequence $(x_j)_{j \geq 0}$. Throughout we'll be using the deep fact that $a-b \mid P^k(a)-P^k(b)$ for all non-negative integers $a,b,k$. CLAIM 1 $x_i \mid x_{iz}$ for all $i,z \in \mathbb{N}$.

CLAIM 2 For all $n \in \mathbb{N}$, we have $n \mid x_n$.

CLAIM 3 Let $x_1=P(0)=A^2$ for some $A \in \mathbb{N}$ (Since $P(0)$ is a non-zero square). Then $x_i-x_{i-1}=A^2$ for all $i \in \mathbb{N}$.

Return to the problem at hand. By Claim 3, we get that the equation $P(x)-x-A^2=0$ has infinitely many roots, namely $x_0,x_1,x_2 \dots$ (which are all distinct, since our claim ascertains that this sequence is an increasing sequence). Thus, we must have $P(x)=x+A^2$. Then $P^m(x)=x+mA^2$ for all $m \geq 0$. Suppose $A>1$, and choose a prime $p \mid A$. Then putting $(m,n)=(A^2,p-1)$ in the given conditions, we get that $pA^2(A^4+p-1)$ is a perfect square. But, $p \mid A$ gives that $\gcd(A^4+p-1,p)=1$. Then $$\nu_p(pA^2(A^4+p-1))=\nu_p(pA^2)=2\nu_p(A)+1$$which means that an odd power of $p$ divides $pA^2(A^4+p-1)$, contradicting the fact that this is a square. Thus, we must have $A=1$, and so we get the desired polynomial as $P(x)=x+1$. This clearly works, and so we're done. $\blacksquare$

Consider $P\ne\text{constant}.$ Since $P\equiv C$ is easy to notice. If \begin{align*} n=0\to mp^m(0)&=x_m^{2}\quad\forall m\left(x_m\in\mathbb N\right)\\ \implies p\mid p^p(0)&=x_p^2\quad\forall p\in\text{(prime)}\\ \implies p\mid p^p(0)\quad\forall p\in\text{(prime)}\\ \end{align*}Take $p\nmid p(0)$ $\{0,p(0),\cdots,p^p(0)\}\implies\exists 0\leqslant i<j\leqslant p, p^i(0)\equiv p^j(0)[p]$ by $\text{Dirichlet's principle}$ Let $a_k=p^k(0)\implies\exists T\in\mathbb Z_p\leqslant p: a_{k+T}\equiv a_k[\pmod {p}]\forall k\ge 0$ Since $p\mid p^p(0)\implies T\mid P\implies\begin{cases} T&=1\\ T&=P\end{cases}$ $T=1\implies a_i\equiv a_{i+1}\equiv\hdots\equiv a_p\equiv a_{p+1}[p]\implies a_{p+1}=P(a_p)\equiv P(0)[\pmod {p}]\implies p\mid p(0)(\text{constant})\implies T=P$ For any $a\in\mathbb Z, P^k(0)\equiv a\pmod{p}$ for exactly one $k, 0\le k<P\implies\{a,P(a),P(P(a)),\hdots,P(a)\}\equiv\{P^k(0),P^{k+1}(0),\hdots,P^{k+p-1}(0)\}(\pmod {p}).$ This is a complete residue system $\pmod{p}.$ If $P(x)-x=Q(x)$ is a non-constant polynomial. By $\text{Schur's theorem}$ $\{P(n)-n: n\in\mathbb Z^+\}$ has infinitely many prime. Take $Q\mid P(0),n_0\in\mathbb Z, Q\mid P(n_0)-n_0.$ Note, $Q$ is prime this contradict to the above conditions when $q=p.$ Therefore $P(x)=x+c$ for some constant $c\in\mathbb Z.$ $(m+cn)(n+cm)$ is a square $\forall m,n\in\mathbb N.$ case 1 $c<0: m=1, n=1-c\implies(m+cn)(m+cm)=1+c-c^2<0$ case 2 $c=0: (m+cn)(n+cm)=mn$ not possible. case 3 $c=1$ is easy to check case 4 $\exists p\in\mathbb P : p >c^2+1$ $m=p-c,n=1\implies (m+cn)(n+cm)=p(1+pc-c^2): p\nmid p^2\implies\text{Contradiction}$ Hence, $c=1\implies P(x)\equiv x+1$

What a nice problem, took the wrong approach several times before trying "arrow" From the problem, we have $p \cdot P^p(0)$ is a square for any prime number $p$, forcing $p \mid P^p(0)$ for all primes $p$. Take a prime number $p \nmid P(0)$. Claim 01. We have $\{ P(0), P^2(0), \dots, P^p(0) \}$ being complete residues modulo $p$. Proof. Consider \[ 0 \mapsto P(0) \mapsto P(P(0)) \mapsto \dots \mapsto P^p(0) \]Let $a$ be the smallest positive integer such that $P^a(0) \equiv 0 \ ( \text{mod} \ p)$. We must have $a \mid p$ by the definition of $a$. Thus, $a = 1$ or $a = p$. However, we have taken $p \nmid P(0)$, so $a = p$. If there exists two positive integers $1 \le a < b \le p - 1$ such that $P^a(0) \equiv P^b(0) \ (\text{mod} \ p)$. This forces $P^{p} (0) \equiv P^{p - b + a} (0) \ (\text{mod} \ p)$, forcing $k = p - b + a < p$ to satisfy $P^k(0) \equiv 0 \ (\text{mod} \ p)$, a contradiction. Thus, all of them must be distinct residues, resulting in a complete residue modulo $p$. Claim 02. This can be extended slightly to $\{ P^k(0), \dots, P^{k + p - 1}(0) \}$ is a complete residue modulo $p$. Proof. Since $P^p(0) \equiv 0 \ (\text{mod} \ p)$, then since $P \in \mathbb{Z}[x]$, then $P^{a + p}(0) = P^a (P^p (0)) \equiv P^a (0) \ (\text{mod} \ p)$. Now, just notice that $\{ k, k + 1, \dots, k + p - 1 \} \equiv \{ 1, 2, \dots, p \}$ in $\mathbb{Z}_p$, and we are done.

Take any integer $t \in \mathbb{Z}$. Claim 03. $\{ t, P(t), \dots, P^{p - 1}(t) \}$ forms a complete residue modulo $p$. Proof. Since $\{ P(0), P^2(0), \dots, P^p(0) \}$ forms a complete residue modulo $p$. Then, we can take $1 \le k \le p - 1$ such that $P^k(0) \equiv t \ (\text{mod} \ p)$. Thus, \[ \{ t, P(t), \dots, P^{p - 1}(t) \} \equiv \{ P^k(0), P^{k + 1}(0), \dots, P^{k + p - 1}(0) \} (\text{mod} \ p) \] Main Claim. $P(n) - n$ is a constant. Proof. Now, we know that for any prime number $p \nmid P(0)$ and any integer $t \in \mathbb{Z}$, then $p \nmid P(t) - t$ (since $\{ t, P(t) \}$ are distinct residues modulo $p$ for any $t \in \mathbb{Z}$.) Therefore, we conclude that if $\mathcal{P}$ is the set of primes dividing $P(n) - n$ for all $n \in \mathbb{N}$, and $\mathcal{Q}$ is the set of primes dividing $P(0)$, then \[ \mathcal{P} \subseteq \mathcal{Q} \Rightarrow |\mathcal{P}| \le |\mathcal{Q}| \]which proves that $|\mathcal{P}|$ is finite. However, by Schur Theorem, unless $P(n) - n$ is a constant, $|\mathcal{P}|$ is infinite, which is a contradiction. Thus, we conclude that $P(n) = n + b$ for some integer $b$. We have $P^m(n) \cdot P^n(m) = (n + mb)(m + nb)$ is a square for all $n,m \in \mathbb{N}_0$. Take $n = 0, m = 1$ gives us $b$ being a perfect square. Take $m = 4, n = 1$, and we have $4b^2 + 17b + 4$ being a square. However, since \[ (2b + 2)^2 = 4b^2 + 8b + 4 < 4b^2 + 17b + 4 < 4b^2 + 20b + 25 = (2b+5)^2 \]We have $4b^2 + 17b + 4 = (2b + 3)^2 \rightarrow b = 1$ or $4b^2 + 17b + 4 = (2b + 4)^2 \rightarrow b = 12$, which is not a square. Therefore, the only solution is $\boxed{P(x) = x + 1}$ which works since \[ P^m(n) \cdot P^n(m) = (m + n)^2 \]is a square for all nonnegative $m,n$.

BartSimpsons wrote: Find all polynomials $P$ with integer coefficients such that $P (0)\ne 0$ and $$P^n(m)\cdot P^m(n)$$is a square of an integer for all nonnegative integers $n, m$. Remark: For a nonnegative integer $k$ and an integer $n$, $P^k(n)$ is defined as follows: $P^k(n) = n$ if $k = 0$ and $P^k(n)=P(P(^{k-1}(n))$ if $k >0$. Proposed by Adrian Beker. Nice Problem !! First note that $p \mid P^{p} (0)$ , suppose there exist a $x <p$ such that $ P^{x} (0) \equiv 0 mod p$ , as $p-x >0$ , choose a minimum such $x$. Now ,$P^{x}(0) = P^{p-x}(P^{p}(0)) \equiv P^{p-x}(0) \equiv 0 mod p$ , so in general $P^{p-kx}(0) \equiv 0 modp$. But we can choose $k > \frac{p}{x} - 1 > 0$ , so $p-kx <x$ , a contradiction to the minimality of $x$. , so using this we get that $P^t (0) \equiv 0 modp$ if and only if $t \equiv 0 mod p$ , for any prime $p$, so $P^{1} (0) = P(0) = 1$. But now $P^{p}(0) = P^{p-1}(1)$ , but from the statement $\nu_p(P^{p}(0))$ is odd , and as $ P^{p-1}(1). P(p-1)$ is perfect square this implies $P(p-1) \equiv P(-1) \equiv 0 mod p$ , but this is true for infinitely many primes $p$ , so $P(-1) = 0$ . So we can write $P(x) = (x+1)^{r}. g(x)$ where $g(-1) \neq 0$ , suppose $g$ is not constant $P^{p}(0)= P(P^{p-1}(0)) = (P^{p-1}(0) +1)^{r} .g( P^{p-1}(0)) = p^{odd}$ , so $P^{p-1}(0) = p^{t} - 1$ , for some natural $t$ , and $ g(p^{t} - 1) \equiv 0 mod p$ , but this is true for infinite $p,s$ , so $g(-1) = 0$ , a contradiction , so $g$ is indeed constant , this implies $P(x) =c(x+1)^{r}$ , but as $P(0) = c = 1$ , so $P(x) = (x+1)^{r}$ , from here we can easily prove $r = 1$ , (I will post it later as it just involved putting some values , to prove that $r = 1$) , Hence $P \equiv x+1$ $\blacksquare$

Answer is $P(x) \equiv x+1$, which clearly works. We will be showing that cycle of each negative number contains $0$ which would then be enough to imply $P(x) \equiv x+1$. Fix any $r \in \mathbb Z_{>0}$, to prove $0 \in -r,f(-r),f(f(-r)),\ldots$. $$m=0 \implies P^n(0) \cdot n \in S \qquad \qquad (1) $$Claim: $0,P(0),P(P(0)),\ldots$ is not a cycle. Proof: Assume on the contrary the sequence is eventually periodic. Pick $k,c$ (with $c \ge 1$) such that $P^k(0) = x \ne 0$ and $$ x = P^k(0) = P^{k+c} (0) = P^{k+2c}(0) = \cdots $$Then $(1)$ gives $$ x \cdot k, x \cdot (k+c), x \cdot (k+2c), \ldots \in S $$But this is an easy contradiction, say by using the fact that $S$ has density $0$ or making $\nu_p(k+yc)$ odd for prime $p \nmid x$. $\square$ Our Claim particularly gives $P^n(0) \ne 0 ~ \forall ~ n \ge 1$. $$ m = P^r(0) \implies P^{n+r}(0) \cdot P^{P^r(0)}(n) \in S \qquad \qquad (2)$$Combining $(1),(2)$ along with our Claim gives $$ Q(n) := (n+r) \cdot P^{P^r(0)} (n) \in S ~ ~ \forall ~ n \ge 0 \qquad \qquad (3)$$This forces $Q(n)$ be a square of polynomial with integer coefficients (see the proof in post #26 to Iran TST 2008/8). Then $$ n+r \mid Q(n) \implies (n+r)^2 \mid Q(n) \implies n+r \implies P^{P^r (0)} (n) \implies P^{P^r(0)}(-r) =0 $$So we have proven $0$ is in the cycle of $-r$. We are ready to finish. Claim $P$ must be linear and its leading coefficient must be $\pm 1$. Proof: Assume contrary. Choose a constant $\mu > 0$ such that $|P(x)| \ge |x|$ whenever $|x| \ge \mu$. But then cycle of $-\mu$ does not contain any $0$, which is a contradiction. $\square$ Now write $P(x) \equiv x+c$ with $c \in \mathbb Z \setminus \{0\}$. Again, exploiting $0$ is in cycle of each negative integer we obtain $c=1$, as desired. $\blacksquare$

The only solution is $\boxed{P(x) = x + 1}$, which works. Now we prove that nothing else works. Setting $m = 0$, we have \[P^n(0) \cdot n\]is a perfect square for nonnegative integers $n$. Therefore $p\mid P^p(0) $ for any prime $p$. For any prime $p$ not dividing $P(0)$, the period of $0,P(0), P(P(0)), \ldots, $ modulo $p$ divides $p$, so it must be equal to $p$. Therefore, $\{0,P(0), P(P(0)), \ldots, P^{p-1}(0) \}$ forms a complete residue set modulo $p$. This in fact implies that $p$ cannot divide $P(n) - n$ for any integer $n$ (if $P(n)\equiv n\pmod p$, take $P^k(0) \equiv n\pmod p$ for $k\le p-1$). Since $P(0)$ has finitely many prime divisors, $P(n) - n$ is constant by Schur. Let $P(n) = n+c$. We have \[(m + nc)(n + cm)\]is a perfect square. From setting $m = 0$, we see that $c$ is a perfect square. From setting $m = 1$ and $n = 4$, we have that $(4c + 1)(c + 4) = 4c^2 + 17c + 4$ is a perfect square. It is clearly strictly in between $(2c + 2)^2$ and $(2c + 5)^2$, so it must be equal to $(2c+3)^2$ or $(2c+4)^2$. This gives the only possibilities $c = 1$ and $12$, but $12$ isn't a perfect square, so $c = 1$, as desired.

Substitute $m=0$: $P^n(0)n$ is a perfect square. Note that if $P$ is constant, then $cn$ is a perfect square, which is false when $n$ is a big prime Now let $p$ be a prime. Because $P^p(0) \vdots p$, the length of the cycle of $0,P(0),P^2(0),\ldots$ mod $p$ should divide $p$, so it is $1$ or $p$. If it is $1$, then $p | P(0)$, so only finitely many $p$. For all other $p$ all residues $P(0),P^2(0),\ldots ,P^p(0)$ are different, and thus $Q(x)=P(x+1)-P(x) \not \vdots p$ for all $x$. Because $Q$ is divisible only by finitely many primes, it should be constant, and so $P$ is linear, say $P(x)=ax+b$. As $P(0)$ is a perfect square, $b=t^2$. Now let $P^k(0)=t^2a_k$. Then $a_1=1$ and $a_{k+1}=a*a_k+1$. And $k*a_k$ is a perfect square for all $k$. Suppose $q | a$, where $q$ is a prime. Then $a_q \equiv 1$ (mod $q$), and so $v_q(qa_q)=1$, contradicting the fact that it is perfect square. So $a$ is either one or negative one, as our values should be positive, it is $1$. Now the original equation tells us that $(m+nt^2)(n+mt^2)$ is always a perfect square. Take $m=p-nt^2$, where $p$ is a large prime. Then $n-nt^4 \vdots p$ for any large $p$, and thus $t^2=1$. So $P(x)=x+1$, which works because $P^n(m) \dot P^m(n)=(m+n)(m+n)=(m+n)^2$

Clearly no $P$ constant works so suppose $\text{deg} P \ge 1$, now let $P(m,n)$ the assertion. $P(p,0)$ gives $p \mid P^p(0)$ for all $p$ primes. Now we focus on all $p>\text{max}(P(0), 1434)$ and consider the orbit $0 \to P(0) \to P(P(0)) \to \cdots$ in $\pmod p$. It's clear that since we found a cycle we can consider minimal $k$ for which $p \mid P^k(0)$, but this means $k \mid p$ so since $p>P(0)$ we end up having $k=p$ and as a result $p$ is the lenght of the minimal cycle, now if there was a sub cycle in the graph we would never reach $0$ therefore $0,P(0), \cdots P^{p-1}(0)$ is a complete residue system $\pmod p$. Select $P^{k}(0) \equiv \ell \pmod p$ and now check that due to the cycle $\ell, P(\ell), \cdots, P^{p-1}(\ell)$ is also a complete residue system $\pmod p$. Suppose FTSOC $P(x)-x$ isn't constant, then by Schur theorem we get that for some $p>\text{max}(P(0), 1434)$ we can find $x_0$ such that $p \mid P(x_0)-x_0$ but this means the orbit of $x_0$ has a cycle of lenght $1$, contradicting minimality of the cycle with lenght $p$. Therefore $P(x)=x+c$ for all integers $x$, now $P(p,0)$ gives $c$ is a perfect square and the problem becomes $(m+cn)(n+cm)$ perfect square for all non-negative integers $m,n$. Trivially $c=0$ fails, and if $c<0$ then fix $m$ and set $n>-cm$ and $m+cn<0$ for large $n$ which gives that something $<0$ is a percect square, contradiction!. Therefore $c$ is a positive integer, now assume FTSOC $c \ne 1$. Note that by dirchlet we can get some large prime $p=m+cn$ by fixing some $m$ such that $\gcd(m,c)=1$ and setting very large $n$, now we have $p \mid n+cm$ which means $n+cm \ge m+cn$ but clearly since $c \ge 2$ we get RHS is larger than LHS at some point, contradiction!. Therefore $c=1$ which means $(m+n)(m+n)$ is a perfect square. This is completely true, therefore all polynomials $P \in \mathbb Z[x]$ that work are $P(x)=x+1$ thus we are done .

Claim: $P$ has positive leading coefficient. Proof. Suppose not, then for sufficiently large $|x|$ it follows that $|P(x)| > |x|$, and that $x$ and $P(x)$ have negative signs. Taking sufficiently large $n$ and $m$ of opposite parity $\pmod{2}$ gives the result. $\blacksquare$ Claim: $\nu_p(P^n(m))$ is unbounded for all primes $p$ and nonnegative $n, m$. Proof. FTSOC suppose that $\nu_p(P^n(0))$ is bounded above by some integer $N$. It then follows that if $a \equiv b \pmod{p^N}$, that then $P(a) \equiv P(b) \pmod{p^N}$. Note that $P^n(0) \cdot n$ is always a perfect square. Consider the cyclic chain taken $\pmod{p^N}$ of \[ 0, P(m), P(P(m)), \dots \]It follows that $\nu_p$ of the chain is eventually cyclic with some period $T$. However, this implies that $P^{kT}(0)$ and $P^{kpT}(0)$ have the same $\nu_p$ for sufficiently large $k$, contradiction. $\blacksquare$ Claim: $P(x) = x + 1$. Proof. Note that $\gcd(P(x), x) \mid P(0)$ for all $x$. Then take sufficiently large $x$ such that $\gcd(x, P(0)) = 1$ and $P(x) - x > 0$. If any prime $p \mid P(x) - x$, then $p \nmid x$, so $\nu_p(P^n(x))$ is always $0$, contradiction. $\blacksquare$

Let $a_n = P^(n)(0)$. Plugging $m=0$ gives $na_n$ to be a perfect square for all $n \ge 0$. Claim: For large enough prime $p$, we have $a_n \pmod p$ to be purely periodic with period $p$. Proof: Let $p > \max(0, |P(0)|)$ be a large enough prime. Note that sequence $a_n \pmod p$ is eventually periodic, as $a_j \equiv a_i \pmod p$ for some $i, j $ (due to PHP). Thus, letting $t = j-i$ implies $a_{k+st} \equiv a_k$ for all $k \ge i$. Let $T$ denote the period (minimum) of sequence $a_n$. Note that: $p a_p$ is a perfect square, which implies $p | a_p$. Notice that: $$a_{n+p} = P^{(n)}(a_p) \equiv P^{(n)}(0) \equiv a_n \pmod p$$which implies $a_n$ is purely periodic. Thus: $T|p$ which implies $T = 1$ or $T=p$. If $T=1$, then $a_n \pmod p$ will be constant eventually. Notice that: $a_{np} \equiv 0 \pmod p$ which implies that, it should equal to $0$ eventually. But: $P(a_p) \equiv P(0) \pmod p$ and $P(a_p) \equiv a_p \equiv 0 \pmod p$, thus contradiction that $p|P(0)$. Therefore $T=p$. Claim: $\deg(P) \le 1$ Proof:FTSOC, assume $\deg(P) \ge 2$. Thus, note that we must have: $$\{ P(0), P(1), \cdots, P(p-1) \} = \{ 0, 1, \cdots, p-1 \}$$since $a_n$ is purely periodic modulo $p$. Let $Q(x) = P(x+1)-P(x)$ be of $\deg P -1$ polynomial with $b_n = Q(n)$. Thus, due to Schurs theorem, infinitely many primes $q$ divide $b_n$ which implies $P(n+1) \equiv P(n) \pmod q$. Taking $q$ to be a prime which is much larger than $p$, it shows that $P(n+1) = P(n)$ which contradicts that $\{ P(0), P(1), \cdots, P(p-1) \} = \{ 0, 1, \cdots, p-1 \}$. Therefore, $P(x)=ax+b$ for some $a, b$ integers. Consider $G(x)=P(x)-x$. Then, by Schur's theorem, $P(n) \equiv n \pmod p$ for infinitely many primes $p$ but this contradicts that $a_n \pmod p$ has period of length $p$, for large enough primes $p$, unless $G$ is constant. Thus: $P(x) = x+c$ and plugging back (followed by a NT-bash), we conclude with $c=1$.