# $P,R \neq 0$ are polynomials with rational coefficients. Show that there exists a polynomial $Q$ such that $P(X) | Q(R(X))$

Given any non-zero polynomials $$P,R$$ with rational coefficients, show that there exists a polynomial $$Q \neq 0$$ with rational coefficients such that $$P(X)|Q(R(X))$$. I would like to know if my solution is correct.
My solution: We will prove the result by induction on $$deg(P)$$. For $$deg(P) = 0$$, we can simply take $$Q=P$$.
Now, assume that we have proven the result for $$deg(P) < n$$, and now we will prove it for $$deg(P) = n$$.
First, if $$P$$ is reducible (over $$\mathbb{Q}$$), write $$P=H_1H_2$$, and by the induction hypothesis we have $$Q_1,Q_2$$ such that $$H_1(X) | Q_1(R(X)), H_2(X)|Q_2(R(X))$$ and therefore $$P=H_1H_2 | Q_1(R)Q_2(R)$$ so taking $$Q=Q_1Q_2$$ gives the desired result.
Now, assume that $$P$$ is irreducible. WLOG $$P$$ is monic (otherwise multiply by a rational constant, and of course it does not change the divisibility). Write, over the complex numbers, $$P= (X-\alpha_1)...(X-\alpha_n)$$. It is well known that since $$P$$ is irreducible, then each $$\alpha_i$$ appears once and only once in the factorization of $$P$$ over the complex numbers. Now, since $$\alpha_1,...,\alpha_n$$ are algebraic over $$\mathbb{Q}$$, then so are $$R(\alpha_1),...,R(\alpha_n)$$. Therefore, there are polynomials $$Q_1,...,Q_n$$ over the rational numbers such that $$Q_1(R(\alpha_1))=...=Q_n(R(\alpha_n))=0$$. So if we take $$Q=Q_1...Q_n$$ we will have $$Q(R(\alpha_1))=...=Q(R(\alpha_n))=0$$, therefore over $$\mathbb{C}$$ we have $$P=(X-\alpha_1)...(X-\alpha_n)|Q(R(X))$$ (again, because $$\alpha_1,...,\alpha_n$$ are distinct). Therefore the divisibility must also carry to $$\mathbb{Q}$$ and we are done. Is this proof correct? If so, is there a more elementary approach?

• There might be some benefit to noting that the $R(\alpha_j)$ are all conjugate under the Galois group of $P$, but it seems correct and pretty consise as it is. – Greg Martin May 30 '20 at 23:12

Looks good to me! If you want, you can avoid the induction and irreducibility argument by simply letting the $$\alpha$$'s be non-distinct. Then each $$R(\alpha_i)$$ is a root of $$Q = Q_1 \cdots Q_n$$ with the correct multiplicity (or higher), so $$P$$ divides $$Q \circ R$$.
Edit: As a silly side note, this argument even works when $$\operatorname{deg}(P) = 0$$: in that case, $$P$$ is a nonzero constant, hence has no roots, whence $$Q = 1$$ (the empty product). Then $$Q \circ R = 1$$ and indeed $$P$$ divides $$1$$.
• Do you mean to take $Q_i$ such that $R(\alpha_i)$ is a root of $Q_i$, and then raise $Q_i$ to a large power so that it reaches the desired multiplicity? – Omer May 30 '20 at 23:17
• Well that's not what I meant but that would certainly work. But as long as each $Q_i$ has $R(\alpha_i)$ as a root at all, this will be fine. You just need to list out the roots $\alpha_1, \dots, \alpha_n$ of $P$ with multiplicity, so $n = \operatorname{deg}(P)$. Now for any root $\alpha$ of $P$, let $m$ be its multiplicity. Since $\alpha$ appears $m$ times in the list of $\alpha_i$'s, there are $m$ different values of $i$ such that $R(\alpha)$ is a root of $Q_i$. Thus, $(X-R(\alpha))^m$ divides $Q$, so $(X-\alpha)^m$ divides $Q \circ R$. – diracdeltafunk May 30 '20 at 23:26