Theorem: Cyclotomic Polynomial of Index times Prime Power

Let $n, k \ge 1$ be natural numbers.
Let $p$ be a prime number.
Let $\Phi_n$ denote the $n$th cyclotomic polynomial.
Then $\map {\Phi_{p^k n}} x = \begin{cases}
\map {\Phi_n} {x^{p^k}} & \text{if } p \divides n\\
\dfrac {\map {\Phi_n} {x^{p^k}}} {\map {\Phi_n} {x^{p^{k - 1}}}} & \text{if } p \nmid n \end{cases}$

Proof:
Suppose $p \divides n$.
Then for all $m \in \Z$:
{{begin-eqn}}
{{eqn | l = m \perp n
      | o = \implies
      | r = m \perp n \land m \perp p
      | c = Law of Identity; Divisor of One of Coprime Numbers is Coprime to Other
}}
{{eqn | o = \implies
      | r = m \perp p^k n 
      | c = Integer Coprime to all Factors is Coprime to Whole
}}
{{eqn | o = \implies
      | r = m \perp n
      | c = Divisor of One of Coprime Numbers is Coprime to Other
}}
{{eqn | ll = \leadsto
      | l = m \perp p^k n
      | o = \iff
      | r = m \perp n
      | c = {{Defof|Biconditional}}
}}
{{end-eqn}}
Hence:
{{begin-eqn}}
{{eqn | l = \map {\Phi_{p^k n} } x
      | r = \prod_{\zeta} \paren {x - \zeta}
      | c = where the product runs over all primitive complex $p^k n$th roots of unity
}}
{{eqn | r = \prod_{\substack {1 \mathop \le m \mathop \le p^k n \\ \gcd \set {m, p^k n} = 1} } \paren {x - \map \exp {\frac {2 \pi i m} {p^k n} } }
      | c = Condition for Complex Root of Unity to be Primitive
}}
{{eqn | r = \prod_{\substack {1 \mathop \le m \mathop \le p^k n \\ \gcd \set {m, n} = 1} } \paren {x - \map \exp {\frac {2 \pi i m} {p^k n} } }
      | c = as $m \perp p^k n \iff m \perp n$
}}
{{eqn | r = \prod_{q \mathop = 0}^{p^k - 1} \prod_{\substack {1 \mathop \le r \mathop \le n \\ \gcd \set {q n + r, n} = 1} } \paren {x - \map \exp {\frac {2 \pi i \paren {q n + r} } {p^k n} } }
      | c = Writing $m = q n + r$ by Division Theorem
}}
{{eqn | r = \prod_{\substack {1 \mathop \le r \mathop \le n \\ \gcd \set {r, n} = 1} } \prod_{q \mathop = 0}^{p^k - 1} \paren {x - \map \exp {\frac {2 \pi i} {p^k} }^q \map \exp {\frac {2 \pi i r} {p^k n} } }
      | c = rearranging; GCD with Remainder
}}
{{eqn | r = \prod_{\substack {1 \mathop \le r \mathop \le n \\ \gcd \set {r, n} = 1} } \paren {x^{p^k} - \map \exp {\frac {2 \pi i r} n} }
      | c = Factorisation of $z^n - a$
}}
{{eqn | r = \prod_{\zeta} \paren {x^{p^k} - \zeta}
      | c = where the product runs over all primitive complex $n$th roots of unity; Condition for Complex Root of Unity to be Primitive
}}
{{eqn | r = \map {\Phi_n} {x^{p^k} }
      | c = {{Defof|Cyclotomic Polynomial}}
}}
{{end-eqn}}
{{qed|lemma}}
Now suppose $p \nmid n$.
We still have $p \divides p n$.
Write $p^k = p^{k - 1} p n$.
Notice that the result we proved above holds trivially for $k = 0$:
:$\map {\Phi_{p^0 n} } x = \map {\Phi_n } x = \map {\Phi_n } {x^1} = \map {\Phi_n } {x^{p^0}}$
Hence from the above:
:$\map {\Phi_{p^k n} } x = \map {\Phi_{p n}} {x^{p^{k - 1}}}$
We need the following result:
:the sets $\set {m \in \Z: m \perp p n}$ and $\set {p r: r \perp n}$ are disjoint and has union $\set {m \in \Z: m \perp n}$
First to show that they are indeed disjoint:
Suppose $x \in \set {p r: r \perp n}$.
Then $p \divides x$.
Since $p \divides p n$:
:$x \not \perp p n$
and thus:
:$x \notin \set {m \in \Z: m \perp p n}$
Hence the sets are disjoint.
Now we show that their union is indeed $\set {m \in \Z: m \perp n}$.
By Divisor of One of Coprime Numbers is Coprime to Other:
:$\forall m \in \Z: m \perp p n \implies \paren {m \perp p \land m \perp n}$
This gives:
:$\set {m \in \Z: m \perp p n} \subseteq \set {m \in \Z: m \perp n}$
Let $x \in \set {p r: r \perp n}$.
We are given that $p \perp n$.
By Integer Coprime to all Factors is Coprime to Whole:
:$x \perp n$
Hence $x \in \set {m \in \Z: m \perp n}$.
This gives:
:$\set {p r: r \perp n} \subseteq \set {m \in \Z: m \perp n}$
By Union of Subsets is Subset:
:$\set {m \in \Z: m \perp p n} \cup \set {p r: r \perp n} \subseteq \set {m \in \Z: m \perp n}$
For the other direction, we let $x \notin \set {m \in \Z: m \perp p n} \cup \set {p r: r \perp n}$.
Then by De Morgan's Laws (Set Theory)/Set Complement:
:$x \in \set {m \in \Z: m \not \perp p n} \cap \set {p r: r \not \perp n}$.
By definition of intersection:
:$x \in \set {p r: r \not \perp n}$
Thus:
:$\exists d \in \Z: d > 1: d \divides r \divides x \land d \divides n$
Therefore $x \not \perp n$.
This gives:
:$x \notin \set {m \in \Z: m \perp n}$
Hence:
:$\set {m \in \Z: m \perp n} \subseteq \set {m \in \Z: m \perp p n} \cup \set {p r: r \perp n}$
and we have our result by definition of set equality.
Therefore:
{{begin-eqn}}
{{eqn | l = \map {\Phi_{p n} } {x^{p^{k - 1} } }
      | r = \prod_{\zeta} \paren {x^{p^{k - 1} } - \zeta}
      | c = where the product runs over all primitive complex $p n$th roots of unity
}}
{{eqn | r = \prod_{\substack {1 \mathop \le m \mathop \le p n \\ m \mathop \perp p n} } \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i m} {p n} } }
      | c = Condition for Complex Root of Unity to be Primitive
}}
{{eqn | r = \prod_{\substack {1 \mathop \le m \mathop \le p n \\ m \mathop \perp n} } \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i m} {p n} } } / \prod_{\substack {1 \mathop \le p r \mathop \le p n \\ \gcd \set {r, n} = 1} } \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i m} {p n} } }
      | c = from above
}}
{{eqn | r = \prod_{\substack {1 \mathop \le m \mathop \le p n \\ m \mathop \perp n} } \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i m} {p n} } } / \prod_{\zeta} \paren {x^{p^k} - \zeta}
      | c = where the product runs over all primitive complex $n$th roots of unity; Condition for Complex Root of Unity to be Primitive
}}
{{eqn | r = \prod_{\substack {1 \mathop \le m \mathop \le p n \\ m \mathop \perp n} } \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i m} {p n} } } / \map {\Phi_n} {x^{p^{k - 1} } }
      | c = {{Defof|Cyclotomic Polynomial}}
}}
{{eqn | r = \prod_{q \mathop = 0}^{p - 1} \prod_{\substack {1 \mathop \le r \mathop \le n \\ \gcd \set {q n + r, n} = 1} } \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i \paren {q n + r} } {p n} } } / \map {\Phi_n} {x^{p^{k - 1} } }
      | c = Writing $m = q n + r$ by Division Theorem
}}
{{eqn | r = \prod_{\substack {1 \mathop \le r \mathop \le n \\ \gcd \set {r, n} = 1} } \prod_{q \mathop = 0}^{p - 1} \paren {x^{p^{k - 1} } - \map \exp {\frac {2 \pi i} p}^q \map \exp {\frac {2 \pi i r} {p n} } } / \map {\Phi_n} {x^{p^{k - 1} } }
      | c = rearranging; GCD with Remainder
}}
{{eqn | r = \prod_{\substack {1 \mathop \le r \mathop \le n \\ \gcd \set {r, n} = 1} } \paren {x^{p^k} - \map \exp {\frac {2 \pi i r} n} } / \map {\Phi_n} {x^{p^{k - 1} } }
      | c = Factorisation of $z^n - a$
}}
{{eqn | r = \prod_{\zeta} \paren {x^{p^k} - \zeta} / \map {\Phi_n} {x^{p^{k - 1} } }
      | c = where the product runs over all primitive complex $n$th roots of unity; Condition for Complex Root of Unity to be Primitive
}}
{{eqn | r = \map {\Phi_n} {x^{p^k} } / \map {\Phi_n} {x^{p^{k - 1} } }
      | c = {{Defof|Cyclotomic Polynomial}}
}}
{{end-eqn}}
as required.
{{qed}}
Category:Cyclotomic Polynomials
bfpzg3nvi0k44pocm217165uhcntqfo