Factoring $x^n-1$ over $\mathbb{Q}$

In other words, we shall express $x^n-1$ as a product of irreducible polynomials having coefficients in $\mathbb{Q}$.

This is harder - the constraint ``having coefficients in $\mathbb{Q}$'' is more restrictive than ``having coefficients in $\mathbb{C}$''. First, let us consider some examples:

$n=1$

$x-1$ is already irreducible.

$n=2$

$x^2-1=(x-1)(x+1)$ is the factorization into irreducibles over $\mathbb{Q}$.

$n=3$

$x^3-1=(x-1)(x^2+x+1)$ is the factorization into irreducibles over $\mathbb{Q}$.

Exercise 2.12.7   Show $x^2+x+1$ is irreducible over $\mathbb{Q}$.

$n=4$

$x^4-1=(x^2-1)(x^2+1)=(x-1)(x+1)(x^2+1)$ is the factorization into irreducibles over $\mathbb{Q}$.

Exercise 2.12.8   Show $x^2+1$ is irreducible over $\mathbb{Q}$.

In general, we have a ``formula'' for the irreducible factors of $x^n-1$. To state this we need a definition.

Definition 2.12.9   Let $n=p_1^{e_1}...p_k^{e_k}$ be the prime factorization of an integer $n>1$. Define the Möbius function $\mu:\mathbb{N}\rightarrow \{0,-1,1\}$ by: $\mu(1)=1$ and, if $n>1$ then

$$\mu(n)= \left\{ \begin{array}{cc} (-1)^k,& {\rm if}\ e_1=...=e_k=1,\\ 0, &{\rm if\ some}\ e_i>1. \end{array}\right.$$

For each $m>1$, define the $m^{th}$ cyclotomic polynomial by

$$C_m(x)=\prod_{d\vert m}(x^d-1)^{\mu(m/d)}.$$

Since cyclotomic polynomials are useful for the construction and theory of finite fields, they are also important in algebraic coding theory.

Theorem 2.12.10   For each $m>1$, $C_m(x)$ is irreducible over $\mathbb{Q}$.

For the proof, which goes beyond the scope of this book, see Lang [La], Ch VIII, §3, or Theorem 6.5.5 of Herstein [Her].

Theorem 2.12.11   We have

$$x^n-1=\prod_{m\vert n}C_m(x),$$

where $C_m(x)$ is as above.

This follows from the Möbius inversion formula (see Lidl, Pilz [LP], Ch. 3, §13).

Example 2.12.12   According to this theorem, $x^4-1=C_1(x)C_2(x)C_4(x)$, where $C_1(x)=1$, $C_2(x)=\frac{x^2-1}{x-1}$, and $C_4(x)=(x-1)^0(x^2-1)^{-1}(x^4-1)^1=x^2+1$. This is the same result as the calculation ``by hand'' above.

Exercise 2.12.13   Show $C_5(x)=x^4+x^3+x^2+x+1$. More generally, show that for any prime $p$, $C_p(x)=x^{p-1}+...+1$.

Exercise 2.12.14   Completely factor $x^8-1$ into irreducibles over $\mathbb{Q}$.

Exercise 2.12.15   Completely factor $x^{10}-1$ into irreducibles over $\mathbb{Q}$.

Exercise 2.12.16   Completely factor $x^{12}-1$ into irreducibles over $\mathbb{Q}$.

Exercise 2.12.17   Compute $C_{i}(x)$, $1\leq i\leq 9$.