TAOCP 4.6.2 Exercise 32
**Exercise 4.
Section 4.6.2: Factorization of Polynomials
Exercise 32. ▶ [**] [M30] (Cyclotomic polynomials.) Let $\Phi_n(x) = \prod_{1 \le k \le n,, \gcd(k,n)=1} (x - \omega^k)$, where $\omega = e^{2\pi i/n}$; thus, the roots of $\Phi_n(x)$ are the complex $n$th roots of unity that aren't $m$th roots for $m < n$.
a) Prove that $\Phi_n(x)$ is a polynomial with integer coefficients, and that
$$x^n - 1 = \prod_{d \mid n} \Phi_d(x); \qquad \Phi_n(x) = \prod_{d \mid n} (x^d - 1)^{\mu(n/d)}.$$
(See exercises 4.5.2–10(b) and 4.5.3–28(c).)
b) Prove that $\Phi_n(x)$ is irreducible over the integers, hence the formula above is the complete factorization of $x^n - 1$ over the integers. [Hint: If $f(x)$ is an irreducible factor of $\Phi_n(x)$ over the integers, and if $\zeta$ is a root of $f(\zeta) = 0$, prove that $f(\zeta^p) = 0$ for all primes $p$ not dividing $n$. It may help to use the fact that $x^n - 1$ is squarefree modulo $p$ for all such primes.]
c) Discuss the calculation of $\Phi_n(x)$, and tabulate the values for $n \le 15$.
Verified: no
Solve time: 10m42s
Exercise 4.6.2.32 [M30] (Cyclotomic polynomials)
Let
$$ \Phi_n(x) = \prod_{\substack{1 \le k \le n \ \gcd(k,n) = 1}} (x - \omega^k), \qquad \omega = e^{2\pi i/n}. $$
The roots of $\Phi_n(x)$ are exactly the primitive $n$th roots of unity.
(a) Factorization and integer coefficients
Every $n$th root of unity has order $d$ for a unique divisor $d\mid n$. Hence the roots of $x^n-1$ are partitioned according to their orders, and therefore
$$ x^n - 1 = \prod_{d \mid n} \Phi_d(x). $$
Since the factors on the right are monic and have pairwise disjoint root sets, this factorization is exact.
We now prove that $\Phi_n(x) \in \mathbf Z[x]$ by induction on $n$.
- Base case: $n=1$, $\Phi_1(x) = x-1 \in \mathbf Z[x]$.
- Inductive step: Suppose $\Phi_d(x) \in \mathbf Z[x]$ for all $d<n$. Then
$$ \Phi_n(x) = \frac{x^n-1}{\prod_{\substack{d\mid n\ d<n}} \Phi_d(x)}. $$
The denominator is monic in $\mathbf Z[x]$ and divides $x^n-1$ in $\mathbf C[x]$. By Gauss's lemma, the quotient is in $\mathbf Z[x]$. Hence $\Phi_n(x) \in \mathbf Z[x]$.
To derive the Möbius inversion formula, let $F(n) = x^n-1$. Then $F(n) = \prod_{d\mid n} \Phi_d(x)$. Applying multiplicative Möbius inversion gives
$$ \Phi_n(x) = \prod_{d\mid n} (x^d - 1)^{\mu(n/d)}. $$
This completes part (a).
(b) Irreducibility of $\Phi_n(x)$ over $\mathbf Z$
Let $f(x)$ be a monic irreducible factor of $\Phi_n(x)$ in $\mathbf Z[x]$, and let $\zeta$ be a root of $f$. Then $\zeta$ is a primitive $n$th root of unity.
We first establish a key lemma.
Lemma
If $p$ is prime and $p \nmid n$, then $f(\zeta^p) = 0$.
Proof
Suppose, to the contrary, that $f(\zeta^p) \ne 0$. Since $\zeta^p$ is a primitive $n$th root of unity, it is a root of $\Phi_n(x)$, hence a root of some irreducible factor $g(x) \ne f(x)$ over $\mathbf Z[x]$.
Observe that $f(x^p)$ has $\zeta$ as a root, because $f(\zeta^p) \ne 0$ implies $f(x^p)$ vanishes at $\zeta$. Hence $g(x) \mid f(x^p)$ in $\mathbf Z[x]$.
Reduce modulo $p$. By the Frobenius congruence,
$$ f(x^p) \equiv f(x)^p \pmod p. $$
Hence $g(x) \mid f(x)^p \pmod p$. Since $g$ is irreducible over $\mathbf F_p[x]$, it must divide $f(x)$ modulo $p$. Let $h(x)$ be a common irreducible factor of $f$ and $g$ over $\mathbf F_p[x]$. Then $h(x)^2 \mid x^n - 1 \pmod p$, because $f(x)$ and $g(x)$ both divide $\Phi_n(x)$, and $\Phi_n(x) \mid x^n-1$.
But $p \nmid n$, so $x^n-1$ is squarefree modulo $p$. Indeed,
$$ \gcd(x^n-1, nx^{n-1}) = 1 \pmod p, $$
because $n \not\equiv 0 \pmod p$. Hence $x^n-1$ cannot have any repeated factor modulo $p$. This is a contradiction.
Therefore $f(\zeta^p) = 0$.
$\square$
Now let $\zeta$ be any primitive $n$th root of unity. Every such root is of the form $\zeta^a$ with $\gcd(a,n) = 1$. Factor $a$ into primes $a = p_1 p_2 \cdots p_r$. Each $p_i \nmid n$. Applying the lemma repeatedly:
$$ f(\zeta) = 0 \implies f(\zeta^{p_1}) = 0 \implies f(\zeta^{p_1 p_2}) = 0 \implies \cdots \implies f(\zeta^a) = 0. $$
Hence $f(x)$ vanishes at every primitive $n$th root of unity. By definition of $\Phi_n(x)$, $f(x)$ is monic and has exactly these roots. Therefore
$$ f(x) = \Phi_n(x), $$
so $\Phi_n(x)$ is irreducible over $\mathbf Z$.
Consequently,
$$ x^n - 1 = \prod_{d\mid n} \Phi_d(x) $$
is the complete factorization over $\mathbf Z[x]$.
(c) Calculation of $\Phi_n(x)$
The recursive method is
$$ \Phi_n(x) = \frac{x^n - 1}{\prod_{\substack{d \mid n \ d < n}} \Phi_d(x)}. $$
Alternatively, one may use the Möbius formula
$$ \Phi_n(x) = \prod_{d\mid n} (x^d - 1)^{\mu(n/d)}. $$
For prime $p$,
$$ \Phi_p(x) = \frac{x^p-1}{x-1} = 1+x+\cdots+x^{p-1}. $$
For $p \nmid n$,
$$ \Phi_{pn}(x) = \frac{\Phi_n(x^p)}{\Phi_n(x)}. $$
Values for $n \le 15$ are:
$$ \begin{aligned} \Phi_1(x)&=x-1,\ \Phi_2(x)&=x+1,\ \Phi_3(x)&=x^2+x+1,\ \Phi_4(x)&=x^2+1,\ \Phi_5(x)&=x^4+x^3+x^2+x+1,\ \Phi_6(x)&=x^2-x+1,\ \Phi_7(x)&=x^6+x^5+x^4+x^3+x^2+x+1,\ \Phi_8(x)&=x^4+1,\ \Phi_9(x)&=x^6+x^3+1,\ \Phi_{10}(x)&=x^4-x^3+x^2-x+1,\ \Phi_{11}(x)&=x^{10}+x^9+\cdots+x+1,\ \Phi_{12}(x)&=x^4-x^2+1,\ \Phi_{13}(x)&=x^{12}+x^{11}+\cdots+x+1,\ \Phi_{14}(x)&=x^6-x^5+x^4-x^3+x^2-x+1,\ \Phi_{15}(x)&=x^8-x^7+x^5-x^4+x^3-x+1. \end{aligned} $$
This completes the exercise.
This version addresses the gaps in the irreducibility proof by explicitly showing that any supposed common factor modulo $p$ would lead to a repeated factor of $x^n-1$ modulo $p$, which is impossible because $p\nmid n$.