$P(x)$ is irreducible so if $P(x)$ and some $R(x)$ share a root then $P(x)|R(x)$. If $x_i$, $i=1,2,3...$ are roots of $P(x)$, then $Q(x_i)=x_j$. Suppose we have $Q_1(x_1)=Q_2(x_1)$. Then $P(x)|Q_1(x)-Q_2(x)$ so $Q_1(x)=Q_2(x)$. Now $Q(x_1)$ has at most $n$ different values so there are at most $n$ polynomials $Q(x)$. Can someone see if this is correct?

@Above, seems correct The following solution is identical; posting it for storage. We prove part b) directly, implying part a) Let $\alpha$ be a root of $P$. Observe that $Q(\alpha)$ is a root of $P$. In particular, there are $n$ choices for $Q(\alpha)$. We claim that there is at most one such polynomial $Q$ for each choice. Assume FTSOC that $Q_1(\alpha) = Q_2(\alpha)$. Observe that $\gcd(Q_1 - Q_2, P)$ is nonconstant and has degree $< n$. This contradicts the irreducibility of $P$.

My favorite problem throughout the test. Pretty much similar to above. For $n = 1$, note that $Q(x)$ must be constant by the condition of the problem. Take $a$ to be the root of polynomial $P$, then $Q(x) = a$ is the only solution, which may or may not satisfy the condition dependant on whether $a \in \mathbb{Q}$ or not, and therefore there are at most one solution. Now, assume $n > 1$, then $P$ has no rational roots. WLOG $P \in \mathbb{Z}[x]$ is irreducible. Since $P(x) \mid P(Q(x))$, if $a$ is a root of $P$ then $Q(a)$ is also a root of $P$. Let $\{ x_1, x_2, \dots, x_n \}$ be the set of complex roots of $P$. Thus $Q(x_i) = x_j$ for all $1 \le i,j \le n$. Now, suppose there exists two polynomials $Q_1, Q_2 \in \mathbb{Q}[x]$ such that $Q_1(x_i) = Q_2(x_i)$. Therefore, $x - x_i \mid Q_1(x) - Q_2(x) \Rightarrow P(x) \mid Q_1(x) - Q_2(x)$ as $Q_1(x) - Q_2(x) \in \mathbb{Q}[x]$. Since $P$ is irreducible, then this forces $Q_1 = Q_2$. Therefore, there are at most one polynomial for each values of $Q(x_1)$, finishing the problem.

IndoMathXdZ wrote: Let $P(x)$ be a nonconstant polynomial of degree $n$ with rational coefficients which can not be presented as a product of two nonconstant polynomials with rational coefficients. Prove that the number of polynomials $Q(x)$ of degree less than $n$ with rational coefficients such that $P(x)$ divides $P(Q(x))$ a) is finite b) does not exceed $n$. My Solution. We know that $P$ is an irreducible polynomial, so if $\mathrm{gcd}(P, R)$ is non-constant then $P \lvert R$. We see that if $\mathbb{F}$ is the set of roots of $P$, then $Q : \mathbb{F} \rightarrow \mathbb{F}$. If $\mathbb{QF}$ is the set of all such polynomials $Q$, then $Q_i, Q_j \in \mathbb{QF}$ such that $Q_i \rightarrow Q_j = \sigma (Q_i)$ has one fixed point, then $P \lvert Q_i - Q_j$ which means that $Q_i = Q_j$, so there can exist at most $n$ polynomials $Q$.

When P2, P3 and P5 is hard, P6 gets a smoke screen. Let $Q_1,Q_2,\ldots,Q_{n+1}$ satisfies the equation. Factoring out $Q_i(x)-Q_j(x)$ does wonders! $\color{green} \rule{25cm}{2pt}$ $\color{green} \textbf{1 Claim and Done.}$ If there is a $k+1-$variabled polynomial with degree $\leq n-k$ so that \[ P \mid S_k(Q_{i_1},Q_{i_2},\ldots,Q_{i_{k+1}}) \: \forall i_a \ne i_b, 1 \leq a,b \leq k+1 \cdots (1) \]then there exists a polynomial $S_{k+1}$ with degree $\leq n-k-1$ so that the same assertion holds for $k+2$ $Q-$polynomials. $\color{green} \textbf{Proof.}$ Substracting two equations in similar form to $(1)$, \[ P \mid S_k(Q_c,Q_{i_2},\ldots,Q_{i_{k+1}}) - S_k(Q_d,Q_{i_2},\ldots,Q_{i_{k+1}}) \]We see this as a polynomial in one-variable (the first one); explicitly, let $S_k(x_1,\ldots,x_{k+1}) = S^{(k)}_{x_2,\ldots,x_{k+1}}(x_1)$. So, the above expression is equal to \[ S^{(k)}_{x_2,\ldots,x_{k+1}}(Q_c) - S^{(k)}_{x_2,\ldots,x_{k+1}}(Q_d) = (Q_c-Q_d) \cdot S_{k+1}(Q_c,Q_d,\ldots,Q_{i_{k+1}}) \]for some $S_{k+1}$. As we know that $\gcd{P,Q_c-Q_d} = 1$, then we know that \[ P \mid S_{k+1}(Q_c,Q_d,\ldots,Q_{i_{k+1}}) \]Note that this $S_{k+1}$ is equal for every $k+2-$tuple of polynomials $Q_{c},Q_d,\ldots,Q_{i_{k+1}}$, as the initial polynomial $S_k$ is equal for all initial tuples. $\blacksquare$ $\blacksquare$ $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{1 Line Finish.}$ First, we let $S_0 = P$. Applying the Lemma $n-1$ times we will reach the polynomial $S_{n-1}$ with degree at most $n-(n-1) = 1$, so that \[ P \mid k_1 \cdot Q_1+k_2 \cdot Q_2+\ldots+k_n \cdot Q_n+C \]However, repeating this for $(Q_{n+1},Q_2,\ldots,Q_n)$ yields \[ P \mid k_1 \cdot Q_{n+1}+k_2 \cdot Q_2+\ldots+k_n \cdot Q_n+C \]Substracting those two equations, we get \[ P \mid k_1 \cdot (Q_1-Q_{n+1}) \]which is impossible. $\blacksquare$ $\blacksquare$ $\blacksquare$

WLOG $P\left(x\right)$ is monic of degree $n$. Assume there exist distinct polynomials $Q_1\left(x\right),\dots,Q_{n+1}\left(x\right)\in\mathbb{Q}\left[x\right]$ such that $P\left(x\right)$ divides $P\left(Q_i\left(x\right)\right)$ for each $i$. Consider the $\left(n+1\right)\times\left(n+1\right)$ matrices \[A=\begin{bmatrix} 1 & Q_1 & Q_1^2 & \ldots & Q_1^{n-1} & P\left(Q_1\right) \\ 1 & Q_2 & Q_2^2 & \ldots & Q_2^{n-1} & P\left(Q_2\right) \\ 1 & Q_3 & Q_3^2 & \ldots & Q_3^{n-1} & P\left(Q_3\right) \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & Q_{n+1} & Q_{n+1}^2 & \ldots & Q_{n+1}^{n-1} & P\left(Q_{n+1}\right) \end{bmatrix}\]and \[B=\begin{bmatrix} 1 & Q_1 & Q_1^2 & \ldots & Q_1^{n-1} & Q_1^n \\ 1 & Q_2 & Q_2^2 & \ldots & Q_2^{n-1} & Q_2^n \\ 1 & Q_3 & Q_3^2 & \ldots & Q_3^{n-1} & Q_3^n \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & Q_{n+1} & Q_{n+1}^2 & \ldots & Q_{n+1}^{n-1} & Q_{n+1}^n \end{bmatrix}\]Since $P\left(x\right)$ is monic we have $\det\left(A\right)=\det\left(B\right)$ by column operations. Moreover $P\left(x\right)\mid\det\left(A\right)$ by the determinant formula and since $P\left(x\right)$ divides $P\left(Q_i\left(x\right)\right)$ for each $i$. Hence by Vandermonde's identity, \[P\left(x\right)\mid\det\left(A\right)=\det\left(B\right)=\prod_{i<j}\left(Q_j\left(x\right)-Q_i\left(x\right)\right)\]Since $P\left(x\right)$ is irreducible we must have $P\left(x\right)\mid Q_j\left(x\right)-Q_i\left(x\right)$ for some $i<j$. Since $\deg\left(Q_j-Q_i\right)<n$ we must have $Q_i=Q_j$, contradiction.

So basically the same solution as above like #2, but anyway, posting it for storage... First it is known that if polynomial $P$ in $\mathbb{Q}[x]$ is irreducible and other polynomial $F$ has the same root as $P$, then $P\mid F$. Also irreducible polynomials don't have double roots which can be checked also using above lemma. So if polynomial $P(x)\mid P(Q(x))$ then we get that $P(Q(x))=P(x)F(x)$ for some $F$ then by plugging roots $\omega_{i}$ in this equality we get that $P(Q(\omega_{i}))=0$ so $Q(\omega_{i}); 1\le i\le n$ is in set of roots of $P$. Now we prove $b)$ so also directly proving $a)$. Suppose we have more than $n$ distinct polynomials $Q_{1},...,Q_{t}$ such that they satisfy the condition, by pigeonhole principle we must have that for some $i$ and $j$ we have $Q_{i}(\omega_1)=Q_{j}(\omega_1)$, but by making a new polynomial $Q_{i}(x)-Q_{j}(x)$ we get that it is divisible by $P$ but it's degree is smaller so impossible unless $Q_{i}(x)-Q_{j}(x)$ is zero polynomial but then they are identical, contrary to hypothesis, done!

Suppose the roots of $P$ are $r_1,\ldots,r_k$ (counted without multiplicity), so $k \leq n$. Since $P$ is irreducible over $\mathbb{Q}[x]$, every $r_i$ must be an algebraic number of degree $n$. If $P(x) \mid P(Q(x))$, then for all $1 \leq i \leq k$, there must exist some $1 \leq j \leq k$ such that $Q(r_i)=r_j$, since otherwise we would have $P(r_i)=0$ and $P(Q(r_i))\neq 0$. I claim that $Q$ is uniquely determined by $Q(r_1)$. Indeed, suppose that we had two different polynomials $Q_1,Q_2$ of degree at most $n-1$ such that $Q_1(r_1)=Q_2(r_1)$. Then $Q_1-Q_2$ also has degree at most $n-1$ and has $r_1$ as a root. But this contradicts the fact that $r_1$ is degree $n$, hence $Q$ is unique. To finish, note that there are $k$ possibilities for $Q(r_1)$, hence there are at most $n$ choices for $Q$, as desired. $\blacksquare$

Let $P$ have distinct roots $r_1, r_2, \ldots, r_m$ for some positive integer $m\le n$. We see that there exists $j$ satisfying $Q(r_i) = r_j$ for each $1\le i\le m$. Claim: For each value of $Q(r_1)$, there is at most one possible polynomial $Q$. Proof: Suppose there were two distinct polynomials $p$ and $q$ of degree less than $n$ in $\mathbb{Q}[x]$, where $P(x)$ divides $P(p(x))$ and $P(q(x))$, and $p(r_1) = q(r_1)$. WLOG $p(r_1) = r_2$. Then we see that $r_2$ is a root of $p(x) - q(x)$, so $P(x)\mid p(x) - q(x)$. Since $p(x)$ and $q(x)$ have degree less than $n$, $p(x) - q(x)$ must be the zero polynomial, which is absurd because $p$ and $q$ are different. $\square$ The result follows because there are at most $m\le n$ possible values for $Q(r_1)$.

Chinese Antiproblems :flushed:. Claim: If $z$ is a root of $P$, then $Q(z)$ must also be a root. Proof. Follows as $P(Q(z)) = 0$. $\blacksquare$ Claim: There are at most $n$ possible $Q$. Proof. FTSOC suppose that $n + 1$ such $Q$ existed. Then by pigeonhole, for a fixed root $z$ there exist polynomials $Q_1, Q_2$ such that $Q_1(z) - Q_2(z) = 0$. It then follows that $Q_1 - Q_2$ has degree less than $n$ but has $z$ as a root, contradiction since $P$ is irreducible and thus minimal. $\blacksquare$

Let $R$ be the set of roots of $P$. Then notice that the condition implies that for any $\alpha \in R$, then $Q(\alpha) \in R$ too. Fix an $\alpha \in R$. If there are more than $n$ possible $Q$, say $Q_1, Q_2, \dots, Q_n$, then there exists $Q_1(\alpha) = Q_2(\alpha)$, hence the minimal polynomial of $\alpha$ is $\deg(Q_1-Q_2) < \deg P$, contradiction.

Here's The official solution. $\color{red}\textbf{Claim:-}$ It is known that an irreducible polynomial $P(x)$ of degree n with rational coeffcients has $n$ different complex roots which we denote by $\alpha_1,\alpha_2,..,\alpha_n$ $\color{blue}\textbf{Proof:-}$ $(a)$ If $P(x)$ divides $P(Q(x)),$ then $Q(\alpha k)$ is also a root of $P(x)$ for each$ k \le n$. It follows that the values of $Q(x)$ at $\alpha_1,\alpha_2,....\alpha_n$ form a sequence $\alpha_{i1},\alpha_{i2},.......,\alpha_{in}$, where all terms are roots of $P(x)$ not necessarily different. The number of such sequences is $n$ , and for each sequence there exists at most one polynomial $Q(x)$ such that $Q(\alpha _k) = \alpha_{ik}$ (since two polynomials of degree less than $n$ with equal values at $n$ points must coincide). $(b)$ Thus the number of possible polynomials $Q(x)$ does not exceed $n$ For each polynomial $Q(x)$ satisfying the condition, $Q(\alpha_1)$ equals one of the roots $\alpha_i$. However, there is at most one polynomial $Q(x)$ of degree less than $n$ with rational coefficients such that $Q(\alpha_1) = \alpha_i$, Indeed, if $Q_1(\alpha_1) = Q_2(\alpha_1) = \alpha_i,$ then $\alpha_1$ is a root of the polynomial $Q_1(x)-Q_2(x)$ with rational coefficients and degree less than $n.$ If this polynomial is not identically zero, its greatest common divisor with $P(x)$ is a nonconstant divisor of $P(x)$ with rational coefficients and degree less than $n,$ a contradiction. Thus the number of possible polynomials $Q(x)$ does not exceed $n.$

Let $\alpha$ be a root of $P$ and let $K=Q(\alpha) =\frac{ Q[x]}{(P)}.$ Since $P$ is irreducible it's the minimal polynomial of $\alpha$, and thus $P$ divides a polynomial $R$ iff $R(\alpha)=0. $ It follows that $P\mid P(Q)$ iff $Q(\alpha)$ is one of the roots of $P$ in $K$. In particular let $T\in Q(x) $ be an arbitrary polynomial and let $Q(x) = P(x)T(x)+x$. Then $P(Q(\alpha)) = P(P(\alpha)T(\alpha)+\alpha) = P(\alpha) = 0$. More generally, let $\{ \alpha_i \}_{i=1}^k$ be the roots of $P$ in $K$ so $k\leq n$ and this is the "at most n" in the question. For each $i$ there is a unique polynomial $R_i \in Q[x]$ of degree less than $n$ so that $\alpha_i = R_i(\alpha)$ (in the example above $R(x)=x$). Then $P | P(Q)$ iff there is $i$ so that $Q(\alpha) = \alpha_i$ iff $Q(\alpha)-R_i(\alpha) = 0$ iff $P | Q-R_i$. We conclude that $P | P(Q)$ iff there are $T\in Q[x]$ and $i$ so that $Q = PT+R_i$. Since the degree of $R_i$ is strictly less than $n$ and the degree of $PT$ is a multiple of $n$ (the degree of $P$) we see that the degree of $Q$ can be at most $n$ only if $T=0$. Thus the only choices for $Q$ are the $R_i$ themselves, and the number of solutions is exactly the number of roots of $P$ in $K.$ $\blacksquare$ Note- Here we should prove that there are at most $n$ polynomials $Q$ with rational coefficients and degree less than $n$ so that the composition $P\circ Q$ is divisible by $P$ in the ring of polynomials with rational coefficients $.$

Let $r$ be a root of $P$. If $Q_1,Q_2$ are distinct and valid and satisfy $Q_1(r)=Q_2(r)$ then $Q_1-Q_2$ has root $r$ and degree $<n$, but $P$ is the minimal polynomial of $r$, impossible. Now $P(x)\mid P(Q(x))$ implies $Q(r)$ is one of $n$ roots of $P$, so at most $n$ valid $Q$ exist, one for each root.