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?

A very simple counting estimation will show that such polynomials have to exist. Let $q=p^k$ and $F=\Bbb F_q$, then it is known that $X^{q^n}-X$ is the product of all irreducible monic polynomials over$~F$ of some degree$~d$ dividing $n$. The product$~P$ of all irreducible monic polynomials over$~F$ of degree strictly dividing $n$ then certainly divides the product over all strict divisors$~d$ of$~n$ of $X^{q^d}-X$ (all irreducible factors of$~P$ are present in the latter product at least once), so that one can estimate
$$
  \deg(P)\leq\sum_{d\mid n, d\neq n}\deg(X^{q^d}-X)\leq\sum_{i<n}q^i=\frac{q^n-1}{q-1}<q^n=\deg(X^{q^n}-X),
$$
so that $P\neq X^{q^n}-X$, and $X^{q^n}-X$ has some irreducible factors of degree$~n$.
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.
