Let be a prime number. We know that . Let be the ring the polynomials with indeterminate and coefficients in . The polynomial factors over as follows for various :

None of the factors above can be factored anymore, hence they are irreducible over . Let us call the trivial factor since the root already belongs to . But why do we have two nontrivial irreducible factors of , each of degree 3, whereas 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 be the number of the nontrivial irreducible polynomials of degree appearing in the factorization of over GF(2). We would like to understand .

In another post, I discussed the structure of the quotient ring . There, we have shown that

where is the smallest natural that makes , and . Here, is called the multiplicative order of modulo . Since Fermat’s little theorem tells us that , it follows that must divide and will always be an integer.

So what? (A little head scratching.) Okay. A root of the polynomial is called a th root of unity. Our base field, , contains 1, the trivial root of unity. It turns out, the smallest extension over that contains a non-trivial th root of unity is . (Why?) This extension , once again, is isomorphic to the quotient field where is an irreducible polynomial of degree over . Each copy of in the decomposition of the quotient ring corresponds to an irreducible polynomial of degree . These polynomials are the factors of over . Therefore,

This means, in the factorization of over GF(2),

- The degree of all nontrivial irreducible factors is the same, and it equals the order of modulo
- The number of these factors times their degree equals

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

For primes and , ; hence there is only nontrivial irreducible factor of degree in the expansion of over GF(2). This is true in general for primes for which 2 is a primitive root.

When , the order of 2 modulo 7 is . This is why there are irreducible factors of degree 2 in the expansion of over GF(2). When , the order of 2 modulo 17 is . This is why there are only irreducible factors of degree 8 in the expansion of over GF(2). A similar analysis is true for .

Let be the number of monic degree- 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 appearing in the factorization of are not unique; unless, of course, all of them appear together and makes the factorization unique. This is indeed the case for , where all monic irreducible polynomials of degree appear as its factors.

## One thought on “Why x^p-1 Factors over GF(2) the Way It Does”