Quoting from Herstein's Abstract Algebra (3rd edition):
Lemma 6.4.1. If $q(x)$ in $\mathbb{Z}_p[x]$ is irreducible of degree $n$, then $q(x) \mid (x^m- x)$, where $m = p^n$.
Proof. By Theorem 4.5.11 the ideal $(q(x))$ of $\mathbb{Z}_p[x]$ generated by $q(x)$ is a maximal ideal of $\mathbb{Z}_p[x]$ since $q(x)$ is irreducible in $\mathbb{Z}_p[x]$. Let $A = \mathbb{Z}_p[x]/(q(x))$; by Theorem 4.4.3, $A$ is a field of degree $n$ over $\mathbb{Z}_p[x]$, hence has $p^n$ elements. Therefore, $u^m= u$ for every element $u$ in $A$. Let $a= x+(q(x))$ be the coset of $x$ in $A = \mathbb{Z}_p[x]/(q(x))$; thus $q(a)= 0$ and $q(x)$ is the minimal polynomial for $a$ over $\mathbb{Z}_p[x]$. Since $a$ is in $A$,$a^m= a$,so $a$ is seen as a root of the polynomial $x^m- x$, where $m = p^n$. Thus $x^m- x$ and $q(x)$ have a common root in A. By Lemma 6.3.2 we have that $q(x) \mid (x_m- x)$.
I have two questions about it:
1) I don't understand why $q(a)$ should be equal to $0$. Probably I'm just looking at things from the wrong point of view, but every element in $A$ is (the equivalence class of) a polynomial of degree at most $n-1$. So..? What are we using to conclude that $q(a)=0$?
2) I was trying to do another kind of reasoning: knowing that, for every $f(x) \in F[x]$ of degree $n$ there exists a finite extension $K$ of $F$ such that $f(x)$ splits into linear factors over $K$ (theorem 5.6.6 for those who have the book) and that $x^m-x = (x-k_1)\cdots(x-k_m)$, where $k_1,\ldots,k_m$ are all the elements of K, can we conclude that $q(x)$ has at least one root in common with $x^m-x$ and so $q(x) \mid (x^m- x)$? I'm a bit confused about it, I feel like I'm slipping in more than one step...
thanks for your help!
EDIT:
Elaborating my reasoning, if we consider $q(x) \in F[x]$ and the finite extension $K$ of $F$ where $q(x)$ splits into linear factors, we know we can write $q(x)=(x-k_1)\cdots(x-k_n)$ where $n$ is the degree of $q(x)$. At the same time $K$ is finite over $F$, so we can write the factorization $x^m-x=(x-k_1)\cdots(x-k_m)$, where, this time, $k_i$ runs over all the $m$ elements of $K$. So, if every root of $q(x)$ has multiplicity $1$ then we can simply write $x^m-x=q(x)(x-k_{n+1})\cdots(x-k_m)$ (up to reordering). Not sure how can we get a result in the same form if $q(x)$ has roots with higher multiplicity (but, as the theorem is correct, there should be a way...).
1) It's because $A$ is defined to be $k[x]/(q(x))$. Using $\overline{f}$ to denote the residue class in $A$ of an element $f \in A$ you have: $a = \overline{x}$ and so $q(a) = q(\overline{x}) = \overline{q(x)} = \overline 0$. (The critical step you might be missing is $q(\overline x) = \overline{q(x)}$, which holds more generally as $q(\overline f) = \overline{q(f)}$. This is because the map $f \mapsto \overline{f}$ is a ring homomorphism and hence respects the multiplications and additions being done by evaluating $q$ at $f$, resp. $\overline{f}$).
2) It's difficult to judge this approach. You don't give a reason why $q(x)$ and $x^m - x$ share a root. Ultimately, of course, all roots of $q(x)$ are roots of $x^m - x$, so I can't give a counterexample.