galois theory - Existence of irreducible polynomial of arbitrary degree over finite field without use of primitive element theorem?

Suppose $F_{p^k}$ is a finite field. If $F_{p^{nk}}$ is some extension field, then the primitive element theorem tells us that $F_{p^{nk}}=F_{p^k}(\alpha)$ for some $\alpha$, whose minimal polynomial is thus an irreducible polynomial of degree $n$ over $F_{p^k}$.

Is there an alternative to showing that irreducible polynomials of arbitrary degree $n$ exist over $F_{p^k}$, without resorting to the primitive element theorem?

Answer

A very simple counting estimation will show that such polynomials have to exist. Let $q=p^k$ and $F=\Bbb F_q$, then $X^{q^n}-X$ is the product of all irreducible polynomials over $F$ of degree dividing $n$. The degree of the product of all irreducible polynomials over $F$ of degree strictly dividing $n$ can then be estimated as at most
$$
\sum_{d\mid n, d\neq n}q^d\leq\sum_{i$$
so they cannot account for all the irreducible factors of $X^{q^n}-X$.

I should add that by starting with all $q^n$ monic polynomials of degree $n$ and using the inclusion-exclusion principle to account recursively for the reducible ones among them, one can find the exact number of irreducible polynomials over $F$ of degree $n$ to be

$$\frac1n\sum_{d\mid n}\mu(n/d)q^d,$$
which is a positive number by essentially the above argument (since all values of the Möbius function $\mu$ lie in $\{-1,0,1\}$ and $\mu(1)=1$). A quick search on this site did turn up this formula here and here, but I did not stumble upon an elementary and general proof not using anything about finite fields, although I gave one here for the particular case $n=2$. I might well have overlooked such a proof though.