It seems that for any prime number $p$ and for any non-zero element $a$ in the finite field $\mathbb F\_p$, the polynomial $x^p-x+a$ is irreducible over $\mathbb F\_p$. (It is of course obvious that there are no linear factors.)


Are there any general irreducibility criteria which can help to prove such a result?


(More generally, it seems that all irreducible factors over $\mathbb F\_p$
of $$a+\sum\_{j=0}^n{n\choose j}(-1)^jx^{p^j}$$
(where $a$ is of course a non-zero element of $\mathbb F\_p$)
have a common degree given by a non-trivial power of $p$.)



Is $x^p-x+1$ always irreducible in $\mathbb F_p[x]$?
This is true. Pass to an extension field where the polynomial has a root $r$, notice that the other roots are of the form $r+1$, $r+2$, ..., $r+p-1$. Suppose that $x^p - x +1 = f(x) g(x)$, with $f, g \in \mathbb{F}\_p\left[x\right]$ and $\deg f = d$. Then $f(x) = (x-r-c\_1) (x-r-c\_2) \cdots (x-r-c\_d)$ for some subset $\{ c\_1, c\_2, \ldots, c\_d \}$ of $\mathbb{F}\_p$. So the coefficient of $x^{d-1}$ in $f$ is $-\sum (r+c\_i) = - (dr + \sum c\_i)$; we deduce that $dr \in \mathbb{F}\_p$. If $d \neq 0 \bmod p$, then $r \in \mathbb{F}\_p$ which is plainly false, so $d=0$ or $p$ and the factorization is trivial.


If I were to try to turn this proof into a general technique, I suppose I would frame it as "prove that the Galois group is contained in a cyclic group of order $p$, and observe that it can't be the trivial group, so it must be the whole group." 




---


I can also prove the generalization. Define a $\mathbb{F}\_p$-module endomorphism $T$ of any commutative $\mathbb{F}\_p$-algebra by $T(u) = u^p-u$. Set $F(n) = \mathbb{F}\_{p^{p^n}}$. Observe that
$$T^r(x) = \sum\_{k=0}^r (-1)^{r-k} x^{p^k} \binom{r}{k}.$$


**Lemma** $T$ is an $\mathbb{F}\_p$-linear endomorphism of $F(n)$ whose Jordan-normal form is a single nilpotent block (of size $p^n$).


**Proof** Obviously, $T$ is $\mathbb{F}\_p$-linear. Observe that
$$T^{p^n}(x) = \sum\_{k=0}^{p^n} (-1)^{p^n-k} x^{p^k} \binom{p^n}{k} = x^{p^{p^n}} - x$$
so $T^{p^n}$ is zero on $F(n)$ and we know that $T$ is nilpotent. Finally, $T(x) = x^p-x$ so the kernel of $T$ is one dimensional, and we see that there is only one Jordan block. $\square$


Now, let $p^{n-1} \leq r < p^n$. Roland's polynomial is $T^r(x) = a$ for $a$ a nonzero element of $\mathbb{F}\_p$. Using the Lemma, the image of $T^r: F(n) \to F(n)$ is the same as the kernel of $T^{p^n-r}$. In particular, since $a \in \mathrm{Ker}(T)$, we see that $a$ is in the image of $T^r: F(n) \to F(n)$. Using the Lemma again, all nonzero fibers of $T^r$ are of size $p^r$, so there are $p^r$ roots of $T^r(x)=a$ in $F(n)$. Since Roland's polynomial only has degree $p^r$, we see that all roots of $T^r(x)=a$ are in $F(n)$.


All proper subfields of $F(n)$ are contained in $F(n-1)$. But, since $r \geq p^{n-1}$, the Lemma shows that $T^r(x)=0$ on $F(n-1)$. So none of the roots of $T^r(x)=a$ are in $F(n-1)$.


We conclude that all the factors of Roland's polynomial are of degree $p^n$.


