Let $F$ be a finite field. How do we prove that for each $n \in \mathbb{N}$ there is an irreducible polynomial of degree $n$?
One can assume that $F = \mathbb{F}_{p^m}$ where $p$ is prime. If $n \ge |F|$ then I can construct an irreducible polynomial, namely
$ p(x) = 1 + \prod_{j=1}^{|F|} ( x - a_j )$
where $a_j$ are all the field elements. It is clear that $p(x)$ has no roots in $F$.
This trick doesn't work for $n < |F|$. A counter-example: Let $F = \mathbb{F}_3$ and $p(x) = 1 + (x-1)(x-2)$, then $p(1) = 1$, $p(2) = 1$, $p(0) = 1 + (-1)(-2) = 1 + 2 = 3 = 0 \pmod 3$.
I know there is a way to count them using the Möbius function $\mu(n)$ but I want a proof without it that just shows existence.