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

Let $p$ be a prime. 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
• The original version of the question (which I've now edited) omitted the requirement that $p$ be a prime. This requirement was necessary: The polynomial $x^4-x+a$ over $\mathbb{F}_4$ is reducible for every $a \in \mathbb{F}_4$ ! – darij grinberg Sep 18 '16 at 3:20
• This is also a particular case of math.stackexchange.com/questions/136164 . – darij grinberg Sep 18 '16 at 3:34

## 7 Answers

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 a field with $p$ elements, we know that $p$ is the characteristic of our field. Hence, the polynomial $g(x)=x^p-x$ has the property $$g(x_1+x_2)=g(x_1)+g(x_2)$$ whenever $x_1$ and $x_2$ are two elements of an extension field of $\mathbb{F}_p$. 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$ with $k \in \Bbb{F}_p$ 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
• just a comment: $r$ is sent to $r - a$ since $r^p -r +a =0$ – Ivan Feb 8 at 19:55

$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 :) :) :) – user87543 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 :) – user87543 Aug 3 '13 at 10:16
• You cannot conclude $f(x)$ is separable simply by $f'(x)\ne 0$ without assuming $f$ is not irrreducible. For example, $f(x)=x(x+1)^2$ is not separable but $f'(x)=(x+1)^2+2x(x+1)\ne 0$. – Bach Jan 28 '20 at 17:42

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

• This probably needs the separability of $f$, because if some of the $g_1,g_2,\ldots,g_k$ could be equal, the concept of a permutation and its order would be somewhat muddled. – darij grinberg Sep 18 '16 at 3:25

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

• Doesn't the first sentence "$x^p - x + a$ divides $x^{p^p} - x$" already assume that $x^p - x + a$ is irreducible? Also this reasoning would show that any polynomial of prime degree over a finite field with no roots is irreducible, which is not true. E.g. an irreducible quadratic times an irreducible cubic over $\mathbb{F}_2$ doesn't divide $x^{2^5} - x$ – math54321 Apr 4 '20 at 5:16

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.

• This is a very helpful and simple answer. Can I ask why it is not the case why f splits in Fp? – P-S.D Apr 1 '17 at 23:20
• Also, by f splits in Fp, do you mean that Fp is the splitting field of f? Why would Fp being the splitting field of f imply that 0 or 1 is a root? – P-S.D Apr 1 '17 at 23:26
• @P-S.D If $\alpha\in\mathbb{F}_p$, then the $p$ elements $\alpha+i$, $0\le i<p$, are all in $\mathbb{F}_p$ and are all roots of $f$. But $f$ has degree $p$, so it clearly splits in $\mathbb{F}_p$ and thus each of the $p$ elements of that field, including $0$ and $1$, is a root of $f$. – rogerl Apr 2 '17 at 14:53

The supposition of Greg Martin is truth, if a polinomyal $f$ with $deg(f)=n$ satisfies the property, then $n\ge p$, by contradiction argument, just write the expansion with the Newton's formula and analyse the coeficient of $x^{n-1}$ term, you get $\binom n 1a_{n}+a_{n-1}=a_{n-1}$, if $n\lt p$, this equation is an absurd.