Proving that $f(x)$ divides $x^{p^n} - x$ iff $\deg f(x)$ divides $n$ 
Prove that $f(x)$ divides $x^{p^n} - x$ if and only if $d := \deg f(x)$ divides $n$.

I believe that I have the backward direction covered: Let $d \mid n$ say $n = dq$ for some $q$ in $\mathbb{F}_p[x]$. Consider the field $\mathbb{F}_p[x]/(f(x))$ which has $p^d$ elements. Take an element $x+I$ from the field (here $I = (f(x))$) so we have: $(x+I)^{p^n} = (x+I)^{p^{dq}}$. As long as you keep factoring out $(x+I)$ with the $p^d$ power you will get $(x+I)$ so $x^{p^n} - x \in (f(x))$.
I am having trouble getting to the other direction. 
 A: This question is very old, but there is a more direct solution worth noting.
Proof. 
Suppose $f(x)$ divides $h(x):=x^{p^n} -x$. Then since $h(x)$ splits over $\mathbb{F}_{p^n}$, so does $f(x)$. Let $\alpha \in \mathbb{F}_{p^n}$ be a root of $f(x)$. Then $\mathbb{F}_{p}(\alpha)\subset \mathbb{F}_{p^n}$, and $[\mathbb{F}_p(\alpha): \mathbb{F}_p] = d$. Finally, we have that $n = [\mathbb{F}_{p^n}: \mathbb{F}_p]= [\mathbb{F}_{p^n}: \mathbb{F}_p(\alpha)][\mathbb{F}_p(\alpha): \mathbb{F}_p]$, completing the proof that $d | n$.
A: Hints:
(i) Show that the splitting field of the polynomial $\,p(x):=x^{p^n}-x\in\Bbb F_p[x]\,$ over the prime field $\,\Bbb F_p\,$ is the field $\,\Bbb F_{p^n}\,$
(ii) One way to go: show that the set of roots of the above polynomial $\,p(x)\,$ in some algebraic closure of $\,\Bbb F_p\,$ is a field...
(iii) Prove that $\,\Bbb F_{p^d}\,$ is a subfield of $\,\Bbb F_{p^n}\,$ iff $\,d\mid n\,$
Of course, take into account that $\,f(x)\mid p(x)\Longrightarrow\,$ all the roots of $\,f(x)\,$ are also roots of $\,p(x)\,$
