On the Irreducibility of Cyclotomic Polynomials (pdf)

We give a detailed account of Landau’s proof (Landau, 1929) of the irreducibility of the cyclotomic polynomial, while only assuming basic knowledge in Group, Ring and Field Theory.

One question that might have motivated the investigation of cyclotomic polynomials is the following. What is the factorization of the polynomial

$$\begin{array}{r}{X}^n-1,\end{array}$$

where $n$ is any positive integer? In this discussion, we will restrict our attention to the case of characteristic $0$, aligning with Landau’s proof. Our aim is thus to identify the irreducible factors of $X^n-1$ over $\mathbb{Z}$. We begin by observing that the roots of $X^n-1$ are precisely given by $e^{2\pi ik/n}$, for $k$ ranging from $1$ to $n$. Let ${\mu }_n$ denote the set of all roots of $X^n-1$. This set ${\mu }_n$ forms a cyclic group under multiplication, which is isomorphic to $\mathbb{Z}/n\mathbb{Z}$. We notice that not every element of ${\mu }_n$ generates the entire group. This observation leads us to the following definitions.

Definition 1

Let $n\ge 1$ be an integer. Let $\xi \in \mathbb{C}$ be a root of the polynomial $X^n-1$. Then we call $\xi$ an $n$-th root of unity. Furthermore, if $n$ is the smallest positive integer such that ${\xi }^n=1$ (i.e. $\xi$ generates the entire group ${\mu }_n$), then we call $\xi$ a primitive $n$-th root of unity

Definition 2

For $n\ge 1$, we define the $n$-th cyclotomic polynomial as

$$\begin{array}{r}{\Phi }_n(X):=\prod _{\xi }(X-\xi ),\end{array}$$

where $\xi$ ranges over all primitive $n$-th roots of unity.

Although Definition 2 is somewhat motivated by the preceding discussion, the reasoning behind this definition will become clearer as our investigation progresses. We will now state and prove Landau’s theorem (Landau, 1929) on the irreducibility of the cyclotomic polynomial. Subsequently, we will examine how this theorem implies the irreducibility of cyclotomic polynomials.

Theorem 3 (Landau)

Let $P\in \mathbb{Z}[X]$ be an irreducible factor of $X^n-1$ in $\mathbb{Z}[X]$ and let $\xi \in \mathbb{C}$ be a root of $P$. Then for any integer $r\ge 1$ coprime to $n$ it holds that $P({\xi }^r)=0$.

Proof:
For each integer $k\ge 1$ we observe that the euclidean algorithm yields $Q_k,R_k\in \mathbb{Z}[X]$ with $\mathrm{deg}(R_k)<\mathrm{deg}(P)$ such that $P(X^k)=Q_k(X)P(X)+R_k(X)$, where $R=0$ is possible. Hence, it holds that

$$\begin{array}{r}P({\xi }^k)=R_k(\xi ).\end{array}\text{\hspace{1em}(⋆)}$$

The above produces a polynomial $R_k$ for each integer $k\ge 1$. Let $\mathcal{R}$ denote the set of all of those polynomials. We wish to show that $\mathcal{R}$ is finite. For that we first notice that by Gauss’ lemma, irreducibility of $P$ over $\mathbb{Z}$ implies irreducibility of $P$ over $\mathbb{Q}$. Thus, $\mathbb{Q}(\xi )\cong \mathbb{Q}[X]/(P)$ is an algebraic extension of degree $\mathrm{deg}(P)$ over $\mathbb{Q}$. In particular, $1,\xi ,\dots ,{\xi }^{\mathrm{deg}(P)-1}$ defines a $\mathbb{Q}$-basis of $\mathbb{Q}(\xi )$ viewed as a $\mathbb{Q}$-vector space. This together with $(\star )$ implies that $R_k(\xi )$ is the unique $\mathbb{Q}$-linear representation of $P({\xi }^k)$ in the basis mentioned above. Combining this with the fact that the value of ${\xi }^k$ only depends on $k\mathrm{mod}n$ (since ${\xi }^n=1$), we obtain that $\mathcal{R}$ is finite.

Now let $p$ be a prime number. We recall that the map $x\mapsto x^p$ defines endomorphism on any ring of characteristic $p$ (called the Frobenius endomorphism) and it is the identity on $\mathbb{Z}/p\mathbb{Z}$. Hence $P(X^p)\equiv P(X{)}^p\mathrm{mod}p\mathbb{Z}[X]$. So there exists a polynomial $H\in \mathbb{Z}[X]$ such that $P(X^p)=P(X{)}^p+pH(X)$. Plugging in our root $\xi$ we obtain $P({\xi }^p)=pH(\xi )$. Thus, by the uniqueness proven above, $R_p(X)=pH(X)$. This implies $R_p\equiv 0\mathrm{mod}p\mathbb{Z}[X]$.

We now exploit the fact that $\mathcal{R}$ is finite to define

$$\begin{array}{r}A:=\max \{|a|:a\in \mathbb{Z}\text{ is a coefficient of }R\text{ for some }R\in \mathcal{R}\}<\infty .\end{array}$$

Let $p$ be a prime number strictly larger than $A$. Then by the conclusion of the previous paragraph we obtain $R_p\equiv 0\mathrm{mod}p\mathbb{Z}[X]$. However, by our choice of $A$ and $p$ this implies $R_p=0$. Hence, $(\star )$ yields $P({\xi }^p)=0$.

We now notice that we can repeat the whole proof starting with ${\xi }^p$ as our initial root. Also, the set ${\mathcal{R}}_p$ that we would obtain in that case is a subset of our original $\mathcal{R}$. This is due to the uniqueness of the representation of ${\xi }^k$ shown above and the fact that ${\xi }^k$ only depends on $k\mathrm{mod}n$ (if $p$ was invertible in $\mathbb{Z}/n\mathbb{Z}$, we would even get equality of the sets). In particular, the largest absolute value of the coefficients of ${\mathcal{R}}_p$ would be smaller or equal to $A$. Thus, by induction on the number of prime factors, we obtain that $P({\xi }^m)=0$ for any positive integer $m$ whose prime factors are all strictly larger than $A$.

Finally, let $r$ be any positive integer coprime to $n$. We define

$$\begin{array}{r}{r}^{\prime }:=r+n\prod _{\begin{array}{c}p\le A\\ p\nmid r\end{array}}p,\end{array}\text{\hspace{1em}(⋄)}$$

where $p$ ranges over prime numbers. We notice that $r^{\prime }\equiv r\mathrm{mod}n$ and claim that $r^{\prime }$ has only prime factors strictly larger than $A$. Indeed, assume for a contradiction that $p\le A$ is a prime number dividing $r^{\prime }$. If $p$ also divides $r$, then by the definition of the product in $(\diamond )$, $p$ must divide $n$. This is a contradiction to the fact that $r$ and $n$ are coprime. Otherwise $p$ does not divide $r$. In this case, the second summand in $(\diamond )$ is zero modulo $p$. Since $p$ is assumed to divide $r^{\prime }$, we obtain that $p$ divides $r$. Thus, we arrive at a contradiction in every case. Finally, we obtain $P({\xi }^r)=P({\xi }^{r^{\prime }})=0$, concluding the proof.

$$\begin{array}{r}\end{array}\text{\hspace{1em}□}$$

Remark 4

In his paper (Landau, 1929), Landau managed to condense the proof above into no more than eight lines.

We will now discuss how Theorem 3 implies the irreducibility of the cyclotomic polynomial and then use this fact to answer our motivating question about the factorization of $X^n-1$ in $\mathbb{Z}[X]$.

Lemma 5

For $n\ge 1$, it holds that

$$\begin{array}{r}{X}^n-1=\prod _{d|n}{\Phi }_d(X),\end{array}$$

where $d$ ranges over all positive integers dividing $n$.

Proof:
Let ${\mu }_n$ denote the set of all roots of $X^n-1$. It then holds that

$$\begin{array}{r}{X}^n-1=\prod _{\xi \in {\mu }_n}(X-\xi ).\end{array}$$

We had already mentioned that ${\mu }_n$ defines a cyclic group of order $n$ under multiplication. We set

$$\begin{array}{r}{\mu }_{n,d}:=\{\xi \in {\mu }_n:\mathrm{ord}(\xi )=d\},\end{array}$$

for all divisor $d\ge 1$ of $n$. Then the ${\mu }_{n,d}$‘s define a partition of ${\mu }_n$. Furthermore, by the definition of primitive roots of unity, ${\mu }_{n,d}$ is exactly the set of all primitive $d$-th roots of unity. Hence,

$$\begin{array}{rl}{X}^n-1& =\prod _{\xi \in {\mu }_n}(X-\xi )\\ & =\prod _{d|n}\prod _{\xi \in {\mu }_{n,d}}(X-\xi )\\ & =\prod _{d|n}{\Phi }_d(X),\end{array}$$

which concludes the proof.

$$\begin{array}{r}\end{array}\text{\hspace{1em}□}$$

Lemma 6

For $n\ge 1$, ${\Phi }_n$ has integer coefficients.

Proof:
We prove the statement by induction on $n$. For $n=1$, we notice that ${\Phi }_1(X)=X-1$ has integer coefficients. Now let $n>1$ and assume that the statement holds for all $d<n$. By Lemma 5 we have

$$\begin{array}{r}{X}^n-1={\Phi }_n(X)\prod _{\begin{array}{c}d|n\\ d\ne n\end{array}}{\Phi }_d(X),\end{array}$$

where all factors on the ride hand side are monic. By our induction hypothesis the product of all ${\Phi }_d(X)$‘s for $d|n$ and $d\ne n$ lies in $\mathbb{Z}[X]$. By Gauss’ lemma (or by simply writing out the product on the right hand side and comparing coeffcients) we obtain that ${\Phi }_n(X)$ has integer coefficients.

$$\begin{array}{r}\end{array}\text{\hspace{1em}□}$$

Theoem 7

For $n\ge 1$, the $n$-th cyclotomic polynomial ${\Phi }_n$ is an irreducible monic polynomial in $\mathbb{Z}[X]$.

Proof:
Let $n$ be an arbitrary positive integer. By definition, ${\Phi }_n$ is monic. From Lemma 6 we obtain that ${\Phi }_n$ lies in $\mathbb{Z}[X]$. It remains to show that ${\Phi }_n$ is irreducible. Let $\xi$ be any root of ${\Phi }_n$. Combining Lemma 5 and Lemma 6 yields that ${\Phi }_n$ divides $X^n-1$ in $\mathbb{Z}[X]$. So there exists an irreducible factor $P\in \mathbb{Z}[X]$ of $X^n-1$ such that $\xi$ is a root of $P$. Now let $\zeta$ be any other primitive $n$-th root of unity. Then, by definition, both $\xi$ and $\zeta$ have order $n$ in ${\mu }_n$, i.e. they both generate ${\mu }_n$. Therefore, there exist integers $r,k\ge 1$ such that $\zeta ={\xi }^r$ and $\xi ={\zeta }^k$. Combining both equations we obtain $\xi ={\xi }^{rk}$. This shows that $r$ is invertible modulo $n$ and thus $r$ is coprime to $n$. Now Theorem 3 yields that $\zeta$ is also a root of $P$. Since $\zeta$ was arbitrary, ${\Phi }_n$ divides $P$ in $\mathbb{Z}[X]$. Finally, irreducibility of $P$ implies that ${\Phi }_n=P$, concluding the proof.

$$\begin{array}{r}\end{array}\text{\hspace{1em}□}$$

Finally, to answer our motivating question, we notice that by combining Lemma 5 and Theorem 7 we obtain that the irreducible factors of $X^n-1$ are exaclty given by ${\Phi }_d$ for divisor $d\ge 1$ of $n$.

References

Landau, E. (1929). Über die Irreduzibilität der Kreisteilungsgleichung. Mathematische Zeitschrift, 29(1), 462–462. https://doi.org/10.1007/BF01180543