Find $f\in \mathbb{Z}_{p}\left[X\right]$ such that $f\left(X^{m}\right)$ is divisible by $\Phi_{p-1}$.

Question

Let $p$ be a prime natural number, let $m\in\left\{ 2,\,\ldots,\,p-2\right\}$ and let $\Phi_{p-1}\in \mathbb{Z}_{p}\left[X\right]$ the cyclotomic polynomial corresponding to $p-1$. Find the polynomials $f\in \mathbb{Z}_{p}\left[X\right]$ such that $f\left(X^{m}\right)$ is divisible by $\Phi_{p-1}$.

Answer 1

Note that $\Phi_{p-1}$ splits completely in $\mathbb F_p$ and its roots are the primitive roots modulo $p$. (see lemma below)

The polynomials $f\in \mathbb F_p[X]$ with $f(X^m) \equiv0\pmod{\Phi_{p-1}}$ form a (principal) ideal (kernel of evaluation homomorphism), and it is equivalent that $f$ is zero at $m$th powers of primitive roots, i.e. that $f$ is zero at elements of order $(p-1)/\gcd(m,p-1)$. These are precisely the (simple) roots of $\Phi_{(p-1)/\gcd(m,p-1)}$. (see lemma below)

So $\Phi_{p-1} \mid f(X^m)$ iff $\Phi_{(p-1)/\gcd(m,p-1)} \mid f$.

---

Lemma. For $d\mid p-1$, the polynomial $\Phi_d \pmod p$ splits completely in $\mathbb F_p$ and has simple roots which are the elements of order $d$.

Proof. $\Phi_d[X] \mid X^{p-1}-1$ so it splits completely in $\mathbb F_p$ and has simple roots. By definition, $\Phi_d \in\mathbb Z[\zeta_{p-1}][X]$ equals $\prod_{ord(\zeta)=d}(X-\zeta)$. Reducing mod $p$, we have $\mathbb Z[\zeta_{p-1}][X] \cong \mathbb F_p$ (as $\mathbb Z$-algebras) because $\mathbb F_p$ has all $(p-1)$th roots of unity.

Moreover, the order of a root of unity $\zeta$ cannot increase when reducing mod $p$, hence the roots of $\Phi_d\pmod p$ have order at most $d$.

On the other hand, $X^{p-1}-1=\prod_{e\mid p-1}\Phi_e(X)$ so all $a\in \mathbb F_p^\times$ of order $d$ are roots of some $\Phi_e$, which can only be $\Phi_d$. $\square$