How to prove $X^{4}+X^{3}+X^{2}+X+1$ is irreductible in $\mathbb{F}_{2}$

Question

How to prove $X^{4}+X^{3}+X^{2}+X+1$ is irreducible over $\mathbb{F}_{2}$.

The main 2 "weapons" I have at my disposal is the Eisenstein criteria and reduction criteria but neither seem to work in this case as $\mathbb{F}_{2} = \left\{ 1,2\right\} $.

Answer 1

You can simply try to factor it; if it is reducible, it must have either a linear or quadratic factor. There aren't many linear and (irreducible) quadratic polynomials in $\Bbb{F}_2[X]$.

Answer 2

You can observe that this is the fifth cyclotomic polynomial, ${x^5-1\over x-1}$, so any field element $\alpha$ making it $0$ is a primitive fifth root of unity. That is, $\alpha^5=1$ and no smaller power will achieve this. Finite fields $\mathbb F_q$ always have cyclic multiplicative groups $\mathbb F_q^\times$, necessarily of order $q-1$. For such a field to contain a primitive fifth root of unity is equivalent to $5|q-1$. For $q$ a power of $2$, the smallest power with this property is $2^4$. Thus, $\mathbb F_{2^4}$ is the smallest field extension of $\mathbb F_2$ containing such $\alpha$. Since this is of degree $4$ over $\mathbb F_2$, the minimal polynomial of $\alpha$ is irreducible (of degree $4$).

Answer 3

If $f(X) = X^4 + X^3 + X^2 + X + 1$ has a linear factor then it has a root in $\mathbb{F}_2$ and if it has a quadratic factor then it has a root in $\mathbb{F}_4 \cong \mathbb{F}_2[t]/(1+t+t^2)$.

Therefore you can simply check all elements of $\mathbb{F}_4$:

\begin{align*} f(0) &= 1 \\ f(1) &= 1 \\ f(t) &= t^4 + t^3 + (t^2 + t + 1) \\ &= t^4 + t^3 \\ &= t^3(t + 1) \\ &= (t^2 + t)(t + 1) \\ &= (t + 1 + t)(t + 1) \\ &= t+1 \\ f(t+1)&= \dots = t \end{align*}

The last one can be computed from the penultimate via some Galois theory: $f(t^2) = f(t)^2 = (t + 1)^2 = t$ since $t$ and $t + 1$ are conjugate under the automorphism $\sigma(z) = z^2$.

Answer 4

It's enough to show the polynomial has no zero in $\mathbb F_4$. $0$ is clearly not a root. Note that $|\mathbb F_4^{\times}|=3$, thus by Lagrange, for any $x\in\mathbb F_4^{\times}$, $x^3=1$, hence the polynomial can be reduced to $x^2=0$ (as $x^3+1=0, x^4+x=x(x^3+1)=0$) which forces $x=0$.