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.