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$.)
Best Answer
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$.