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

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?

• Worst case scenario, check the different choices for $b$ and $a$. $c$ and $d$ are dictated at that point. I'd like to see a slicker way. Aug 6 '18 at 19:38
• this question may help.
– lulu
Aug 6 '18 at 19:43

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.

• Why would there be a smaller splitting field (than that with $7^4$ elements) with the roots of $x^4+x^3+x^2+x+1$ if that polynomial were reducible? Aug 6 '18 at 20:00
• I have lost count of the questions I have settled here using this argument. Welcome to the club :-) Aug 6 '18 at 21:12
• @user437309 If $f(x)$ splits into two irreducible quadratics $g(x)h(x)$, we can construct a finite field $K = \mathbb F_7[x]/(g(x))$. Now we can still compute in $K$: $$x^5-1 = (x-1)f(x) = (x-1)g(x)h(x) \equiv 0 \pmod{g(x)}$$ This means we have constructed a finite field $K = \mathbb F_7[x]/(g(x))$ with $7^2$ elements which also contains an element $x$ with order $5$. But that is not possible since $5\nmid 7^2-1 = 48$. Aug 7 '18 at 7:19
• Now I understand the solution as follows. Let $a$ be a root of $x^4+x^3+x^2+x+1$ in a field extension of $\mathbb F_7$. If the polynomial were reducible, then the degree $[\mathbb F_7(a):\mathbb F_7]$ would be strictly less than $4$, and also $a$ would have order $5$ in this extension. The first condition means that $\mathbb F_7(a)=(\mathbb F_7)^k$ where $k=1,2,3$, but none of these three fields contains an element of order $5$. Aug 7 '18 at 19:26
• @user437309 yes, that’s right. Aug 7 '18 at 19:45

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.

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$.

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.

• Explain the reason of your downvote, please. If there exists a factorization in two quadratics, then it would have two distinct factorizations in two quadratics over an extension of $\mathbb F_7$. This is not possible. Aug 6 '18 at 22:38
• I don't know who downvoted this answer, I just upvoted it. Aug 6 '18 at 23:05
• @user437309: I did not say, dear friend, that it was you who put the downvote. It should be mandatory in S.E. that a downvote is always with justification exposed. That the person that put it refuses to respond shows its (mathematically speaking) ilk. Aug 7 '18 at 0:07
• Hmm. Over $\Bbb{C}$ the roots of the polynomial $x^4+x^3+x^2+x+1$ are $\zeta^k$ with $\zeta=e^{2\pi i/5}$, $k=1,2,3,4$. Your argument shows that the quadratic factors with real coefficients, $(x-\zeta)(x-\zeta^4)$ and $(x-\zeta^2)(x-\zeta^3)$, don't exist in $\Bbb{F}_7$ because they involve $\sqrt5$. But how do you rule out a factor like $(x-\zeta)(x-\zeta^2)$ showing up? True, Galois theory shows that $\Bbb{Q}(\sqrt5)$ is the only quadratic subfield of $\Bbb{Q}(\zeta)$. That does lead to an argument, but the connection to Galois theory of finite fields runs a bit deep. Aug 7 '18 at 5:34
• (cont'd) In if you really want to use Galois theory here, a simpler way is to use the Frobenius automorphism $F$ of all extensions of $\Bbb{F}_7$: If $\zeta$ is a root of some polynomial with coefficients in $\Bbb{F}_7$ then so is $F(\zeta)=\zeta^7=\zeta^2$, and therefore also $F(\zeta^2)=\zeta^{14}=\zeta^4$, and therefore also $F(\zeta^4)=\zeta^3$. That's four zeros, so any polynomial with $\zeta$ as a root has degree four. Aug 7 '18 at 5:37