# 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?

-
Yes. See this for the case $k=1$. The same argument works when $k>1$. I like to think that the more general version has been covered here. The Möbius inversion formula for the number of irreducible polynomials works out irrespective of whether $k=1$ or not, and the linked question explains, how to deduce that the number is always positive. – Jyrki Lahtonen Jan 27 '13 at 15:35
Alternatively you can use the argument of the linked question to prove the existence of an irreducible polynomial of degree $nk$ over the prime field. The factors of that polynomial (over the extension field) are then necessarily of degree $n$. – Jyrki Lahtonen Jan 27 '13 at 15:39
Does the fact that the multiplicative group is cyclic count as a use of the primitive element theorem? – Lior B-S Jan 27 '13 at 18:00
For $n=2$ and $n=3$ there exists a truly elementary proof, which is unfortunately hard to generalize... – N. S. Jan 27 '13 at 18:34
@HailieMathison I think the following is one way to answer your question. Let $n>0$ be given. Since $k$ divides $kn$, we know that $F_{p^k}$ embeds in $F_{p^{kn}}$. Knowing that $F_{p^{kn}}^*$ is cyclic, let $\alpha\in F_{p^{kn}}^*$ generate $F_{p^{kn}}^*$. Then we must have $F_{p^k}(\alpha)=F_{p^{kn}}$ and thus the minimal polynomial of $\alpha$ over $F_{p^k}$ has degree $[F_{p^{kn}}:F_{p^k}]=n$. – caffeinemachine Mar 14 at 13:54

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<n}q^i=\frac{q^n-1}{q-1}<q^n=\deg(X^{q^n}-X),$$ 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.