Existence of an irreducible polynomial over $\mathbb F_p$. 
Possible Duplicate:
Lack of understanding of the proof of the existence of an irreducible polynomial of any degree $n \geq 2$ in $\mathbb{Z}_p[x]$
Existence of irreducible polynomials over finite field 

I need to prove that there exists an irreducible polynomial of degree $n$ over $\mathbb F_p$. Here is what I know so far:


*

*The polynomial $x^{p^n} - x$ is the product of all monic irreducible polynomials of degrees dividing $n$.

*The above polynomial has no roots with multiplicities $>1$. So, has $p^n$ distinct roots in some field.

*A monic irreducible polynomial of degree $d$ over $\mathbb F_p$ has the form $$(x - \alpha)(x-\alpha^p)\cdots(x - \alpha^{p^{d-1}}),$$ where all the $\alpha^{p^i}$ are distinct.

*Map $a\mapsto a^p$ is an automorphism of any finite field of characteristic $p$ and so are all it's iterations.

*I know Möbius inversion formula and can therefore count monic irreducible polynomials from the above information, and get the formula $I_n = \frac 1n\sum_{d|n}p^d\mu(n/d)$ for their number. I don't know that this number is not zero.


What I "do not know" is the existence of a finite field of $p^n$ elements. In fact, my aim is to prove the existence of such a field from the existence of polynomial. I also "do not know" any Galois theory.
It seems that $I_n>0$ could be shown by induction from the above expression, but I run into inclusion-exclusion and get confused. Is there a more transparent argument for why there must be an irreducible polynomial of degree n over $\mathbb F_p$?
Thank you!
 A: Sometimes it's best to start with a "simple case", and see where that leads us. So let's start by just looking at where $n=q$, a prime number. It is easy to see the polynomial: $f(x) = x^{p^q} - x$ has no repeated root, as its derivative is $p^qx^{p^q - 1} - 1 = -1$ and thus shares no roots with $x^{p^q} - x$.
Since there are only $p$ elements of $\Bbb F_p$, $f$ must have some irreducible factor of degree > $1$. Let's call this factor $g$. If $\deg(g) = t$, we therefore have a field $K$ with $p^t$ elements. Suppose $u$ is a root of $g$ that lies in this field. Then every element of $K$ can be written as a $\Bbb F_p$-linear combination of $\{1,u,...,u^{t-1}\}$. So if $y\in K$:
$\displaystyle f(y) = y^{p^q} - y = \left(\sum_{j=0}^{t-1} \alpha_ju^j\right)^{p^q} - \sum_{j=0}^{t-1}\alpha_ju^j = \sum_{j=0}^{t-1} \alpha_j^{p^q}u^{jp^q} - \sum_{j=0}^{t-1}\alpha_ju^j$.
Since $\alpha_j \in \Bbb F_p$, $\alpha_j^{p^q} = \alpha_j$, and since $u$ is a root of $f$, $u^{jp^q} = u^j$, so $f(y) = 0$. So every element of $K$ is a root of $f$. This, in turn, implies that:
$x^{p^t} - x|x^{p^q} - x$, so $x^{p^t-1}-1|x^{p^q-1}-1$, so $p^t - 1|p^q - 1$, and thus $t|q$. Since by assumption $t > 1$, $t = q$. This is truly "the hard part".
For now, we write $n = q_1^{r_1}q_2^{r_2}\cdots q_k^{r_k}$. Using the same construction, we first construct a field of $p^{q_1}$ elements, then a field of $(p^{q_1})^{q_1} = p^{q_1^2}$ elements, and continuing in like fashion until we have a field of $p^{q_1^{r_1}}$ elements, and then move on to $q_2$, etc. until we exhaust all the prime factors of $n$.
