Exercise 4.3.26* (Cyclotomic polynomials)

Proof.

(a)

Let ${𝕌}_n$ denote the set of $n$-th roots of unity. By Problem 26, $${𝕌}_n=\{\zeta \in ℂ\mid {\zeta }^n=1\}=\{1,\xi ,{\xi }^2,\dots ,{\xi }^{n-1}\}(\text{ where }\xi =e^{2\mathit{i\pi }∕n}).$$

Then ${𝕌}_n$ is a subgroup of $({ℂ}^{\text{∗}},\times )$ of order $n$.

By definition,

$${\Phi }_n(x)=\underset{\zeta \in A_n}{\prod }(x-\zeta ),$$

where $A_n$ is the subset of ${𝕌}_n$ of the elements of order $n$ in the group $({𝕌}_n,\times )$:

$$A_n=\{\zeta \in {𝕌}_n\mid \mathrm{ord}(\zeta )=n\}.$$

(Here $x$ is not a complex number, but the variable (indeterminate) of the ring $ℂ[x]$.)

By Problem 25, if $\zeta =e^{2\mathit{i\pi a}∕n}$, then $\mathrm{ord}(\zeta )=\frac{n}{n\wedge a}$, so $\mathrm{ord}(\zeta )$ divides $n$ (this is also a consequence of the Lagrange’s Theorem).

If $d\mid n$, then ${𝕌}_d\subset {𝕌}_n$: if ${\zeta }^d=1$, then ${\zeta }^n={({\zeta }^d)}^{n∕d}=1$. Therefore, for all divisors $d$ of $n$,

$$\begin{array}{llll}\hfill {\Phi }_d(x)& =\underset{\zeta \in A_d}{\prod }(x-\zeta ),\text{ where}& \hfill & \\ \hfill A_d& =\{\zeta \in {𝕌}_d\mid \mathrm{ord}(\zeta )=d\}=\{\zeta \in {𝕌}_n\mid \mathrm{ord}(\zeta )=d\}\subset {𝕌}_n.& \hfill & \end{array}$$

Since the order of every element of ${𝕌}_n$ divides $n$,

$${𝕌}_n=\underset{d\mid n}{\bigcup }{A}_d\text{(disjoint union)}.$$

Therefore

$$\begin{array}{llll}\hfill x^n-1& =\underset{\zeta \in {𝕌}_n}{\prod }(x-\zeta )& \hfill & \\ \hfill & =\underset{d\mid n}{\prod }\underset{\zeta \in A_d}{\prod }(x-\zeta )& \hfill & \\ \hfill & =\underset{d\mid n}{\prod }{\Phi }_d(x).& \hfill & \end{array}$$

This shows that

$$\begin{array}{lll}\hfill x^n-1=\underset{d\mid n}{\prod }{\Phi }_d(x).& & \hfill \text{(1)}\end{array}$$

This equality in $ℂ[x]$ shows that for every $z\in ℂ$, $z^n-1={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n}{\Phi }_d(z)$.

Note: by comparing the degrees, we obtain anew $n={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n}\varphi (d)$.

(b)

Using the Möbius multiplicative inversion formula in the group $ℂ{(x)}^{\text{∗}}$ of nonzero rational fractions (where $f(n)={\Phi }_n(x)$, and $F(n)={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n}f(d)=x^n-1$), we obtain $$\begin{array}{llll}\hfill {\Phi }_n(x)& =f(n)& \hfill & \\ \hfill & =\underset{d\mid n}{\prod }F{(d)}^{\mu (n∕d)}& \hfill & \\ \hfill & =\underset{d\mid n}{\prod }{(x^d-1)}^{\mu (n∕d)}.& \hfill & \end{array}$$

So

$$\begin{array}{lll}\hfill {\Phi }_n(x)=\underset{d\mid n}{\prod }{(x^d-1)}^{\mu (n∕d)}.& & \hfill \text{(2)}\end{array}$$

(c) We show by strong induction that the coefficients of ${\Phi }_n(x)$ are integers. Let $\mathbb{Z}[x]$ denote the ring of polynomials in $\mathbb{Q}[x]$ with integers coefficients.

First ${\Phi }_1(x)=x-1\in \mathbb{Z}[x]$. Suppose now that ${\Phi }_k(x)\in \mathbb{Z}[x]$ for all positive integers $k<n$.

By equality (1),

$$x^n-1={\Phi }_n(x)\underset{d\mid n,d\ne n}{\prod }{\Phi }_d(x),$$

where ${\prod <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n,d\ne n}{\Phi }_d(x)\in \mathbb{Z}[x]$ by the induction hypothesis.

Then ${\Phi }_n(x)=A(x)∕B(x)$, where $A(x)=x^n-1,B(x)={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n,d\ne n}{\Phi }_d(x)\in \mathbb{Z}[x]$ are monic polynomials (polynomials whose leading coefficients is $1$).

The algorithm of the Euclidean division shows that if $A(x),B(x)$ are in $\mathbb{Z}[x)$, where $B(x)\ne 0$ is a monic polynomial, then there exist polynomials $Q(x),R(x)$ in $\mathbb{Z}[x]$ such that

$$A(x)=B(x)Q(x)+R(x),R(x)=0\text{ or }\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(R)<\mathrm{deg}<!--\; FUNCTION\; APPLICATION\; -->(B).$$

Since ${\Phi }_n(x)\in \mathbb{Q}[x]$, $B(x)$ divides $A(x)$ in the ring $\mathbb{Q}[x]$. Comparing

$$A(x)=B(x)Q(x)+R(x),A(x)=B(x){\Phi }_n(x)+0,$$

the unicity of the Euclidean division in $\mathbb{Q}[x]$ shows that $R(x)=0$ and ${\Phi }_n(x)=Q(x)\in \mathbb{Z}[x]$. Therefore the coefficients of ${\Phi }_n(x)$ are integers, and the induction is done.

For all positive integers $n$, the coefficients of ${\Phi }_n(x)$ are integers. □