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. \]

Author

Desvl

Posted on

2022-09-22

Updated on

2022-09-22

Licensed under