In Reutenauer's "Free Lie Algebras", section 7.6.2:
A direct bijection between primitive necklaces of length $n$ over $F$ and the set of irreducible polynomials of degree $n$ in $F[x]$ may be described as follows: let $K$ be the field with $q^n$ elements; it is a vector space of dimension $n$ over $F$, so there exists in $K$ an element $\theta$; such that the set $\{\theta, \theta^q, ..., \theta^{q^{n-1}}\}$ is a linear basis of $K$ over $F$.
With each word $w = a_0\cdots a_{n-1}$ of length $n$ on the alphabet $F$, associate the element $\beta$ of $K$ given by $\beta = a_0\theta + a_1\theta^q + \cdots + a_{n-1} \theta^{q^{n-1}}$. It is easily shown that to conjugate words $w, w'$ correspond conjugate elements $\beta, \beta'$ in the field extension $K/F$, and that $w \mapsto \beta$ is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality $n$ in $K$; to the latter corresponds a unique irreducible polynomial of degree $n$ in $F[x]$. This gives the desired bijection.
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$.
Best Answer
The product of all monic irreducible polynomials of degree dividing $d$ in $\mathbb F_q[x]$ is $$x^{q^d}-x,$$ so from Mobius inversion we get the number of irreducible polynomials of degree $d$ is $$M _d (q) = \frac{1}{d} \sum _{k | d} \mu(k) q ^{d/k} $$ This is known as the necklace polynomial.