Is $x^p-x+1$ always irreducible in $mathbb F_p[x]$?

Here is a quick proof using Galois theory.

Let $r$ be any of the roots in an algebraic closure of $mathbb{F}_p$. Then $r^p=r-a$, hence by induction $r^{p^k}=r-ka$. Therefore the elements $r^{p^k}$ ($0leq kleq p-1$) are all different, hence $r$ is of degree $p$.

Added. More generally, it follows by Artin-Schreier theory that the polynomial $$ f_{n,a}(x):=a+sum_{j=0}^n{nchoose j}(-1)^jx^{p^j} $$ decomposes over $mathbb{F}_p$ into irreducible factors of $p$-power degree. We proceed by induction on $n$. Let $ngeq 1$, and assume the statement for $n-1$ in place of $n$. Let us work in a fixed algebraic closure $overline{mathbb{F}_p}$. Let $rinoverline{mathbb{F}_p}$ be a root of $f_{n,a}$. Then $s:=r-r^p$ is a root of $f_{n-1,a}$, so $(mathbb{F}_p(s):mathbb{F}_p)$ is a power of $p$. Clearly, $mathbb{F}_p(r)$ is an extension of $mathbb{F}_p(s)$, because $sinmathbb{F}_p(r)$. This extension is of Artin-Schreier type, because $r$ is the root of the polynomial $x^p-x+s$ over $mathbb{F}_p(s)$. Hence $(mathbb{F}_p(r):mathbb{F}_p(s))$ is equal to $1$ or $p$, and so $(mathbb{F}_p(r):mathbb{F}_p)$ is a power of $p$.

Remark. The degree of $(mathbb{F}_p(r):mathbb{F}_p(s))$ equals $p$ if and only if the trace of $s$ is nonzero. However, it seems difficult to show in this way that $(mathbb{F}_p(r):mathbb{F}_p)$ only depends on $n$ and $a$, let alone calculate it explicitly. David Speyer's elegant solution based on linear algebra seems to be the right approach here.

There is kind of an easy proof given that Berlekamp's algorithm works?

In the notation of https://en.wikipedia.org/wiki/Berlekamp%27s_algorithm, the point is that the space of polynomials g congruent to their p-th power is not going to contain anything but constants, because the p-th power map is a translation of the argument.

You might be interested in Artin-Schreier theory.

Here is an alternate proof of the OP's first conclusion, based on the same idea as David's, but which avoids consideration of coefficients. Let $r$ be a root of $h(x):=x^p-x+1$, so that $rnotinmathbf{F}_p$. Since $h(x+c)=h(x)$ for every $cinmathbf{F}_p$, the other roots of $h(x)$ are $r+1,r+2,dots,r+p-1$. Let $f(x)$ be the minimal polynomial of $r$ over $mathbf{F}_p$, and let $r+c$ be a root of $f(x)$ with $cne 0$. Write $h(x)=f(x)g(x)$, so that $$ f(x+c)g(x+c)=h(x+c)=h(x)=f(x)g(x). $$ Since $f(x)$ and $f(x+c)$ are monic irreducible polynomials in $mathbf{F}_p$ which both have $r$ as a root, they must be the same polynomial. Therefore the set of roots of $f(x)$ is preserved by the map $smapsto s+c$, so this set must include all the roots of $h(x)$.

I mention this variant of David's proof mostly in case this version might suggest generalizations to different types of settings.

---

Here is a proof of the OP's more general conclusion. Write $L(x)^{circ n}$ for the $n$-th iterate of $L(x):=x^p-x$. We compute $$ L(x)^{circ n} = (L(x)^{circ (n-1)})^p-L(x)^{circ (n-1)}=L(x)^{circ (n-1)}prod_{a=1}^{p-1} (L(x)^{circ (n-1)}+a) $$ $$= L(x)^{circ (n-1)}prod_{a=1}^{p-1}Bigl( a + sum_{j=0}^n {nchoose j}(-1)^jx^{p^j}Bigr). $$ It follows that $L(x)^{circ n}$ is divisible by $L(x)^{circ (n-1)}$, and the goal is to prove that for every $n$ there exists $k$ so that every irreducible factor of $f_n(x):=L(x)^{circ n}/L(x)^{circ (n-1)}$ in $mathbf{F}_p[x]$ has degree $p^k$.

The key step in the proof is the following claim: if $u$ is a root of $f_n(x)$, then all roots of $f_n(x)$ have the form $iu+L(w)$ where $iinmathbf{F}_p$ and $L^{circ n}(w)=0$. To prove this, first note that $L(x+dy)=L(x)+dL(y)$ for any $dinmathbf{F}_p$, so that $L^{circ n}(iu+j)=0$ for every $iinmathbf{F}_p$ and every root $j$ of $L^{circ (n-1)}(x)$. But the polynomial $L^{circ (n-1)}(x)$ is squarefree (since its derivative is $1$), so its roots form an $(n-1)$-dimensional $mathbf{F}_p$-vector space, and since $L^{circ (n-1)}(u)ne 0$ it follows that the above values $iu+j$ comprise $p^n$ distinct roots of $L^{circ n}(x)$, so every root has this form. Since $L^{circ (n-1)}(j)=0$, we can write $j=L(w)$ for some root $w$ of $L^{circ n}(x)$, which proves the claim.

Now we prove by induction on $n$ that for every $n$ there exists $k$ so that every irreducible factor of $f_n(x)$ in $mathbf{F}_p[x]$ has degree $p^k$. The base case $n=1$ is trivial (where $L(x)^{circ 0}=x$ by definition). Inductively, suppose that all irreducible factors of $f_n(x)$ have degree $p^k$.
Let $r,s$ be roots of $f_{n+1}(x)$. Then $u:=L(r)$ and $v:=L(s)$ are roots of $f_n(x)$, so that $mathbf{F}_p(u)=mathbf{F}_{p^k}=mathbf{F}_p(v)$, and by the above claim we have $v=iu+L(w)$ with $iinmathbf{F}_p$ and $L^{circ n}(w)=0$. Note that $ine 0$ since $L^{circ (n-1)}(v)ne 0$. Also $winmathbf{F}_{p^k}$, since if $wne 0$ then $w$ is a root of $f_{ell}(x)$ for some $ellle n$, so that $w=L^{circ (n-ell)}(z)$ for some root $z$ of $f_n(x)$, where $zinmathbf{F}_{p^k}$ by inductive hypothesis. By the Artin-Schreier theorem, $[mathbf{F}_p(r):mathbf{F}_{p^k}]$ is either $1$ or $p$, and is $1$ if and only if $L(x)-u$ has a root in $mathbf{F}_{p^k}$. This is equivalent to saying that $iL(x-w/i)-iu$ has a root in $mathbf{F}_{p^k}$, or in other words (with $y=ix$) that $L(y)-(iu+j)$ has such a root, which in turn says that $[mathbf{F}_p(s):mathbf{F}_{p^k}]=1$. Therefore $mathbf{F}_{p}(r)=mathbf{F}_{p}(s)$, and this field is either $mathbf{F}_{p^k}$ or $mathbf{F}_{p^{k+1}}$, as desired.

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}_pleft[xright]$ 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$.