Show that $x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1$ are irreducible over $GF(4), GF(8)$

Question

I've showed that the polynomials $$x^4 + x^3 + 1 \quad \text{and} \quad x^4 + x^3 + x^2 + x + 1 $$ are irreducible over $GF(2)$.

Now I want to show that for $GF(4)$ and $GF(8)$. I'm not sure my approach is correct, would like your opinion (or any other correct approach if possible)

For $GF(8)$ - We'll need to use some Galois theory:

Edited: Was wrong here, will update later.

For $ GF(4)$ we'll need to construct a mul. and sum table:

Edited: also, will update later.

Answer 1

You can deal with these questions totally abstractly, no hand computations needed. I’ll answer your question as asked, but the generalization to other-degree polynomials than quartic and other characteristics than $2$ are pretty much immediate.

You need to know that $\Bbb F_{2^m}\subset\Bbb F_{2^n}$ if and only if $m\mid n$. Let’s use this fact:

Let $g(x)$ be an irreducible quartic over $\Bbb F_2$. Then any one of its roots, say $\rho$, will generate $\Bbb F_{2^4}=\Bbb F_{16}$, and all its roots are in that extension of $\Bbb F_2$. Now look at $g$ as an $\Bbb F_{2^2}=\Bbb F_4$-polynomial. The root $\rho$ of $g$ still generates $\Bbb F_{16}$, which you see does contain $\Bbb F_4$, and is a quadratic extension of this latter field. So the $\Bbb F_4$-minimal polynomial of $\rho$ is quadratic: $g$ factors over $\Bbb F_4$. (And as @JWL has remarked in a comment, $x^4+x^3+1=(x^2+\omega x+\omega)(x^2+\omega^2x+\omega^2)$, where $\omega$ is an element of $\Bbb F_4$ not in the prime field.)

On the other hand, $\Bbb F_8\not\subset\Bbb F_{16}$ because $3$ is not a divisor of $4$. You see that $\rho$ now must generate a quartic extension of $\Bbb F_8$ because $\rho$ still isn’t in $\Bbb F_{2^6}$ : $4$ isn’t a divisor of $6$. In other words, $g$ is still irreducible over $\Bbb F_8$.

Answer 2

If $f(x)=x^4 + x^3 + 1$ was reducible in $GF(q)$ ($q=2,4,8$), it would have a factor of degree $1$ or $2$. Then, $f(x)$ would have a common factor with $x^{q^2} - x$. This can be checked by taking gcd in $GF(2)$. To compute the gcd easily, use repeated squaring, i.e. compute $x^{2^k} \pmod {f(x)}$ as $k$ increases, by squaring the remainder you get at each step.

This method should work in more general situations.