Show that $f(x) = x^p -x -1 \in \Bbb{F}_p[x]$ is irreducible over $\Bbb{F}_p$ for every $p$.

Let $$p$$ be a prime.

a) Show that $$f$$ has no roots in $$\Bbb{F}_p$$.

Let $$F^*$$ be the multiplicative group of $$\Bbb{F}_p$$. Then, by lagrange's thoerem for all nonzero $$\alpha \in \Bbb{F}_p$$, $$\alpha^{p-1} = 1 \implies \alpha^p=\alpha \implies \alpha^p-\alpha=0$$. Of course $$0^p=0$$, so this is true for all elements of $$F$$ and not just the nonzero ones. But then $$\alpha^p - \alpha - 1 = -1$$ for all $$\alpha \in \Bbb{F}_p$$ and so it must have no roots in $$\Bbb{F}_p$$. I could have also done this using the Frobenius automorphism, right?

b) Let $$\alpha$$ be a root of $$f$$ (in some algebraic closure of $$\Bbb{F}_p$$). Show that $$\alpha + s$$ is also a root for all $$s \in \Bbb{F}_p$$.

Let $$\alpha^p - \alpha -1 =0$$. Let $$E$$ be an algebraic closure of $$\Bbb{F}_p$$. Since $$E$$ has characteristic $$p$$, $$(\alpha + s)^p = \alpha^p + s^p$$. So we have,

$$(\alpha + s)^p - (\alpha + s) -1 = \alpha^p + s^p - \alpha -s -1 = s^p - s = 0.$$

c) Conclude that $$f$$ is irreducible over $$\Bbb{F}_p$$, for every $$p$$.

By b) and the fact that $$\Bbb{F}_p$$ has $$p$$ distinct elements, we know that the roots of $$f$$ are $$\alpha, \alpha+1, ... , \alpha + p-1$$. So if $$K$$ is a splitting field, we have $$x^p - x -1 = (x-\alpha)(x-(\alpha+1))...(x-(\alpha+p-1)).$$

Now let's assume that $$f$$ is reducible over $$\Bbb{F}_p$$. Then $$f=gh$$ for some $$g$$ and $$h$$ with degrees less than that of $$f$$. So $$g$$ and $$h$$ must be of the form $$(x-(\alpha+s_1))...(x-(\alpha+s_k))$$ where k is less than n. Let's say that g has degree 2, because the other cases are similar.

So $$g =(x-(\alpha + s_i))(x-(\alpha + s_j))$$ and the constant term for $$g$$ is,

$$(\alpha + s_i)(\alpha + s_j) = \alpha^2 + s_is_j\alpha + s_is_j.$$

Since $$\Bbb{F}_p$$ is a field, if $$\alpha s_is_j$$ is an element of $$\Bbb{F}_p$$ , then so is $$((\frac{1}{s_is_j})(\alpha s_is_j) = \alpha$$, a contradiction.

We can show by induction that if we multiply $$(x-(\alpha+s_1))...(x-(\alpha+s_k)$$, we get a term that looks like $$s_1s_2...s_k\alpha$$. So this is also true for $$k>2$$.

Do you think that my answer is correct?

• See this related question for several proof ideas requiring varying background. ALL: Not a dup, as this is a "check my proof"-question!! – Jyrki Lahtonen Jul 23 '13 at 21:15

I like your idea very much, but I didn't understand how you managed to ignore the $\alpha^2$ term from your constant term.

I have written up an answer to this question with a similar idea, where I look at the next to highest degree term of $g(x)$ (=the term of degree $k-1$). In your degree two example, this would be the linear term. Its coefficient is $2\alpha+(s_i+s_j).$ As $s_i,s_j$ are in the prime field, and $2$ is invertible, we can, as in your argument, conclude that $\alpha\in\mathbb{F}_p$, which is a contradiction.

By studying the lowest degree term, you get a lot of clutter from powers of $\alpha$. The degree $k-1$ term is IMHO easier to manage.

• I don't know...maybe my answer is wrong. I wasn't looking at $\alpha^2$, I was just looking at the term $s_is_j\alpha$. – user58289 Jul 23 '13 at 21:07
• There is a problem with that step, sure. You could try the induction on the $x^{k-1}$ term. You made it so far that it would be a shame to abandon this general approach. – Jyrki Lahtonen Jul 23 '13 at 21:13

a) and b) are fine. I haven't checked c) but you could also note that if the polynomial splits into $h \cdot g$ with $h,g \in \mathbb{F}_p[x]$ then, say $$h(x) = \prod_{i \in S} (x - (\alpha + i)) \in \mathbb{F}_p[x]$$

with $S$ proper subset of $\{0,1,\ldots,p-1\}$. Therefore $$\sum_{i \in S} (\alpha + i) \in \mathbb{F}_p$$ hence $|S| \alpha \in \mathbb{F}_p$ but since $0 < |S| < p$ this implies that $\alpha \in \mathbb{F}_p$, but then $$f(x) = \prod_{i} (x - i) = x^p - x$$ which is not true.

(This is an alternate approach that doesn't use the outlined argument.)

In general, if $h(x)|x^{p^n}-x$ in $\mathbb F_p[x]$ then $h(x)$ is the product of distinct prime polynomials, each of degree equal to a factor of $n$.

If you know this, a fun way to prove this theorem (but skipping the outlined steps in the question) is to prove that $x^p-x-1$ is a divisor of $x^{p^p}-x$. Since $x^p-x-1$ has no roots in $\mathbb F_p$, this would mean that it has to be a prime polynomial.

You show that it is a factor by noting that:

$$x^{p^p}-x = \sum_{k=0}^{p-1} \left(x^{p^{k+1}}-x^{p^k}\right) = \sum_{k=0}^{p-1} (x^p-x)^{p^k} = \\\sum_{k=0}^{p-1}((x^p-x-1)+1)^{p^k} \equiv 0\pmod{x^p-x-1}$$

Another approach:

Suppose $x^p-x -1 = gh$ for $g, h \in \mathbb F_p[x]$ with degrees $\geq 1$. Then taking a (formal) derivative, we have $$-1 = g'h + gh'$$ since $px^{p-1} = 0$ in $\mathbb F_p[x]$. Note that $g'$ and $h'$ cannot both be $0$, otherwise, $-1 = 0$. This implies the degree of the right hand side is at least $1$ (verify!). But the degree of $-1$ is $0$. Contradiction.

• An interesting idea! I really want it to work! But, you lost me at the verification step. How do you arrive at this contradiction? Observe that $x^p-x-1$ does factor over the field $\Bbb{F}_{p^p}$, it splits into linear factors over that field. So any argument needs to use a property specific to the field $\Bbb{F}_p$. Characteristic $p$ is not enough, because the polynomial factors over a bigger field with the same characteristic. – Jyrki Lahtonen Sep 18 '16 at 15:27
• Your first equation may be wrong as there may be cancellations (and there will be cancellations in extension field situation I described). The formula $$\deg (a(x)+b(x))=\max\{\deg a(x),\deg b(x)\}$$ only holds, when the polynomials $a(x)$ and $b(x)$ have distinct degrees. Otherwise their leading coefficients may cancel each other. – Jyrki Lahtonen Sep 18 '16 at 18:22
• To address your second claim, the argument I state uses the fact that for any polynomial $p(x) \in \mathbb F_p[x]$, its derivative $p'(x)$ is also in $\mathbb F_p[x]$. So if I assume $x^p-x -1 = gh$ in $\mathbb F_p[x]$, then taking derivatives gives us an equation still n $\mathbb F_p[x]$. – cat Sep 18 '16 at 18:22
• I see my error now, thank you. – cat Sep 18 '16 at 18:23
• For example, $f(x)=x^2+x+1$ factors as $f(x)=(x+\alpha)(x+\alpha+1)$ over $\Bbb{F}_4$. Here $\alpha$ is zero of $f(x)$. With $g(x)=x+\alpha$, $h(x)=x+\alpha+1$ we have, indeed, $$g'h+gh'=1\cdot(x+\alpha+1)+(x+\alpha)\cdot1=1=-1.$$ – Jyrki Lahtonen Sep 18 '16 at 18:25