# How do I prove that $x^p-x+a$ is irreducible in a field with $p$ elements when $a\neq 0$?

How do I prove that $x^p-x+a$ is irreducible in a field with $p$ elements when $a\neq 0$?

Right now I'm able to prove that it has no roots and that it is separable, but I have not a clue as to how to prove it is irreducible. Any ideas?

-
When reading recently an article about the Artin-Schreier theorem, some properties of the so-called Artin extensions were used, and, if no mistakes occur here, those are intimately related to the polynomials of the form $x^p-x+a$. Is there indeed any error that occur? and is there any reference to know more in this direction? Thanks in advance. – awllower Nov 13 '11 at 14:05
@awllower: This question may get you started? – Jyrki Lahtonen Nov 13 '11 at 16:39
@JyrkiLahtonen: Thanks for the question. I really appreciate this. – awllower Nov 13 '11 at 16:46

Greg Martin and zyx have given you IMHO very good answers, but they rely on a few basic facts from Galois theory and/or group actions. Here is a more elementary but also a longer approach.

Because we are in char $p$, the polynomial $g(x)=x^p-x$ has the property $$g(x_1+x_2)=g(x_1)+g(x_2).$$ By little Fermat we know that $g(k)=k^p-k=0$ for all $k\in \Bbb{F}_p$. Therefore, if $r$ is one of the roots of $f(x)=x^p-x+a$, then $$f(r+k)=g(r+k)+a=g(r)+g(k)+a=f(r)+g(k)=0,$$ so all the elements $r+k, k=0,1,2,\ldots,p-1$ are roots of $f(x)$, and as there are $p$ of them, they must be all the roots. It sounds like you have already shown that $r$ cannot be an element of $\Bbb{F}_p$.

Now assume that $f(x)=f_1(x)f_2(x)$, where both factors $f_1(x),f_2(x)\in \Bbb{F}_p[x]$. From the above consideration we can deduce that $$f_1(x)=\prod_{k\in S}(x-(r+k)),$$ where $S$ is some subset of the field $\Bbb{F}_p$. Write $\ell=|S|=\deg f_1(x)$. Expanding the product we see that $$f_1(x)=x^\ell-x^{\ell-1}\sum_{k\in S}(r+k)+\text{lower degree terms}.$$ This polynomial was assumed to have coefficients in the field $\Bbb{F}_p$. From the above expansion we read that the coefficient of degree $\ell-1$ is $|S|\cdot r+\sum_{k\in S}k$. This is an element of $\Bbb{F}_p$, if and only if the term $|S|\cdot r\in\Bbb{F}_p$. Because $r\notin \Bbb{F}_p$, this can only happen, if $|S|\cdot1_{\Bbb{F}_p}=0_{\Bbb{F}_p}$. In other words $f_1(x)$ must be either of degree zero or of degree $p$.

-
Well done, it is a good proof. – awllower Nov 13 '11 at 14:01
I love your proof. One thing is bothering me, though. And It's probably really obvious. How do you know that if $|S|\cdot r\in F_p$, then $|S|$ must be a multiple of $p$ in order for $|S|\cdot r$ to be in $F_p$? I know it has to do with the fact that $r\notin F_p$, and I have some intuition for it, but I don't know how to prove it. – MathTeacher Nov 14 '11 at 4:21
@MathMastersStudent: If $|S|$ is not a multiple of $p$, then $|S|\cdot 1$ is an invertible element of $F_p$. So if $|S|\cdot r= b$ with $b\in F_p$, then $r=b|S|^{-1}$ would be in the prime field $F_p$ as well contradicting known facts. – Jyrki Lahtonen Nov 14 '11 at 7:20
Great answer as usual, Jyrki: +1. Just to show you how pathologically nit-picking some guys are, I would write $|S|\cdot 1_{F_p}=0_{F_p}$ rather than $|S|=0_{F_p}$, since $S$ is an integer and the integers are not included in a finite field... – Georges Elencwajg Jul 24 '13 at 8:05
This argument also applies to any field of characteritic $p$. – Lao-tzu Dec 31 '14 at 12:41

$x \to x^p$ is an automorphism sending $r$ to $r-a$ for any root $r$ of the polynomial. This operation is cyclic of order $p$, so that one can get from any root to any other by applying the automorphism several times. The Galois group thus acts transitively on the roots, which is equivalent to irreducibility.

-
Impressively elegant, zyx: +1 – Georges Elencwajg Jul 24 '13 at 8:12

$f(x)$ is separable since its derivative is $f'(x) = -1 \ne 0$.

Suppose $\theta$ is a root of $f(x) = x^p - x + a$. Using the Frobenius automorphism, we have: \begin{align} f(\theta + 1) &= (\theta + 1)^p - (\theta + 1) - a\\ &= \theta^p + 1^p - \theta - 1 + a\\ &= \theta^p - \theta + a\\ &= f(\theta) = 0 \end{align}

Thus, by induction, if $\theta$ is a root of $f(x)$, then $\theta + j$ is also a root for all $j \in \mathbb F_p$.

By above, if $f(x)$ were to have a root in $\mathbb F_p$, then $0$ would a be a root too, but this contradicts $a \ne 0$. Thus, $f(x)$ has no roots in $\mathbb F_p$. (This can also be shown using Fermat's little theorem.)

Suppose $\theta$ is a root of $f(x)$ in some extension of $\mathbb F_p$. We know that $\theta + j$ is also a root for all $j \in \mathbb F_p$. Since $f(x)$ is of degree $p$, these are all of the roots of $f(x)$.

Clearly, $\mathbb F_p(\theta) = \mathbb F_p(\theta + j)$ for all $j \in \mathbb F_p$. Thus, all $\{\theta + j\}$ have the same degree over $\mathbb F_p$. Since $f(x)$ is separable, it follows that $f(x)$ must be the product of all minimal polynomials of $\{\theta + j\}$. Suppose the minimal polynomials have degree $m$. We have $p = km$ for some $k$. Since $p$ is prime, either $m = 1$; hence $\theta \in \mathbb F_p$, a contradiction. Or $k = 1$; hence $f(x)$ is irreducible because it's the minimal polynomial.

-
Ah, I already accepted it. I want to accept it another time but it will get as unaccepted :P Thank You for this wonderful proof :) :) :) – Praphulla Koushik Aug 3 '13 at 10:03
A good one! ${}$ – Jyrki Lahtonen Aug 3 '13 at 10:06
Happy to help! I have it in my notes. I don't actually remember if I came up with it myself or found it somewhere. – Ayman Hourieh Aug 3 '13 at 10:11
What ever may be the source, Your Answer is good :) – Praphulla Koushik Aug 3 '13 at 10:16

I think the following idea works. Let $f(x) = x^p-x+a$. They key observation is that $f(x+1)=f(x)$ in the field of $p$ elements. Now factor $f(x) = g_1(x) \cdots g_k(x)$ as a product of irreducibles. Sending $x$ to $x+1$ must therefore permute the factors $\{ g_1(x), \dots, g_k(x) \}$. But sending $x$ to $x+1$ $p$ times in a row comes back to the original polynomial, so this permutation of the $k$ factors has order dividing $p$. It follows that either every $g_j(x)$ is fixed by sending $x$ to $x+1$ - which I think is a property that no nonconstant polynomial of degree less than $p$ can have, but that needs proof - or else there are $k=p$ factors, which can only happen in the case $a=0$.

-

$x^p-x+a$ divides $x^{p^p}-x$. If $f$ is an irreducible divisor of $x^p-x+a$ of degree $d$ then $\mathbf{Z}_p[x]/f$ will be a subfield of the field with $p^p$ elements so $p^p = (p^d)^e$ and so $d=1$ or $e=1$. since $x^p-x+a$ has no roots $e=p.$

-

One more proof, similar to Greg Martin's: Suppose $\alpha$ is a root of $f(x)=x^p-x+a$ in some splitting field; then \begin{equation*} (\alpha+1)^p - (\alpha+1) + a = \alpha^p + 1 - \alpha - 1 + a = \alpha^p - \alpha + a = 0, \end{equation*} so that $\alpha+1$ is also a root. It follows that the roots of $f$ are $\alpha+i$ for $0\le i < p$. If $f$ factors in $\mathbb{F}[x]$, say $f = gh$, then the sum of the roots of $g$ is $k\alpha + r$ where $\deg g = k$ and $k, r\in\mathbb{F}_P$. Since $g\in \mathbb{F}_p[x]$ it follows that $\alpha\in \mathbb{F}_p$. But that implies that $f$ splits in $\mathbb{F}_p$, which is not the case (for example, neither $0$ nor $1$ is a root). Thus $f$ is irreducible.

-