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?

Solution 1:

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.

Once one learns some Galois theory these and related arguments will become much more intuitive, e.g. see here for a simple example.

Solution 2:

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.

Solution 3:

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

Solution 4:

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.

Solution 5:

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.