Show some polynomial is irreducible over the field of 7 elements.

Question

I have to show that the polynomial $x^4+x^3+x^2+x+1$ is irreducible over the field $F_7$.

It doesn't have roots in $F_7$, but I can't show it does not have degree two irreducible factors in $F_7[x]$. Please help me. Thank you.

Answer 1

Exercise 8 of Chapter 13.6 in Dummit & Foote's Abstract Algebra provides a step-by-step exercise (which is fairly easy) to determine the factorization of $\Phi_{\ell}(x)$ in $\mathbb F_p[x]$ where $p, \ell$ are primes and $\Phi_{\ell}$ is the $\ell^{\text{th}}$ cyclotomic polynomial. In your case you are trying to factor $\Phi_5$ over $\mathbb F_7$. The exercise determines the degrees of the irreducible factors of the factorization of $\Phi_{\ell}$ as soon as you know the order of $p$ in the multiplicative group of $\mathbb F_{\ell}$, i.e. the least positive integer $f$ such that $p^f \equiv 1 \pmod{\ell}$ (assuming $p \neq \ell$, of course ; the case $p=\ell$ is actually trivial, since $\Phi_p(x) = (x-1)^{p-1}$ because of the Frobenius automorphism). It requires some field theory though, so I don't know if you have the tools for this. I just thought this was of public interest.

Hope that helps,

Answer 2

Try dividing your polynomial by the arbitrary quadratic (WLOG, monic) polynomial $x^2 + ax + b$. The remainder will be a quadratic cubic polynomial in $a$ and $b$. Check that it has no roots over $F_7$ by brute force.

Answer 3

The brute-force approaches of the earlier answers might be appropriate if the polynomial were essentially random, but it is not. It is the fifth cyclotomic polynomial! It will have a root in the smallest extension $\mathbb F_{7^d}$ of $\mathbb F_7$ that has a (necessarily cyclic) subgroup of order $5$. Since the multiplicative group of $\mathbb F_{7^d}$ is (cyclic) of order $7^d-1$, the question is what multiplicative order $7$ has mod $5$. Since $7=2 \mod 5$, and $2^2=4$, $2^3=8=3\mod 5$, and $2^4=2\cdot 3=6=1\mod 5$, the order of $7$ is $4$. That is, the smallest-degree extension containing a root is of degree $4$, and the $5$th cyclotomic polynomial is irreducible mod $7$.

Answer 4

Assume $F$ is a ring ( commutative, with $1$) and $K$ is an extension of $F$ in which $x^4 + x^3 + x^2 + x + 1$ has a root $a$. Then one checks that we have the following decomposition in $K[x]$:

$$x^4 + x^3 + x^2 + x + 1 = (x-a)(x-a^2)(x-a^3)(x-a^4)$$

Indeed, we have the identity:

$$x^4 + x^3 + x^2 + x + 1 - (x-a)(x-a^2)(x-a^3)(x-a^4)= \\=(a^4 + a^3 + a^2 + a+1)\cdot \\ \cdot \left( x^3 + (1-a-a^3) x^2 + (1-a + a^5) x + (1-a + a^5 - a^6)\right)$$

Now, assume that we can combine one or two factors $(x-a^i)$ to get a polynomial in $F[x]$. Then $a \in F$, or a products $(x-a^i)(x-a^{5-i})$ is in $F$. Now from

$$(x-a^{i})(x-a^{5-i}) = (x-b)(x-b^{-1}) = x^2+ (-(b+\frac{1}{b})) x +1$$

so $\phi = -(b+\frac{1}{b}) \in F$. It is easy to check that $\phi^2 -\phi-1 = 0$.

Conclusion: $x^4 + x^3 + x^2 + x + 1$ is decomposable over the field $F$ if and only if the "golden" equation $t^2 - t-1$ has roots in $F$. If so, then it decomposes as

$$x^4 + x^3 + x^2 + x + 1 = (x^2 + \phi x + 1)(x^2 +\bar \phi x + 1)$$

where $\bar \phi = 1-\phi$.

Now we notice that $t^2 -t-1$ does not have roots in $\mathbb{F}_7$.