Number of Polynomial Q such that P(x) | P(Q(x))

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Number of Polynomial Q such that P(x) | P(Q(x))

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IZHO 2021 P6

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

694 posts

#1 h Jan 9, 2021, 1:24 PM • 4 Y

Y by Rounak_iitr, Mango247, Mango247, Mango247

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

Igore

#2 h Jan 9, 2021, 1:37 PM • 9 Y

Y by MazeaLarius, Mathematicsislovely, Kobayashi, mijail, Assassino9931, hakN, Rounak_iitr, bin_sherlo, farhad.fritl

$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?

This post has been edited 1 time. Last edited by Igore, Jan 9, 2021, 1:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

442 posts

#3 h Jan 9, 2021, 4:12 PM • 4 Y

Y by MazeaLarius, Atpar, Mathematicsislovely, Assassino9931

@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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

694 posts

#4 h Jan 10, 2021, 3:49 PM • 2 Y

Y by mathingbingo, Rounak_iitr

My favorite problem throughout the test. :-D

:-D

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.

Some failed attempts and fakesolve

Here's a fakesolve since we assume divisibility on complex numbers:

Fakesolve wrote:

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$ .

Suppose $Q(a) = a$ for some root $a$ , then $(x - a) \mid Q(x) - x$ , forcing $P(x) \mid Q(x) - x$ , a contradiction unless $Q(x) = x$ for all $x \in \mathbb{R}$ .

Claim 01. The map $Q : \{ x_1, x_2, \dots, x_n \} \to \{ x_1, x_2, \dots, x_n \}$ is injective.
Proof. Draw a graph where we denote the set of roots of polynomial $P$ as the vertices of the graph. Now, notice that there are $n$ edges and $n$ vertices, and therefore this graph is not a tree, and hence, this graph contains a cycle. Now, consider the minimal length of the cycle $\ell$ .
This means that $Q^{\ell}(x_i) = x_i$ for some $1 \le i \le n$ . Therefore,
$x - x_i \mid Q^{\ell}(x) - x$ Since $Q^{\ell}(x) - x \in \mathbb{Q}[x]$ , this forces $P(x) \mid Q^{\ell}(x) - x$ as $P$ is the minimal polynomial of $x_i$ . Therefore, $Q^{\ell}(a) = a$ for all $a$ . This is enough to prove that this map $Q$ is injective.

Claim 02. Let $\ell$ be the minimal positive integer such that $Q^{\ell}(x_i) = x_i$ for all $1 \le i \le n$ . Then $\ell = 1$ or $\ell = 2$ .
Proof. This can be described as a cycle of length $\ell$ . Now consider such cycle where $\ell > 1$ .
$x_1 \mapsto x_2 \mapsto x_3 \mapsto \dots \mapsto x_{\ell} \mapsto x_1$ We have $x_{k + 1} - x_k \mid Q(x_{k + 1}) - Q(x_k) = x_{k + 2} - x_{k + 1}$ for all $1 \le k \le \ell$ where indices is considered modulo $\ell$ . Therefore, we conclude that
$x_1 - x_2 \mid x_2 - x_3 \mid \dots \mid x_{\ell - 1} - x_{\ell} \mid x_{\ell} - x_1 \mid x_1 - x_2$ This gives us $|x_1 - x_2| = |x_2 - x_3| = \dots = |x_{\ell} - x_1|$ . Since we assume that there are no double root (since $P$ is irreducible, all complex roots are unique), then we can proved that either $\ell = 2$ ( $x_1 - x_2 = x_3 - x_2$ ) or $\ell = 1$ ( $x_1 - x_2 = x_2 - x_3 = x_3 - x_4 = \dots = x_{\ell} - x_1 = a$ ).

If $\ell = 1$ , then $Q(x) = x$ for all $x \in \mathbb{R}$ (which we have discussed before.)
This has solved the problem for odd $n$ , as we must have $\ell \mid n$ .
If $\ell = 2$ , then $P(x) \mid Q(Q(x)) - x$ . Now, divide the set of roots into cycles of length $2$ :
$(a_1, b_1), (a_2, b_2), \dots, (a_j, b_j)$ where $a_i \mapsto b_i \mapsto a_i$ for all $1 \le i \le j$ .

Claim 03. $a_i + b_i$ is constant for all $1 \le i \le j$ .
Proof. Since $a_i - a_j \mid Q(a_i) - Q(a_j) = b_i - b_j \mid Q(b_i) - Q(b_j) = a_i - a_j$ , we conclude that $|a_i - a_j| = |b_i - b_j|$ and from $a_i - b_j \mid Q(a_i) - Q(b_j) = a_j - b_i \mid Q(a_j) - Q(b_i) = a_i - b_j$ , we conclude that $|a_i - b_j| = |b_i - a_j|$ for all $1 \le i,j \le n$ .

Now, we just need to check $4$ cases:
If $a_i - a_j = b_i - b_j$ and $a_i - b_j = b_i - a_j$ , then we have $a_i = b_i$ and $a_j = b_j$ , a contradiction.
If $a_i - a_j = b_i - b_j$ and $a_i - b_j = a_j - b_i$ , then we have $b_i = b_j$ , a contradiction.
If $a_i - a_j = b_j - b_i$ and $a_i - b_j = b_i - a_j$ , then we have $a_i = b_j$ , a contradiction.
If $a_i - a_j = b_j - b_i$ and $a_i - b_j = a_j - b_i$ , then we have $a_i + b_i = a_j + b_j$ for any $1 \le i \le j \le \ell$ .

Thus, we conclude that $a_i + b_i = c$ for all $1 \le i \le \ell$ .
This gives us $Q(x_i) = c - x_i$ for all $1 \le i \le n$ . Therefore, $P(x) \mid Q(x) - x + c$ , forcing $Q(x) = c - x$ for maximal $n - 1$ number of constants $c$ : that is, $a_1 + a_i$ where $2 \le i \le n$ .

Therefore, we have at most $n$ polynomials $Q \in \mathbb{Q}[x]$ that satisfy the condition.

Stuffs I tried

This post has been edited 4 times. Last edited by IndoMathXdZ, Jan 11, 2021, 7:25 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

126 posts

#5 h Jan 10, 2021, 5:57 PM • 1 Y

Y by Rounak_iitr

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

110 posts

#6 h Jan 15, 2021, 2:25 AM • 6 Y

Y by Math_olympics, amar_04, mijail, David-Vieta, guptaamitu1, Rounak_iitr

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$
Short motivational remarks for Short Solution.

Attachments:

2INA11-11-13.pdf (388kb)

This post has been edited 1 time. Last edited by alexiaslexia, Jan 15, 2021, 2:26 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1477 posts

math90

#7 h Jan 15, 2021, 9:11 AM • 1 Y

Y by guptaamitu1

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

38 posts

#8 h May 14, 2021, 10:48 PM • 3 Y

Y by Rounak_iitr, Mango247, Mango247

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!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#9 h Dec 11, 2022, 9:02 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5608 posts

#10 h Aug 8, 2023, 1:01 AM

Y by

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)$ .

This post has been edited 1 time. Last edited by megarnie, Aug 8, 2023, 1:02 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1541 posts

#11 h Sep 5, 2023, 8:00 PM • 1 Y

Y by Rounak_iitr

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8866 posts

#12 h Oct 13, 2023, 3:17 PM • 1 Y

Y by Rounak_iitr

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.

This post has been edited 2 times. Last edited by HamstPan38825, Oct 13, 2023, 3:20 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

456 posts

#15 h Dec 31, 2023, 6:18 PM

Y by

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.$

This post has been edited 1 time. Last edited by Rounak_iitr, Jan 15, 2024, 1:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

642 posts

#17 h Jul 4, 2024, 12:46 PM • 2 Y

Y by GeoKing, MS_asdfgzxcvb

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 $.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1745 posts

OronSH

#18 h Jan 22, 2025, 9:29 AM • 2 Y

Y by MS_asdfgzxcvb, megarnie

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1921 posts

#19 h Feb 10, 2025, 4:34 PM • 1 Y

Y by OronSH

Let $\alpha_1,\alpha_2,\dots,\alpha_n$ be the roots of $P(x)$ . Then $\alpha_1$ is a root of $P(Q(x))$ , so $Q(\alpha_1)=\alpha_k$ for some $k$ . For each $k$ , there exists at most one such polynomial (since the difference between two of them would need to be a multiple of $P$ ), done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#20 h Apr 20, 2025, 2:24 AM

Y by

Note that we clearly require all of the roots of $P$ to be complex. Let $z_1, z_2, \dots, z_n$ be the $n$ roots. For every $i,$ we require $Q(z_i) = z_j$ for some $j.$ Now, suppose there existed more than $n - 1$ such polynomials. By PHP, there must exist $Q_1, Q_2$ that work and $Q_1(z_1) = Q_2(z_1).$ If we subtract, then $Q_1(X) - Q_2(X)$ is a rational polynomial with root $z_1.$ However, $P$ is the minimal polynomial of $z_1,$ as $P$ is irreducible. Thus, $P\mid Q_1 - Q_2,$ implying $Q_1 = Q_2$ due to degree. This finishes.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a