# Why x^p-1 Factors over GF(2) the Way It Does

Let $p$ be a prime number. We know that $F_2=GF(2)=\{0,1\}$. Let $F_2[x]$ be the ring  the polynomials with indeterminate $x$ and coefficients in $F_2$. The polynomial $(x^p-1) \in F_2[x]$ factors over $F_2$ as  follows for various $p$:

$x^3-1=(1+x) (1+x+x^2).$
$x^5-1=(1+x) (1+x+x^2+x^3+x^4).$
$x^7-1=(1+x) (1+x+x^3) (1+x^2+x^3).$
$x^{11}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}).$
$x^{13}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}).$
$x^{17}-1=(1+x) (1+x^3+x^4+x^5+x^8) (1+x+x^2+x^4+x^6+x^7+x^8).$

None of the factors above can be factored anymore, hence they are irreducible over $F_2$. Let us call $x+1$ the trivial factor since the root $x= 1$ already belongs to $F_2$. But why do we have two nontrivial irreducible factors of $x^7-1$, each of degree 3, whereas $x^{13}-1$ has only one non-trivial irreducible factor of degree 12? It appears that either there is only one nontrivial factor, or the degree of all nontrivial factors is the same. Why?

More formally, let $n_p(d)$ be the number of the nontrivial irreducible polynomials of degree $d$ appearing in the factorization of $x^p-1$ over GF(2). We would like to understand $n_p(d)$.

In another post, I discussed the structure of the quotient ring $R=F_\ell[x]/(x^p-1)$. There, we have shown that

$\displaystyle R=F_\ell[x]/(x^p-1) \cong F_\ell \oplus (F_{\ell^r})^s,\ \ \ \ \ \ \ \ (*)$

where $r$ is the smallest natural that makes $\ell^r \equiv 1 \pmod{p}$, and $s=(p-1)/r$. Here, $r$ is called the multiplicative order of $\ell$ modulo $p$. Since Fermat’s little theorem tells us that $\ell^{p-1}\equiv 1 \pmod{p}$, it follows that $r$ must divide $p-1$ and $s$ will always be an integer.

So what? (A little head scratching.) Okay. A root of the polynomial $x^p-1$ is called a $p$th root of unity. Our base field, $F_2$, contains 1, the trivial root of unity. It turns out, the smallest extension $E$ over $F_2$ that contains a non-trivial $p$th root of unity is $E=F_{2^r}$. (Why?) This extension $E$, once again, is isomorphic to the quotient field $F_2[x]/(q(x))$ where $q(x)$ is an irreducible polynomial of degree $r$ over $F_2$. Each copy of $F_{2^r}$ in the decomposition of the quotient ring $R$ corresponds to an irreducible polynomial of degree $r$. These polynomials are the factors of $x^p-1$ over $F_2$. Therefore,

$\displaystyle \boxed{n_p(d)=\left\{\begin{array}{ll} (p-1)/ord_p(2) & \text{ if } d=ord_p(2) \\ 0 & \text{ otherwise} \end{array}\right..}$

This means, in the factorization of $x^p-1$ over GF(2),

• The degree of all nontrivial irreducible factors is the same, and it equals the order of $2$ modulo $p$
• The number of these factors times their degree equals $(p-1)$

Now that is awesome. Moreover, this argument is valid over any base field of prime order $l$, which was $2$ in the above discussion.

For primes $p = 3, 5, 11, 13, 19$ and $29$, $r=ord_p(2)=p-1$; hence there is only $s=(p-1)/(p-1)=1$ nontrivial irreducible factor of degree $p-1$ in the expansion of $x^p-1$ over GF(2). This is true in general for primes for which 2 is a primitive root.

When $p=7$, the order of 2 modulo 7 is $r=3$. This is why there are $(7-1)/3=2$ irreducible factors of degree 2 in the expansion of $x^p-1$ over GF(2). When $p=17$, the order of 2 modulo 17 is $r=8$. This is why there are only $(17-1)/8=2$ irreducible factors of degree 8 in the expansion of $x^p-1$ over GF(2). A similar analysis is true for $p=23$.

Let $N(d)$ be the number of monic degree-$d$ irreducible polynomials over $latex F_2$. (See this sequence and this Wikipedia article.) The splitting fields of two irreducible polynomials of the same degree are isomorphic. (Why? See this post again.) Hence the polynomials of a given degree $d$ appearing in the factorization of $x^p-1$ are not unique; unless, of course, all $N(d)$ of them appear together and makes the factorization unique. This is indeed the case for $x^7-1$, where all $N(3)=2$ monic irreducible polynomials of degree $3$ appear as its factors.