Number of roots of $f=x^5-x-1$ in $\mathbb{F}_4$

Question

According to David Cox’s ‘Galois Theory’ (Proposition 11.1.5.),

If $f \in \mathbb{F}_p[x]$ is nonconstant and $n \geq 1$, then the number of roots of $f$ in $\mathbb{F}_{p^n}$ is the degree of the polynomial $\gcd(f,x^{p^n}-x)$.

(Here the $\gcd$ is computed in $\mathbb{F}_p[x]$).

I was trying to use this to calculate the Galois group of $f=x^5-x-1$. I have first verified that $f$ has no roots mod $2$, but then (here I call $\bar{f}$ the reduction of $f$ mod $2$):

$$ \bar{f} \equiv x^2-x-1 \mod x^4-x $$

…and $x^2-x-1 \equiv x^2+x+1 \mod 2$, which divides $x^4-x$, so the degree of $\gcd(f,x^4-1)$ is at least $2$… but I’m verifying manually and $\bar{f}$ doesn’t seem to have any roots in $\mathbb{F}_4$. Where did I go wrong?

Answer 1

When verifying manually, did you possibly confuse $\mathbb{F}_4$ with $\mathbb{Z}_4$? That would explain why you didn't find the two roots of $x^2 + x +1$, if you tested the elements $0$, $1$, $2$ and $3$.

The four elements of $\mathbb{F}_4$ are found by adjoining a new element $\omega$ to $\mathbb{F}_2$. I tend to think of $\omega$ as a non-trivial cube root of $1$, and the four elements are then $0$, $1$, $\omega$ and $\omega +1$.

We find that $\omega^2$, as the other non-trivial cube root of $1$, has to be the same as $\omega +1$, and after a bit of rearranging that gives us $\omega^2 + \omega +1 = 0$. This gets us the roots you were looking for.

In any case, this construction of $\mathbb{F}_4$ is exactly the same as the quotient ring $\mathbb{F}_2 [X] / (X^2+X+1)$ since that polynomial is irreducible over $\mathbb{F}_2$. Of course, with this construction it clearly has roots to that polynomial.

Answer 2

The answer is indeed $2$.

Indeed, for all $\alpha \in \mathbb{F}_4$ the relation $\alpha^5=\alpha^2$ holds, so $\alpha \in \mathbb{F}_4$ is a root of the polynomial $x^5+x+1$ iff $\alpha$ is the root of the polynomial $x^2+x+1$. Thus, as $x^2+x+1$ is degree-$2$, it follows that there can be at most $2$ roots of $x^2+x+1$ in $\mathbb{F}_4$, and thus on the one hand, there can be at most $2$ roots of the polynomial $x^5+x+1$ in $\mathbb{F}_4$.

However, note that every root of every polynomial $p \in \mathbb{F}_2[x]$ such that $p$ divides $x^4+x$ , is a root in $\mathbb{F}_4$. So, as $x^2+x+1$ divides $x^4+x$, it follows that the $2$ roots $\alpha_1, \alpha_2$ of $x^2+x+1$ are in $\mathbb{F}_4$. And so from the above paragraph, those $2$ roots $\alpha_i; i=1,2$ satisfy $\alpha^5_i+\alpha_i+1$ $=$ $\alpha^2_i+\alpha_i+1=0$. So thus, on the other hand, $x^5+x+1$ has at least $2$ roots in $\mathbb{F}_4$, namely $\alpha_1$ and $\alpha_2$.

Thus, putting the conclusions of the above two paragraphs together, it follows that $x^5+x+1$ has exactly $2$ roots in $\mathbb{F}_4$.

Answer 3

As described by Chessanator, $\mathbb{F}_4=\mathbb{F}_2 [X]/(X^2+X+1)=\{0,1,w,w+1\}$ where $w=\bar X$. We have the following factorization in $\mathbb{F}_4 [X]$: $$f(x)=x^5+x+1=(x+w)(x+w+1)(x^3+x^2+1)$$ where the polynomial $x^3+x^2+1$ is irreducible since none of $0,1,w,w+1$ is a root of it. Hence, $f(x)$ has only two roots, namely $w$ and $w+1$ in $\mathbb{F}_4$ of order $1$ each.