Proving the identity $\Phi_{np}(x) = \Phi_n(x^p)/\Phi_n(x)$, with $p \nmid n$

Question

I've been going through the Wikipedia article on cyclotomic polynomials, trying to prove the various identities that can be used as tools to compute $\Phi_n(x)$.

One such identity that I'm not sure how to prove is the following, with $p$ prime and $p \nmid n$:

$\Phi_{np}(x) = \Phi_n(x^p)/\Phi_n(x)$.

A proof is given in Trygve Nagell's Introduction to Number Theory, but it is difficult to follow.

How might I go about proving this?

Answer 1

We need to prove that $\Phi_n(x)\Phi_{np}(x)=\Phi_n(x^p)$. The left side is squarefree and its zeros are the primitive $n$-th and $np$-th roots of unity. As $p\nmid n$ then $\zeta^p$ is a primitive $n$-th root of unity if $\zeta$ is, and it is clear that $\zeta^p$ is a primitive $n$-th root of unity if $\zeta$ is a primitive $np$-th root of unity. Conversely if $\zeta^p$ is a primitive $n$-the root of unity, then $\zeta$ has multiplicative order $n$ or $np$.

Summarising, the zeros of $\Phi_n(x)\Phi_{np}(x)$ are the $p$-th roots of the primitive $n$-th roots of unity. But these are precisely the zeros of $\Phi_n(x^p)$. As this is monic, with the same degree as $\Phi_n(x)\Phi_{np}(x)$ (why?) then these polynomials are equal.

Answer 2

The long way around.

$$x^n-1=\prod_{d\mid n} \Phi_d(x)\tag{1}$$

Substituting $x^p$ for $x$ in $(1)$ and you get:

$$x^{pn}-1=\prod_{d\mid n}\Phi_d(x^p)$$

Replacing $n$ with $np$ in $(1)$ we get $$x^{np}-1=\prod_{d\mid np}\phi_{d}(x)=\prod_{d\mid n}\Phi_d(x)\Phi_{pd}x).$$

The second equality because every $d\mid np$ can be written uniquely as either $d'$ or $d'p$ for some $d'\mid n.$

Induction proof:

We will prove by strong induction on $n.$ If true for all $n'\mid n$ with $n'\neq n.$

Then we have:

$$\prod_{d\mid n}\Phi_d(x^p)=\prod_{d\mid n}\Phi_d(x)\Phi_{pd}x).$$

Now we prove this by induction in $n$. When $d\mid n$ and $d<n$ we'd have $\Phi_d(x^p)=\Phi_d(x)\phi_{pd}(x).$ So we can remove all the terms other than $d=n$ from both sides and get the result for $n.$

You need to handle the case $n=1$ to start the induction, hence show: $$\Phi_1(x^p)=x^p-1=\Phi_1(x)\Phi_p(x),$$ which is true by (1).