# Olympiad problem :Integer roots of $P(P(x))$ in function of the roots of $P(x)$

Here is the original problem :

A polynomial $$P(x)$$ of degree $$n \geq 5$$ with integer coefficients and $$n$$ distinct integer roots is given. Find all integer roots of $$P(P(x))$$ given that $$0$$ is a root of $$P(x)$$.

Here is my solution, however i'm not sure of it , could you guys please check it ?

Solution :

It's easy to see that $$P(P(x))=0$$ for all $$x=x_1,..,x_n$$. The other roots that $$P(P(x))$$ may have are the eventual values $$X_j$$ for which $$P(X_j)=x_j, j\neq 1$$ (and those $$X_j$$ must be integers.) We have $$P(0)=0$$ so obviously $$P(x)=a_nx^n+..+a_1x$$. For all integers $$a,b$$ : $$a-b\mid P(a)-P(b)$$, since $$P\in\mathbb Z[x]$$. Taking $$a=X_j$$ and $$b=x_j$$ (for $$i=2,..,n$$, this is just : $$X_j-x_j\mid x_j$$. This means there exists some integer $$k>1$$ such that: $$X_j=kx_j$$, for all $$2\le i\le n$$. We have : $$P(x_j)=a_nx_j^n+..+a_1x_j$$. Thus : $$P(X_j)=P(kx_j)=a_nk^nx_j^n+..+a_1kx_j=x_j\Longleftrightarrow$$ $$a_nk^nx_j^{n-1}+..+a_1k=1$$. Thus : $$a_nk^{n-1}x_j^{n-1}+..+a_1=\frac{1}{k}$$. But $$P$$ has integer coefficients and $$k,x_j$$ are integers, so $$\frac{1}{k}$$ must be an integer, so $$k=1\Longrightarrow X_j=x_j$$, so the integer roots of $$P(P(x))$$ are the same as those of $$P(x)$$.

Thanks a lot !

• How do you conclude $X_j = kx_j$? From $X_j-x_j | x_j$ it follows that kX_j = (k+1)x_j$for some integer$k$. Or did I misunderstand something? – MichalisN Jan 14 at 20:29 • Oh i see, such a stupid error, thanks a lot ! :) – 1 2 3 Jan 14 at 20:50 • Just editted my answer for clarity – Mike Jan 14 at 22:10 • I actually, i think we could have used the fact that$\frac{k+1}{k}x_j=X_j$. For instance, we may write$P(x)=xQ(x)$since$0$is a root of$P$. It follows that$P(X_i)=x_i$if and only if,$X_iQ(X_i)=x_i$so$Q(X_i)=\frac{x_i}{X_i}$.$Q$has integer coefficients, so the fraction must be an integer, so$\frac{k}{k+1}$is an integer, so$k=0$. This means$X_j=x_j\$. – 1 2 3 Jan 15 at 14:31

So $$P(x)=x\prod_{i=2}^n (x-x_i)$$ where $$x_2,\ldots, x_n$$ are the nonzero integral roots of $$P$$. Now suppose there is a a nonzero root $$y$$ of $$P(P(x))$$ that is distinct from $$0,x_2,\ldots, x_n$$. Then $$y\prod_{i=2}^n(y-x_i)$$ must be in $$\{x_2,x_3,\ldots, x_n\}$$. We show that this is impossible for integral $$y \not = 0,x_2,\ldots, x_n$$ via Claim 1 below:

Claim 1: Let us use the notation as above, and let us write $$x_n$$ be the root of $$P$$ with the largest modulus i.e., $$|x_n| \ge |x_i|$$ for each $$i=2,3,\ldots, n$$. Let $$y$$ be a nonzero integer. Then $$|P(y)| > |x_n|$$.

Case 1: $$0< |y| \le \frac{|x_n|}{2}$$. Then $$|y\prod_{i=2}^n (y-x_i)| > |x_n|$$. Indeed, that $$y$$ is distinct from $$0,x_2,\ldots, x_n$$ implies $$|y|$$ and $$|y-x_i|$$ for each $$i=2, \ldots, n-2$$ is at least 1, and that at least 2 of $$\{|y|, |y-x_i|; i=2,\ldots, n-1\}$$ is at least 2, since the degree $$n$$ of $$P$$ is at least 5. So $$|y\prod_{i=2}^{n-1}(y-x_i)|$$ is at least 4. But then indeed as $$|y| \le \frac{|x_n|}{2}$$ it follows that $$|y-x_n|$$ is at least $$\frac{|x_n|}{2}$$, this implies that

$$|y\prod_{i=2}^{n} (y-x_i)| \ge \frac{|x_n|}{2} \times |y\prod_{i=2}^{n-1}(y-x_i)|$$

$$\ge \frac{|x_n|}{2} \times 4 > |x_n|.$$

So Claim 1 follws for Case 1.

Case 2: $$|y| \ge \frac{|x_n|}{2}$$. Then $$|y\prod_{i=2}^n (y-x_i)| > |x_n|$$. Indeed, that $$y$$ is distinct from $$0,x_2,\ldots, x_n$$ implies $$|y-x_i|$$ for each $$i=2, \ldots, n$$ is at least 1, and that $$|y-x_i| \ge 2$$ for at least 2 of the other $$i$$s in $$2,\ldots, n$$, since the degree $$n$$ of $$P$$ is at least 5. So $$|\prod_{i=2}^{n}(y-x_i)|$$ is at least 4. But then indeed as $$|y|$$ is at least $$|x_n/2|$$, this implies that

$$|y\prod_{i=2}^{n} (y-x_i)| \ge \frac{|x_n|}{2} \prod_{i=2}^{n}|(y-x_i)|$$

$$\ge \frac{|x_n|}{2} \times 4 > |x_n|.$$

So Claim 1 follows for the remaining Case 2 as well, thus Claim 1 follows.