$x^4+x^3+x^2+x+1$ irreducible over $\mathbb F_7$

Question

This question came from the answer here.

The answer claims that $x^4+x^3+x^2+x+1$ is irreducible over $\mathbb F_7$. I can check that it has no roots in the field, but why can't it be written as a product of two quadratics? I tried the method of undetermined coefficients: $$x^4+x^3+x^2+x+1=(x^2+ax+b)(x^2+cx+d)=\\ x^4+(a+c)x^3+(ac+b+d)x^2+(bc+ad)x+bd$$ so $$a+c=1\\ac+b+d=1\\bc+ad=1\\bd=1$$ but I wasn't able to solve this. Maybe there is a way to see irreducibility by only using general finite fields theory?

Answer 1

Any element in any field satisfying $x^4+x^3+x^2+x+1=0$ also satisfies $x^5=1$. In other words, it has order $5$ in the multiplicative group of that field.

The field with $p^k$ elements has a multiplicative group with $p^k-1$ elements, so it has elements of order $5$ if and only if $5$ divides $p^k-1$. This is not the case for $p=7$ and $k=1,2,3$, but it is the case for $p=7,k=4$.

Therefore, the smallest field containing $\mathbb{F}_7$ and roots of $x^4+x^3+x^2+x+1$ has $7^4$ elements. If that polynomial were reducible, there would be a smaller splitting field with such roots, but there isn’t.

Answer 2

If you want to continue your approach in case you cannot come up with some clever argument like that in Alon Amit's answer, then you can do it as follows. First, note that $c=1-a$ and $d=b^{-1}$. Thus, the equation $ac+b+d=1$ becomes $$a(1-a)+b+b^{-1}=1\,.\tag{*}$$ The equation $bc+ad=1$ is now $$b(1-a)+ab^{-1}=1\,.$$ Thus, $$a^{-1}\big(1-b(1-a)\big)=b^{-1}=1-b-a(1-a)\,.$$ That is, $$1-b(1-a)=a-ab-a^2(1-a)\,.$$ Consequently, $$(2a-1)b=-1+a-a^2+a^3=(a-1)(a^2+1)\,.\tag{#}$$ Thus, $a\notin\{0,1,4\}$ for the equation above to be possible (noting that $a\neq 0$ and $b\neq 0$). You are left with four choices of $a$, namely, $a\in\{2,3,5,6\}$.

If $a=2$, then, using (#), we get $b=3^{-1}\cdot 5=5\cdot 5=4$, so $b^{-1}=2$, but then $$a(1-a)+b+b^{-1}=2\cdot(-1)+4+2=4\neq 1\,.$$ If $a=3$, then we have by (#) that $b=5^{-1}\cdot20=-3=4$, whence $$a(1-a)+b+b^{-1}=3\cdot(-2)+4+2=0\neq 1\,.$$ If $a=5$, then $b=3^{-1}\cdot (-1)=-5=2$, so $b^{-1}=4$, but then $$a(1-a)+b+b^{-1}=5\cdot(-4)+2+4=0\neq 1\,.$$ Finally, if $a=6$, then $b=4^{-1}\cdot3=2\cdot 3=-1$, whence $b^{-1}=-1$, and $$a(1-a)+b+b^{-1}=6\cdot(-5)+(-1)+(-1)=-4\neq 1\,.$$ Thus, (*) cannot be satisfied.

Answer 3

Yet an other solution. It is based on the fact that $$ f = x^4+x^3+x^2+x+1\in\Bbb F_7[x] $$ is reciprocal, and tries to use the idea in the OP. (There should be no splitting in two polynomials of degree two.)

Assume there is a factorization $$ f=(x^2+ax+b)(x^2+cx+d)\ ,\qquad a,b,c,d\in\Bbb F_7\ .$$ Let $u\ne 0$ be a root of the first factor in some extension (of degree two). Then $1/u$ is also a root. We distinguish two cases.

First case: $1/u$ is also a root of the first factor. Then $b=1$, then $d=1$, $c+a=1$, the product $$(x^2+ax+1)(x^2+(1-a)x+1)$$ is reciprocal, and we have to look for a match of the coefficient in $x^2$, for a few values of $a$ (modulo the action $a\leftrightarrow (1-a)$). There is no such $a$ with $1+a(1-a)+1=1$.

Second case: $1/u$ is not a root of the first factor. Let $u$, $v$ be the two roots of $x^2+ax+b$. Then $1/u$, $1/v$ are the roots of the second factor, which is the reciprocal polynomial, made monic, so we expect an equality of reciprocal polynomials $$ (x^2+ax+b)(1+ax+bx^2) = b(x^4+x^3+x^2+x+1)\ . $$ The two equations obtained, $ab+a=b$ and $1+a^2+b^2=b$, have no solution in $\Bbb F_7$. (The substitution of $a=b/(b+1)$ in the second equation leads to... $(b^4+b^3+b^2+b+1)/(b+1)^2=0$.)

---

Note: This is arguably shorter then taking all possible polynomials $x^2+ax+b$, $b\ne 0$, associating $c=1-a$, $d=1/b$, and checking if the other conditions among $a,b,c,d$ are satisfied.

Note: Computer algebra programs show that we have an irreducible polynomial in our hands. For instance using sage:

sage: R.<x> = PolynomialRing(GF(7))
sage: f = x^4 + x^3 + x^2 + x + 1
sage: f.is_irreducible()
True

One can use then computer power also as follows to conclude. (With a slightly bigger effort than for the typing, one can also conclude humanly.) Assume $f$ splits in two (or more factors). One can check there is no root in $\Bbb F_7$. Then there is a root in $\Bbb F_{7^2}=\Bbb F_{49}$, so the polynomials $f$ and $x^{49}-x$ have a common divisor. The gcd is but... we type

sage: gcd( x^49 - x, f ) 
1
sage: gcd( x^(7^4) - x, f ) 
x^4 + x^3 + x^2 + x + 1

For this, one can also compute easily $(x^{49}-x,f)$ as a human by noting that $f$ divides $x^5-1$, so $(x^{49}-x,f)=(x^{49}-x^4+x^4-x,f)=(x^4-x,f)=(x^3-1,f)=(x^2+x+1,f)=(x^2+x+1,x+1)=(1,x+1)=1$.

Answer 4

HINT.-If $x^4+x^3+x^2+x+1$ were reducible then we have either a linear factor with a cubic one or two quadratic factors.

We have $$x^4+x^3+x^2+x+1=-\dfrac 14(-2x^2+(\sqrt5-1)x-2)(2x^2+(\sqrt5+1)x+2)$$ Since $\mathbb F_7^2=\{1,2,4,0\}$ we see that $5$ is not a square modulo $7$. It follows $x^4+x^3+x^2+x+1$ is not a factor of two quadratics modulo $7$.

Besides that a linear factor is not possible is checked easily.