How to show that if $\pi(x) \mid x^{p^n} - x$ then $\deg(\pi(x)) \mid n$? I'm in the middle of the proof about $P_n = x^{p^n} - x \in F_p[x]$ for p prime, being the product of all monic, irreducible polynomials of degree $d$ such that $d \mid n$.
I've already proved that if $\pi(x) \in F_p[x]$ is monic, irreducible, such that $\deg(\pi(x)) \mid n$ then $\pi(x) \mid P_n$.
I've also proved that there are no irreducible factors with multiplicity in the factorization of $P_n$.
It remains to prove that every factor of $P_n$ is of the form $\pi(x)$, that is, if $r(x) \in F_p[x]$ is a monic, irreducible polynomial of degree $d$, such that $r(x) \mid P_n$, than $d | n$.
How can I go on with that to finish the proof? Here's what I was trying:
Let $\pi(x) \in F_p[x]$ be a monic and irreducible polynomial of $\deg(\pi(x)) = d$, such that $\pi(x) | P_n$. Since $\pi(x) | P_d$, it implies that $\pi(x) \mid P_{\gcd(n,d)}$. Now suppose that $d \nmid n$, therefore $\gcd(n,d) < d$... 
(Now I'm aiming for a contradiction in the fact that $\pi(x) \mid P_{\gcd(n,d)}$ or $\pi(x) \mid P_n$, but idk how to continue...)
I'm new to finite fields and abstract algebra, so please, if it's possible, don't use more advanced techniques.
Thanks for your time and help.
 A: Consider the following field : $F:=\mathbb F_p[x]/(r)$ (it's a field because $r$ is irreducible of course). 
This field has $p^d$ elements, therefore by Lagrange's theorem applied to $F^\times$, we see that each of its elements is a root of $X^{p^d}-X$, so $X^{p^d}-X = \prod_{a\in F}(X-a)$
Now note the following thing : in a characteristic $p$ field, $(a+b)^{p^k} = a^{p^k}+ b^{p^k}$ for any integer $k$. 
It follows that if we let $\alpha$ denote the image of $x$ in $F$, and if $P$ is a polynomial, then $P(\alpha)^{p^n} = P(\alpha^{p^n}) = P(\alpha)$ (indeed, $\alpha^{p^n} = \alpha$ because $r\mid P_n$, so $\alpha$ is a root of $p^n$).
Therefore, $P(\alpha)$ is also a root of $P_n$. But $F$ consists of elements of this form : any element of $F$ is a root of $P_n$ !
Therefore $P_d\mid P_n$, and it's easy to see that this divisibility relation holds in $\mathbb F_p[x]$, not only $F[x]$ (to see why, think about euclidean division). 
Do you know that this implies $d\mid n$ ? (I think you do, since you mentioned $P_{gcd(d,n)}$) If yes, then we are done. Else, I'll add something to that effect. 
