Prove that a polynomial is irreducible over $F_{13}$

Question

I am asked to prove that $ f(x) = x^4 + x^3 + x^2 + x +1 $ is irreducible over $F_{13}$. One way that I can think of is to first check for roots, which would rule out linear factors. If there are no roots, then suppose $ f(x) = (x^2+ax+b)(x^2+cx+d) $ where the two factors are irreducible. Then I can also manually check for quadruples $ (a,b,c,d) \in F_{13}^4 $. Obviously, this is very time consuming and not at all enlightening. How do I prove this without resorting to manual checking?

Answer 1

For the cyclotomic polynomials there is a very useful criterion.

Suppose , $f(x)$ is the $n$-th cyclotomic polynomial and $q$ a power of a prime with $\gcd(n,q)=1$

Then, $f(x)$ is irreducible in $\mathbb Z_q$ if and only if the order of $q$ in $\mathbb Z_n^*$ is equal to $\phi(n)$ , in other words, $\mathbb Z_n^*$ is cyclic and $q$ is a generating element.

Answer 2

Here’s another approach, self-contained, but maybe you’ll consider it more advanced.

You see that your $f$ is $(x^5-1)/(x-1)$, so that its roots are the fifth roots of unity different from $1$. You know that $\Bbb F_{13}$ certainly has no such fifth roots of unity since $5$ doesn’t divide $12=13-1$ Similarly, $5$ doesn’t divide $168=169-1$, which is the order of the multiplicative group of $\Bbb F_{13^2}$, the quadratic extension of your original field. This means that the roots of $f$ aren’t in the quadratic extension, and therefore the irreducible factor(s) of $f$ aren’t quadratic. (Remember that the degree of an extension $\Bbb F(\alpha)$ over $\Bbb F$ is the degree of an (the) irreducible $\Bbb F$-polynomial of which $\alpha$ is a root.)

But wait! $5$ doesn’t divide $13^2-1$ because $13^2\not\equiv1\pmod5$, in other words $3^2\not\equiv1\pmod5$. And you know that $3^4\equiv1\pmod5$, so that the same is true of $13$, so $5|(13^4-1)$. So $\Bbb F_{13^4}$ is the smallest extension of $\Bbb F_{13}$ that contains all fifth roots of unity, and consequently your $f\,$’s roots are of degree four over $\Bbb F_{13}$, and their minimal polynomial is of degree four, and thus equal to $f$ itself.