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.
Best Answer
The multiplicative group of nonzero elements of any finite field is cyclic; so if $K=\mathbb{F}_{p^n}$, letting $\alpha$ be a generator of the multiplicative group of $K$, we have that $K=\mathbb{F}_p(\alpha)$. In particular, the minimal polynomial of $\alpha$ over $\mathbb{F}_p$, which is irreducible, must have the same degree as $[\mathbb{F}_p(\alpha):\mathbb{F}_p] = [K:F] = n$, so there must exist an irreducible polynomial over $\mathbb{F}_p$ of degree $n$.