# Irreducibility of $x^5 -x -1$ by reduction mod 5

Is there a quick way of deducing that $x^5-x-1 \in \mathbb{Z}[x]$ is irreducible by reducing it mod 5, other than verifying that it has no roots in $\mathbb{Z}_5$ and no factorization as the product of a factor of order 2 and a factor of order 3?

-
Perhaps not as "quick" as desired, but it must be noted that this is an example of "Artin-Schreier" polynomials $x^p-x+a$ which for $a\not=0$ are always irreducible over $\mathbb F_p$. In particular, one does not try to take advantage of "small numbers", as in the degrees of putative factors. Just that the Galois group of any extension of $\mathbb F_p$ is generated by Frobenius $\beta\rightarrow \beta^p$, and here a root $\beta$ behaves like $\beta^p=\beta-a$. The smallest power that fixes it is $p$-th power, so a root is in $\mathbb F_p$, the fixed field of Frobenius. – paul garrett Jul 29 '12 at 23:38

Hint  If it had an irreducible quadratic factor $\rm\:f(x)\:$ then $\rm\:\Bbb F_5[x]/(f(x)) = \Bbb F_5[w] = \Bbb F_{25}\,$ so $$\rm w^5 = w\!+\!1,\ \ \color{#C00}w = w^{25} = (w^5)^5 = (w\!+\!1)^5 = w^5\! +\! 1^5 = \color{#C00}w\!+\!2\:\Rightarrow\: \color{#C00}0 = 2\:\Rightarrow\Leftarrow$$

Remark $\$ The same proof works generally. Let $\rm\:p\:$ be prime. Working in $\rm \,\Bbb F_p[x]\,$ suppose that $\rm\:g = x^p\! -\!x\! -\! 1\:$ has an irreducible factor $\rm\:f\:$ of degree $\rm\:n< p.\,$ Then in $\rm\:\Bbb F_p[x]/(f) = \Bbb F_p[w] = \Bbb F_{p^n},\:$ $\rm\:w^p = w\!+\!1\:$ so the linear Frobenius map $\rm\:z\to z^p\:$ is just the shift $\rm\:S\!: w\to w\!+\!1,\,$ $\rm\, k\to k\in\Bbb F_p.\:$ Iterated $\rm\:n\:$ times yields $\rm\: w\!+\!n = S^n\, w = w^{p^n}\! =w,\:$ thus $\rm\: 0 = n < p\:$ in $\rm\,\Bbb F_p,\,$ a contradiction.

Alternatively, equivalently, one can instead show that $\rm\:gcd(x^p\!-\!x\!-\!1,\,x^{p^n}\!-\!x) = 1.$ For example, see the answer by Thomas Andrews.

-
As a matter of style I don't like "$\rm0=n<p$ in $\rm\mathbb F_p$" very much, since "$\rm0<p$ in $\rm\mathbb F_p$" is already wrong. I would prefer saying "thus $p=\mathrm{char}(\mathbb F_p)\mid n$, contradicting $n<p$"; then is is also clearer that the contradiction disappears when one replaces $p$ by a prime power $q=p^k$ with $k>1$, and $\mathbb F_p$ by the finite field $\mathbb F_q$. – Marc van Leeuwen Jul 29 '12 at 8:07

Note that it is easy to see there are no roots in $\mathbb Z_5$: by Fermat's theorem, $x^5 - x - 1$ is always $-1$.

This is called an Artin-Schreier polynomial, and with just a little more insight we can see that it is irreducible over $\mathbb Z_5$. If $\alpha$ is a particular root in an algebraic closure of $\mathbb Z_5$, then all 5 roots are given by $\alpha + k$ for each $k \in \mathbb Z_5$ (think "freshman's dream").

Let $d$ be the degree $[\mathbb Z_5(\alpha) : \mathbb Z_5]$. As noted by Patrick Da Silva below, we also have $[\mathbb Z_5(\alpha + k) : \mathbb Z_5] = d$.

Since $x^5-x-1$ splits as $$\prod_{k\in \mathbb Z_5} (x-\alpha+k),$$ the irreducible factorization of $x^5-x-1$ consists entirely of polynomials of degree $d$. Since $d > 1$ as $\alpha \notin \mathbb Z_5$, this forces $d = 5$.

It might be a stretch to say this is faster than direct computation in this tiny case, but I'm guessing it's along the lines you were looking for.

-
"But this is impossible since the degree $[\mathbb{Z}_5(\alpha):\mathbb{Z}_5]$ is prime." You are kind of putting the cart before the horse here. How do you know this? – jspecter Jul 25 '12 at 17:14
@jspecter : $x^5-x-1 = (x-\alpha)(x-\alpha+1)(\dots)(x - \alpha+4)$. If $p(x)$ is the minimal polynomial of $\alpha$, then $p(x-k)$ is the minimal polynomial of $\alpha+k$. Now $x^5-x-1$ is the product of the minimal polynomials of the roots because its separable ; the fact that the degree is prime gives you the result. – Patrick Da Silva Jul 25 '12 at 17:15
Thanks for catching this, will fix. – Erick Wong Jul 25 '12 at 17:16
The usual proof is that if $x^5 - x - 1 = \prod_{k = 0}^{p - 1} (x - \alpha - k)$ has a non-trivial factor of degree $m$ then its coefficient of $x^{m - 1}$ will be in $\mathbb Z_5$ and, writing that out, this will imply that $\alpha \in \mathbb Z_5$, which you know is untrue. – Dylan Moreland Jul 25 '12 at 17:25

Your polynomial is quite special, so that there are many specific ways to prove its irreducibility, as indicated in other answers. Here is how Berlekamp's algorithm, which will detect irreducibilty of general polynomials over finite fields and and leads to a factorisation if they are reducible, applies to this particular case; while not as slick as other approaches it is quite doable by hand.

You first need to check the polynomial $P=X^5-X-1\in\mathbb F_5[X]$ is squarefree by computing the gcd with its formal derivative; the latter is $-1$ in the example, so that's OK.

Next one considers the ring $A=\mathbb F_5[X]/(P)$ as vector space over $\mathbb F_5$, and computes the matrix of the $\mathbb F_5$-linear (thanks to Frobenius) map $f:A\to A$ given by $x\mapsto x^5-x$ on the basis $(1,X,X^2,X^3,X^4)$; in general this would require reducing a certain number of powers of $X$ modulo $P$, but the special form of $P$ allows avoiding that here using $X^{5i}\equiv (X+1)^i\pmod P$ for any $i$, so that the matrix is $$\begin{pmatrix} 0&1&1&1&1\\ 0&0&2&3&4\\ 0&0&0&3&1\\ 0&0&0&0&4\\ 0&0&0&0&0\\ \end{pmatrix}.$$ This matrix clearly has rank $4$ (note the $4\times 4$ triangular minor), so $\dim\ker(f)=1$. This proves that $P$ is irreducible, since if $P$ were reducible, then $A$ would be a product of more than one ring (by the Chinese remainder theorem and the fact that $P$ is squarefree) each of which would contain a copy of $\mathbb F_5$, and the product of these copies would form a subspace of dimension${}>1$ contained in the kernel of $f$, and this is impossible.

Added. To illustrate the reducible case, consider the following related question. It is fairly easy to see that $X^p-X-1\in\mathbb F_p$ will be irreducible for any prime $p$ (and even $X^p-X-a$ for any $a\in\mathbb F_p^\times$ will be irreducible), as several answers indicate; the computation above will give a truncated Pascal triangle matrix with a nonzero $(p-1)\times(p-1)$ minor, and therefore still $\dim\ker(f)=1$. So one might think that maybe even $X^q-X-1\in\mathbb F_q$ would be irreducible for any prime power $q$.

However, if one computes the matrix of $f: x\mapsto x^4-x$ in $A=\mathbb F_4[X]/(X^4+X+1)$ one finds $$\begin{pmatrix} 0&1&1&1\\ 0&0&0&1\\ 0&0&0&1\\ 0&0&0&0\\ \end{pmatrix} \in M_4(\mathbb F_4)$$ whose rank is only $2$, so this shows that $X^4+X+1$ is reducible in $\mathbb F_4[X]$ (if it were irreducible then $A$ would be a field, and $\ker f=\mathbb F_4$, of dimension $1$). Indeed one can see similarly that $X^q-X-1\in\mathbb F_q$ is always reducible when $q$ is a prime power but not a prime.

To concretely find a factorisation of $P=X^4-X-1\in\mathbb F_4$, one lets $Q\in\mathbb F_4[X]$ run through representatives of a coset of $\mathbb F_4$ in $\ker f$ that does not contain $0$, and computes $\gcd(P,Q)$ for all of them, which should reveal nontrivial factors of $P$. One can take that coset to be $\{\,X^2+X+c\mid c\in\mathbb F_4\,\}$, and one finds nontrivial factors (indeed the representative $Q$ itself) for $c=\alpha$ (a root of $X^2+X+1$ in $\mathbb F_4$) and for $c=\alpha+1$; one may check that in fact $X^4+X+1=(X^2+X+\alpha)(X^2+X+\alpha+1)$ in $\mathbb F_4[X]$.

-

One approach would be to prove that $h(x)=x^5-x-1$ is relatively prime to $x^{25}-x$, since that polynomial is the product of all monic primes in $\mathbb Z_5[x]$ of degree $1$ and $2$.

Or, alternatively, show that $h(x)$ is a factor of $\frac{x^{5^5}-x}{x^5-x}$.

In general, $x^{p^n}-x$ is the product of all monic primes in $\mathbb Z_p[x]$ whose degree divides $n$.

It's actually not hard to show that, in $\mathbb Z_p[x]$, $x^{p^p}-x$ is divisible by $h(x)$, and that no prior $x^{p^n}-x$ is divisible by $h(x)$.

Essentially, you prove inductively that $x^{p^n}-x \equiv n \pmod{h(x)}$, and hence that $x^{p^p}-x$ is divisible by $h(x)$, and $x^{p^n}-x$ and $h(x)$ are relatively prime for $1\leq n<p$.

So let's prove my claim.

Clearly, $n=1$ is true, since $x^p-x = h(x)+1\equiv 1 \pmod {h(x)}$

Assume that $x^{p^n}-x \equiv n \pmod {h(x)}$.

Then $x^{p^n} \equiv x+n \pmod {h(x)}$.

Raise both sides to the $p$, and you get:

$$x^{p^{n+1}} \equiv (x+n)^p = x^p + n^p \equiv x+1+n = x+(n+1)\pmod {h(x)}$$

Subtract $x$ from both sides and you get the result required.

-
@Manos If it's not clear, the gcd suggested in the first paragraph above is essentially what I compute in my answer. – Bill Dubuque Jul 25 '12 at 17:47

Suppose $p$ is a prime and $$f(x):=x^p-x-1=f_1(x)f_2(x)\ldots f_n(x)$$ where $f_i(x)$ is irreducible for each $i$. Suppose $a$ is a root of $f(x)$, wlog assume $f_1(a)=0$. Now note that for each $1\leq j\leq (p-1),$ $f(a+j)=(a^p+j^p)-(a+j)-1=0$, so there is a $f_j\ne f_1$ such that $f_j(a+j)=0$. So we have $f_j(a+j)=f_1(a)$ which implies $\deg(f_j)=\deg(f_1)$ for all $j$. So $\deg(f)=n.\deg(f_1)=p$ and this implies $n=1$ or $p$. If $n=p$ then all the roots are in $\mathbb{Z}_p$ but this would imply $0$ is a root of $f(x)$ ( because of the fact: $a$ is a root implies $a+j$ is a root), which is not true. Hence $n=1$ and so $f(x)$ is irreducible.

-

Here's a more general claim. We claim that given any $a\neq 0 \in F$ where $F = \Bbb{Z}_5$, the polynomial $$f(x) = x^5 - x- a\in F[x]$$ is irreducible. Now the condition $a \neq 0$ shows that this polynomial has no roots in $F$. Then as Erick Wong notes above such a polynomial by the schoolboy binomial theorem will have all its roots in an extension as long as it has at least one of them.

Now we claim that $f(x)$ is actually irreducible over $F$. Suppose it is not so that we can write $f =gh$ for some polynomials $g$ and $h$ with $\deg g, \deg h \geq 2$. Neither of them can have degree 1 because otherwise this would contradict $f(x)$ having no roots in $F$. Then $F[x]/(g)$ and $F[x]/(h)$ are extensions of $F$ that have at least one root of $f$ in them. By the note above, $F[x]/(g)$ and $F[x]/(h)$ contain all the roots of $f$. It is easy to see that $F[x]/(g)$ and $F[x]/(h)$ are splitting fields for $f$. But then any two splitting fields are isomorphic so that in particular $[F[x]/(g) : F] = [F[x]/(h) : F]$.

But then this means that $\deg f$ is twice the degree of $g$ (or $h$ for that matter) which is a contradiction because $5$ is an odd number and hence is not divisibly by $2$. Hence $f$ is irreducible over $F$.

$\hspace{6in} \square$

-
The formulation of your proof assumes implicitly ("extension", "splitting field") that $g$ and $h$ are irreducible polynomials. However on the sole assumption that $f$ is reducible, one cannot assume this. It can be deduced in this case by degree consideration (since $\deg f=5$ cannot be sum of more than two numbers${}>1$), but this should be said more clearly. Also note that for $x^p-x-a$ over $\mathbb F_p$, where the result is still true (cf. other answers), such a degree argument would not work. – Marc van Leeuwen Jul 26 '12 at 4:25