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?

Continue reading “Why x^p-1 Factors over GF(2) the Way It Does”