Irreducibility of $x^4+x+4$ over $\mathbb{F}_5$

Question

Suppose $f$ is not irreducible. Since $f(x)=x^4+x+4$ does not have any root in $\mathbb{F}_5$, the only possible factorization can be $f(x)=(x^2+ax+b)(x^2+cx+d)$ for $a,b,c,d \in \mathbb{F}_5$.

Now by comparing the coefficients one gets:

$$1. \,\,a+c \equiv 0 $$ $$2. \,\, b+d+ac \equiv0 $$ $$3. \,\,ad+bc \equiv 1 $$ $$4. \,\,bd \equiv 4 $$

From condition $1$ and $4$, one can find possible values of $a,b,c,d$ and show that none of them simultaneously satisfy $2$ and $3$. But this is a rather long process.

I came across this post here but Rabin's test is even more computationally difficult to do by hand. Is there any other way to tackle this without doing tediously long computations especially if one does not have access to computers?

I will appreciate any suggestions.

Answer 1

Checking whether a polynomial is irreducbile is a lot like checking whether a number is prime. You need to check there are no degree-two factors of your polynomial. There are ten irreducible polynomials of degree 2 (which you can list easily), so you can check divisibility by those.

On the other hand Rabin's test which you mention is not that bad here. Since $f$ is square-free (check $\gcd(f, f')=1$) and has no roots we know $f \mid x^{5^4}-x$, so we just have to check $\gcd(f, x^{5^2}-x) = 1$. Moreover we can compute $x^{5^2}$ modulo $f$ via $x^{5^2} = (x^5)^5$, which makes this easy. Modulo $f$ we have $$x^{5^2} \equiv (-x^2+x)^5 \equiv -x^{10}+x^5 \equiv -(-x^2+x)^2 -x^2+x\equiv 2x^3 + 3x^2 + 2x + 4.$$ Call this $g$ and now check $\gcd(f, g-x) = 1$ by the usual algorithm.

Answer 2

I don't know if you'd consider this easier than the direct approach, but here's an alternate method that's pretty reasonable to do by hand. First, note that $f$ is squarefree: $f(2) = 2$ is not a square mod $5$, so $f$ can't be the square of a quadratic (and we already know $f$ has no roots).

Since $f$ is monic of degree $4$, the discriminant $D(f)$ is equal to the resultant $R(f, f')$. Since $f'(x) = 4x^3 + 1$, this is equal to the determinant of the Sylvester matrix $$\begin{pmatrix} 1 & 0 & 0 & 1 & 4 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 4 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 4 \\ 4 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 4 & 0 & 0 & 1 \end{pmatrix}.$$ Applying elementary row operations, we see that $$D(f) = R(f, f') = \det \begin{pmatrix} 1 & 0 & 0 & 1 & 4 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 4 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 2 & 4 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 4 \end{pmatrix} = 2. $$ By the main theorem of [Leonard 1969], since $D(f)$ is not a square mod $5$, the number of irreducible factors of $f$ does not have the same parity as the degree of $f$. Thus, $f$ can't be a product of two irreducible quadratic polynomials.

Reference:

• Leonard, Philip A. "On factoring quartics (mod $p$)." J. Number Theory 1 (1969), pp. 113–115. DOI: 10.1016/0022-314X(69)90029-8. [MR 237469]

Answer 3

1. $a+c=0$ implies $c=-a$
2. $b+d+ac=0$ implies $b+d=a^2$
3. $ad+bc=1$ implies $b-d = a^{-1}$

Hence $b = 3(a^2+a^{-1})$ and $c = 3(a^2-a^{-1})$

4. $bd=4$ implies $3(a^2+a^{-1}).3(a^2-a^{-1}) = 4$

Hence $1=(a^4-a^{—2})$

Note that $a\neq 0$ so $a^4=1$. Hence $a^{-2}$ equals 0, this is impossible.

Answer 4

This answer uses a little bit of Galois theory.

To simplify the computation a bit, let's replace $x$ by $-x$, and show that $x^4-x+4$ is irreducible. Suppose $a$ is a zero of $x^4-x+4$, it suffices to show $a\not\in\mathbb F_{5^2}$.

Note that $\text{Gal}(\mathbb F_{25}/\mathbb F_5)=\{1, \sigma\}$ where $$\sigma(a) = a^5=aa^4=a(a-4)=a(a+1)=a^2+a$$ Hence $$a + \sigma(a) = a^2+2a \in\mathbb F_5$$ $$a\sigma(a) = a(a^2+a)=a^3+a^2\in\mathbb F_5$$

Now $(a^2+2a)^2-4(a^3+a^2) = a^4 = a+1\in\mathbb F_5$, $a\in\mathbb F_5$, but it's easy to check no element in $\mathbb F_5$ satisfies the polynomial.