Properties of Cyclotomic Polynomials

Background in Basic Field Theory

Let $K$ be a field (in this post we mostly assume that $K \supset \mathbb{Q}$) and $n$ an integer $>1$ which is not divisible by the characteristic of $K$. Then the polynomial

$$X^n-1$$

is separable because its derivative is $nX^{n-1} \ne 0$. Hence in the algebraic closure $\overline{K}$, the polynomial has $n$ distinct roots, which forms a group $U$, and is cyclic. In fact, as an exercise, one can show that, for a field $k$, any subgroup $U$ of the multiplicative group $k^\ast$ is a cyclic group.

The generator $\zeta_n$ of $U$ is called the primitive $n$-th root of unity. Let $K=\mathbb{Q}$ and $L$ be the smallest extension that contains all elements of $U$, then we have $L=\mathbb{Q}(\zeta_n)$. As a matter of fact, $L/K$ is a Galois extension (to be shown later), and the cyclotomic polynomial $\Phi_n(X)$ is the irreducible polynomial of $\zeta_n$ over $\mathbb{Q}$. We first need to find the degree $[L:K]$.

Proposition 1. Notation being above, $L/K$ is Galois, the Galois group $\operatorname{Gal}(L/K) \cong (\mathbb{Z}/n\mathbb{Z})^\ast$ (the group of units in $\mathbb{Z}/n\mathbb{Z}$) and $[L:K]=\varphi(n)$.

Let’s first elaborate the fact that $|(\mathbb{Z}/n\mathbb{Z})^\ast|=\varphi(n)$. Let $[0],[1],\dots,[n-1]$ be representatives of $\mathbb{Z}/n\mathbb{Z}$. An element $[x]$ in $\mathbb{Z}/n\mathbb{Z}$ is a unit if and only if there exists $[y]$ such that $[xy]=[1]$, which is to say, $xy \equiv 1 \mod n$. Notice that $xy \equiv 1 \mod n$ if and only if $xy+mn=1$ for some $y,n \in \mathbb{Z}$, if and only if $\gcd(x,n)=1$. Therefore $|(\mathbb{Z}/n\mathbb{Z})^\ast|=\varphi(n)$ is proved.

The proof can be produced by two lemmas, the first of which is independent to the characteristic of the field.

Lemma 1. Let $k$ be a field and $n$ be not divisible by the characteristic $p$. Let $\zeta=\zeta_n$ be a primitive $n$-th root of unity in $\overline{k}$, then $(\mathbb{Z}/n\mathbb{Z})^\ast \supset \operatorname{Gal}(k(\zeta)/k)$ and therefore $[k(\zeta):k] \le \varphi(n)$. Besides, $k(\zeta)/k$ is a normal abelian extension.

Proof. Let $\sigma$ be an embedding of $k(\zeta)$ in $\overline{k}$ over $k$, then

$$(\sigma\zeta)^n=\sigma(\zeta^n)=\sigma(1)=1$$

so that $\sigma\zeta$ is also an $n$-th root of unity also. Hence $\sigma\zeta=\zeta^i$ for some $i=i(\sigma)$, uniquely determined modulo $n$. It follows that $\sigma$ maps $k(\zeta)$ into itself. This is to say, $k(\zeta)$ is normal over $k$. Let $\tau$ be another automorphism of $k(\zeta)$ over $k$ then

$$\sigma\tau\zeta=\zeta^{i(\sigma)i(\tau)}.$$

It follows that $i(\sigma)$ and $i(\tau)$ are prime to $n$ (otherwise, $\sigma\zeta$ would have a period smaller than $n$, implying that the period of $\zeta$ is smaller than $n$, which is absurd). Therefore for each $\sigma \in \operatorname{Gal}(k(\zeta)/k)$, $i(\sigma)$ can be embedded into $(\mathbb{Z}/n\mathbb{Z})^\ast$, thus proving our theorem. $\square$

It is easy to find an example with strict inclusion. One only needs to look at $k=\mathbb{R}$ or $\mathbb{C}$.

Lemma 2. Let $\zeta=\zeta_n$ be a primitive $n$-th root of polynomial over $\mathbb{Q}$, then for any $p \nmid n$, $\zeta^p$ is also a primitive $n$-th root of unity.

Proof. Let $f(X)$ be the irreducible polynomial of $\zeta$ over $\mathbb{Q}$, then $f(X)|(X^n-1)$ by definition. As a result we can write $X^n-1=f(X)h(X)$ where $h(X)$ has leading coefficient $1$. By Gauss’s lemma, both $f$ and $h$ have integral coefficients.

Suppose $\zeta^p$ is not a root of $f$. Since $(\zeta^p)^n-1=(\zeta^n)^p-1=0$, it follows that $\zeta^p$ is a root of $h$, and $\zeta$ is a root of $h(X^p)$. As a result, $f(X)$ divides $h(X^p)$ and we write

$$h(X^p)=f(X)g(X).$$

Again by Gauss’s lemma, $g(X)$ has integral coefficients.

Next we reduce these equations in $\mathbf{F}_p=\mathbb{Z}/p\mathbb{Z}$. We firstly have

$$\overline{f}(X)\overline{g}(X)=\overline{h}(X^p).$$

By Fermat’s little theorem $a^p=a$ for all $a \in \mathbf{F}_q$, we also have

$$\overline{h}(X^p)=\overline{h}(X)^p.$$

Therefore

$$\overline{f}(X)\overline{g}(X)=\overline{h}(X)^p,$$

which implies that $\overline{f}(X)|\overline{h}(X)^p$. Hence $\overline{f}$ and $\overline{h}$ must have a common factor. As a result, $X^n-\overline{1}=\overline{f}(X)\overline{h}(X)$ has multiple roots in $\mathbf{F}_p$, which is impossible because of our choice of $p$. $\square$

Now we are ready for Proposition 1.

Proof of Proposition 1. Since $\mathbb{Q}$ is a perfect field, $\mathbb{Q}(\zeta)/\mathbb{Q}$ is automatically separable. This extension is Galois because of lemma 1. By lemma 1, it suffices to show that $[\mathbb{Q}(\zeta):\mathbb{Q}] \ge \varphi(n)$.

Recall in elementary group theory, if $G$ is a finite cyclic group of order $m$ and $x$ is a generator of $G$, then the set of generators consists elements of the form $x^\nu$ where $\nu \nmid m$. In this occasion, if $\zeta$ generates $U$, then $\zeta^p$ also generates $U$ because $p \nmid n$. It follows that every primitive $n$-th root of unity can be obtained by raising $\zeta$ to a succession of prime numbers that do not divide $n$ (as a result we obtain exactly $\varphi(n)$ such primitive roots). By lemma 2, all these numbers are roots of $f$ in the proof of lemma 2. Therefore $\deg f = [L:K] \ge \varphi(n)$. Hence the proposition is proved. $\square$

We will show that $f$ in the proof lemma 2 is actually the cyclotomic polynomial $\Phi_n(x)$ you are looking for. The following procedure works for all fields where the characteristic does not divide $n$, but we assume characteristic to be $0$ for simplicity.

We have

$$X^n-1=\prod_{\zeta}(X-\zeta),$$

where the product is taken over all $n$-th roots of unity. Collecting all roots with the same period $d$ (i.e., those $\zeta$ such that $\zeta^d=1$), we put

$$\Phi_d(X)=\prod_{\operatorname{period} \zeta=d}(X-\zeta).$$

Then

$$X^n-1=\prod_{d|n}\Phi_d(X).$$

It follows that $\Phi_1(X)=X-1$ and

$$\Phi_n(X)=\frac{X^n-1}{\prod_{d\mid n}^{d<n}\Phi_d(X)}.$$

This presentation makes our computation much easier. But to understand $\Phi_n$, we still should keep in mind that the $n$-th cyclotomic polynomial is defined to be

$$\Phi_n(X)=\prod_{\operatorname{period}\zeta=n}(X-\zeta),$$

whose roots are all primitive $n$-th roots of unity. As stated in the proof of proposition 1, there are $\varphi(n)$ primitive $n$-th roots of unity, and therefore $\deg\Phi_n(X)=\varphi(n)$. Besides, $f|\Phi_n$. Since both have the same degree, these two polynomials equal. It also follows that $\sum_{d|n}\varphi(n)=n$.

Proposition 2. The cyclotomic polynomial is irreducible and is the irreducible polynomial of $\zeta$ over $\mathbb{Q}$, where $\zeta$ is a primitive $n$-th root of unity.

We end this section by a problem in number fields, making use of what we have studied above.

Problem 0. A number field $F$ only contains finitely many roots of unity.

Solution. Let $\zeta \in F$ be a root of unity with period $n$. Then $\Phi_n(\zeta)=0$ and therefore $[\mathbb{Q}(\zeta):\mathbb{Q}]$ has degree $\varphi(n)$. Since $\mathbb{Q}(\zeta)$ is also a subfield of $F$, we also have $\varphi(n) \le [F:\mathbb{Q}]$. Since $\{n:\varphi(n) \le [F:\mathbb{Q}]\}$ is certainly a finite set, the number of roots of unity lie in $F$ is finite. $\square$

Technical Computations

We will do some dirty computation in this section.

Problem 1. If $p$ is prime, then $\Phi_p(X)=X^{p-1}+X^{p-2}+\dots+1$, and for an integer $\nu \ge 1$, $\Phi_{p^\nu}(X)=\Phi_p(X^{p^{\nu-1}})$.

Solution. The only integer $d$ that divides $p$ is $1$ and we can only have

$$\Phi_p(X)=\frac{X^p-1}{\Phi_1(X)}=X^{p-1}+\dots+1.$$

For the second statement, we use induction on $\nu$. When $\nu=1$ we have nothing to prove. Suppose now

$$\Phi_{p^\nu}(X)=\Phi_p(X^{p^{\nu-1}}) =\frac{X^{p^{\nu}}-1}{X^{p^{\nu-1}}-1} =\frac{X^{p^{\nu}}-1}{\prod_{r=0}^{\nu-1}\Phi_{p^{r}}(X)}$$

is proved, then $X^{p^\nu}-1=\prod_{r=0}^{\nu}\Phi_{p^r}(X)$ and therefore

$$\begin{aligned} \Phi_{p^{\nu+1}}(X)&=\frac{X^{p^{\nu+1}}-1}{\prod_{r=0}^{\nu}\Phi_{p^r}(X)} \\ &=\frac{X^{p^{\nu+1}}-1}{X^{p^{\nu}}-1} \\ &=\Phi_p(X^{p^\nu}). \end{aligned}$$

Problem 2. Let $p$ be a prime number. If $p \nmid n$, then

$$\Phi_{pn}(X)=\frac{\Phi_n(X^p)}{\Phi_n(X)}.$$

Solution. Assume $p \nmid n$ first. It holds clearly for $n=1$. Suppose now the statement holds for all integers $<n$ that are prime to $p$. We see

$$\begin{aligned} \frac{\Phi_n(X^p)}{\Phi_n(X)} &= \frac{X^{pn}-1} {\prod_{d|n}^{d<n}\Phi_d(X^p)}\frac{\prod_{d|n}^{d<n}\Phi_d(X)}{X^n-1} \\ &= \frac{X^{pn}-1}{(X^n-1)\prod_{d|n}^{d<n}\Phi_{dp}(X)} \\ &= \frac{X^{pn}-1}{\prod_{d|n}\Phi_d(X)\prod_{d|n}^{d<n}\Phi_{dp}(X)} \\ &=\Phi_{np}(X). \end{aligned}$$

Problem 3. If $n$ is an odd number $>1$, then $\Phi_{2n}(X)=\Phi_n(-X)$.

Solution. By problem 2, $\Phi_{2n}(X)=\Phi_n(X^2)/\Phi_n(X)$. To show the identity it suffices to show that

$$\Phi_n(X)\Phi_n(-X)=\Phi_n(X^2).$$

For $n=3$ we see

$$\begin{aligned} \Phi_3(X)\Phi_3(-X) &= (X^2+X+1)(X^2-X+1) \\ &=(X^2+1)^2-X^2 \\ &=X^4+X^2+1 \\ &=\Phi_3(X^2). \end{aligned}$$

Now suppose it holds for all odd numbers $3 \le d < n$, then

$$\begin{aligned} \Phi_n(X)\Phi_n(-X) &= \frac{(X^n-1)(-X^n-1)}{ (X-1)(-X-1)\prod_{3\le d < n}^{d|n}\Phi_d(X)\Phi_d(-X) } \\ &= \frac{-(X^{2n}-1)}{-(X^2-1)\prod_{3 \le d < n}^{d|n} \Phi_d(X^2)} \\ &= \Phi_n(X^2). \end{aligned}$$

The following problem would not be very easy without the Möbius inversion formula so we will use it anyway. Problems above can also be deduced from this formula. Let $f:\mathbb{Z}_{\ge 0} \to \mathbb{Z}_{\ge 0}$ be a function and $F(n)=\prod_{d|n}f(d)$, then the Möbius inversion formula states that

$$f(n)=\prod_{d|n}F(n/d)^{\mu(d)}$$

with

$$\mu(n)=\begin{cases} 0 & \text{if $n$ is divisible by $p^2$ for some prime $p$}, \\ (-1)^r & \text{if $n$ is a product of $r$ distinct primes,} \\ 1 & \text{if $n=1$.} \end{cases}$$

Putting $f(d)=\Phi_d(X)$, we see

$$\Phi_n(X)=\prod_{d|n}(X^{n/d}-1)^{\mu(d)}.$$

Now we proceed.

Problem 4. If $p|n$, then $\Phi_{pn}(X)=\Phi_n(X^p)$.

Solution. By the Möbius inversion formula, we see

$$\begin{aligned} \Phi_{pn}(X) &= \prod_{d|pn}(X^{pn/d}-1)^{\mu(d)} \\ &= \left(\prod_{d|n}(X^{pn/d}-1)^{\mu(d)} \right) \left(\prod_{d|np}^{d\nmid n}(X^{pn/d}-1)^{\mu(d)}\right) \\ &= \Phi_n(X^p) \end{aligned}$$

because all $d$ that divides $np$ but not $n$ must be divisible by $p^2$. Problem 2 can also follow from here.

Problem 5. Let $n=p_1^{r_1}\dots p_s^{r_s}$, then

$$\Phi_n(X)=\Phi_{p_1 \dots p_s}(X^{p_1^{r_1-1}\dots p_s^{r_s-1}}).$$

Solution. This problem can be solved by induction on the number of primes. For $s=1$ it is problem 1. Suppose it has been proved for $s-1$ primes, then for

$$n_{s-1}=p_1^{r_1}\dots p_{s-1}^{r_{s-1}}$$

and a prime $p_s$, we have

$$\Phi_{n_{s-1}p_s}(X)=\frac{\Phi_{n_{s-1}}(X^{p_s})}{\Phi_{n_{s-1}}(X)}$$

On the other hand,

$$\begin{aligned} \frac{\Phi_{n_{s-1}}(X^{p_s})}{\Phi_{n_{s-1}}(X)}&=\frac{\Phi_{p_1\dots p_{s-1}}(X^{ p_1^{r_1-1}\dots p_{s-1}^{r_{s-1}-1}p_s })}{\Phi_{p_1\dots p_{s-1}}(X^{ p_1^{r_1-1}\dots p_{s-1}^{r_{s-1}-1} })} \\ &=\Phi_{p_1 \dots p_{s-1}p_s}(X^{p_1^{r_1-1}\dots p_{s-1}^{r_{s-1}-1}p_s^{1-1}}) \end{aligned}$$

if we put $Y=X^{p_1^{r_1-1}\dots p_{s-1}^{r_{s-1}-1}}$. When it comes to higher degree of $p_s$, it’s merely problem 2. Therefore we have shown what we want.

Computing the Norm

Let $\zeta$ be a primitive $n$-th root of unity, put $K=\mathbb{Q}(\zeta)$ and $G$ the Galois group.. We will compute the norm of $1-\zeta$ with respect to the extension $K/\mathbb{Q}$. Since this extension is separable, we have

$$\begin{aligned} N_\mathbb{Q}^K(1-\zeta)&=\prod_{\sigma \in G}\sigma(1-\zeta) \\ &=\prod_{\sigma \in G}(1-\sigma\zeta) \\ \end{aligned}$$

Since $G$ acts on the set of primitive roots transitively, $\{\sigma\zeta\}_{\sigma \in G}$ is exactly the set of primitive roots of unity, which are roots of $\Phi_n(X)$. It follows that

$$N_\mathbb{Q}^K(1-\zeta)=\Phi_n(1).$$

If $n=p^r$, then $N_\mathbb{Q}^K(1-\zeta)=\Phi_p(1^{p^{r-1}})=\Phi_p(1)=p$. On the other hand, if

$$n=p_1^{r_1}\dots p_s^{r_s},$$

then

$$\Phi_n(1)=\Phi_{p_1\dots p_s}(1)=1.$$