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?
 A: $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.
A: 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$.
A: $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.
A: 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.
A: 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$.
A: $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.$
A: 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.
A: A little bit late, but I have no doubt people will still come back to this question.
To the proof:
If $r$ is a root of $f$ then $r+j$ is a root of $f$, for $j\in \mathbb F_p$. If $r\in \mathbb F_p$, then $0$ is a root of $f$, but $f(0)=a\neq 0$. Therefore, $f$ has no roots in $\mathbb F_p$. Let $r$ be a root of $f$. Then $\mathbb F_p(r)$ is Galois over $\mathbb F_p$, since all roots are of the form $r+j$, and $f'(x)=-1\neq 0$ so $f$ is separable.
There exists an automorphism of $\mathbb F_p(r)$ given by $\sigma(r)=r+1$. Therefore, $\sigma^j(r)=r+j$, and therefore $r+j$ is a root of the minimal polynomial of $f$, for all $j\in \mathbb F_p$. Therefore, $f$ is irreducible.
