Here is a fundamental fact that is essential in the proof of the classification theorem:
Let $ p $ be a prime and $ n $ a positive integer. Then, in $ {\mathbb F}_p[x]$,
$$
x^{p^n}-x = \prod_{d|n} \prod_{\stackrel{f(x) \text{ monic, irred.}}{\text{deg}(f)=d}} f(x).
$$
Proof of the fact:
There are a few steps. First note that $ x^{p^n}-x $ has no repeated factors: if it did, its derivative would share a common factor with it, but its derivative is just $ -1 $, which has no nontrivial factors.
Now, suppose $ f(x) $ is irreducible of degree $ d|n $. Then $ {\mathbb F}_p[x]/(f(x)) $ is a finite field of order $ p^d $. So if $ f(x) \ne x $, in that field $ {\overline x}^{p^d-1} = 1 $, by a generalization of Fermat's little theorem. This means that $ f(x) $ divides $ x^{p^d-1} -1 $. If $ d|n$, $ (p^d-1) | (p^n-1)$, so $ f(x) $ divides $ x^{p^n-1}-1, $ hence divides $ x^{p^n}-x $.
The last step is to show that no other factors divide $ x^{p^n}-x $. This is best done by induction and using the fact that $ \gcd(p^k-1,p^n-1) = p^{\text{gcd}(k,n)}-1 $, but the details are omitted. $_\square$
Taking the degrees of both sides gives a useful corollary:
Corollary:
For primes $ p $ and positive integers $ n $, let $ \nu_p(n) $ be the number of monic irreducible polynomials of degree $n $. Then
$$
p^n = \sum_{d|n} d\nu_p(d)
$$
and by Möbius inversion,
$$
\nu_p(n) = \frac1{n} \sum_{d|n} \mu(n/d) p^d.
$$
| 
