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

As an example of polynomial factorization, we shall factor $x^n-1$ over and $\mathbb{F}_p$ (over the fields $\mathbb{C}$ and $\mathbb{Q}$, see the Special Projects section towards the end of the chapter).

There are many polynomials having integral coefficients which are irreducible over $\mathbb{Q}$ yet, when regarded as polynomials over $\mathbb{F}_p$, factor into irreducibles having smaller degree. For example, $x^2+1$ is irreducible over $\mathbb{Q}$ but over $\mathbb{F}_2$, $x^2+1=x^2-1=(x+1)^2$, since $+1=-1$ in $\mathbb{F}_2$.

This is not too bizarre. It simply warns us that even though we might have an irreducible polynomial having integral coefficients (i.e., irreducible in $\mathbb{Q}[x]$), after we reduce mod $p$, it need not be irreducible (i.e., might be reducible in $\mathbb{F}_p[x]$). What is even more remarkable is the following fact.

Theorem 2.4.9   Let $p$ be any prime and let $f(x)$ be any polynomial having coefficients in $\mathbb{F}_p$. There there is an $n>1$ for which $f(x)$ divides $x^n-1$.

(This theorem will not be proven here - it follows from the polynomial analog of Fermat's little theorem.) In other words, factoring all the $x^n-1$ (the title of this section!) is tantamount to determining all the irreducible polynomials over $\mathbb{F}_p$.

Here is the rough idea. To factor $x^n-1$, we begin by using the same formula that we did over $\mathbb{Q}$:

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

It suffices to factor the $C_m(x)$'s. Let $k$ be the smallest integer for which $p^k\equiv 1 \, ({\rm mod}\, m)$ (this exists by Fermat's Little Theorem). It is known that the roots of $C_m(x)$ in $\mathbb{F}_{p^k}$ are precisely the elements of order $m$ in $\mathbb{F}_{p^k}$. The minimal polynomial of any element of order $m$ in $\mathbb{F}_{p^k}$ is an irreducible factor of $C_m(x)$ and all irreducible factors of $C_m(x)$ arise in this way.