# Polynomials such that $P(X)\mid P(X^2)$

I just found this problem in an old email but I have forgotten how to do it.

Find the number of monic irreducible polynomials $$P \in \mathbb{Z}[X]$$ such that $$P(X) \mid P\left(X^2\right)$$ and $$\deg(P) = 144$$.

• $X$ and $X-1$ are examples – J. W. Tanner Dec 16 '19 at 20:18
• @J.W.Tanner The problem is about such polynomials with degree 144. – Labo Dec 16 '19 at 20:43
• ... only for odd $n$. For example, $n=292$ does not work even though $\phi(292)=144$. – Robert Israel Dec 16 '19 at 20:52

## 1 Answer

If $$r$$ is a root of $$P(X)$$, it must also be a root of $$P(X^2)$$, which says $$r^2$$ is a root of $$P(X)$$. Thus squaring maps the set of roots of $$P(X)$$ into itself. This implies that all roots of $$P(X)$$ must be either $$0$$ or roots of unity. $$P(X)$$ is either $$X$$ or a cyclotomic polynomial. Moreover, you can show that only cyclotomic polynomials $$\Phi_j(X)$$ with odd $$j$$ work. Now, what odd $$j$$ have $$\Phi_j(X)$$ of degree $$144$$?

• Why is it that only odd $j$ work? Using your other observations, I could bruteforce the answer: sagecell.sagemath.org/… – Labo Dec 17 '19 at 12:22
• A root $r$ of $\Phi_j(X)$ is a primitive $j$'th root of unity. If $j$ is even, $(r^2)^{j/2} = 1$, so $r^2$ is a primitive $(j/2)$'th root of unity, not $j$'th. – Robert Israel Dec 17 '19 at 12:54
• Oh and when j is odd, 2 is invertible modulo so $r^2$ is still primitive. Nice! – Labo Dec 17 '19 at 19:08
• Here is a simpler solution that computes the answer: sagecell.sagemath.org/… – Labo Dec 17 '19 at 19:12