# Existence of irreducible polynomials over finite field

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.

-
$p$ has no roots, but why is it irreducible? –  Chris Eagle May 13 '12 at 19:50
Several other threads on this site have answered this question by using the classification of finite fields. Essentially: If $|F|=q=p^m$, there exists a unique field of size $q^n$. The minimal polynomial of a primitive element of that extension field must have degree $n$. Q.E.D. –  Jyrki Lahtonen May 13 '12 at 20:05
To @Chris: yes, I assumed that if $p(x)$ has no roots it is reducible, I forgot situation of the type $(x^2 - 2)(x^2 - 3)$ say, over $\mathbb{Q}$. I don't have good intuition with finite fields. –  Zachi Evenor May 13 '12 at 20:39
As far as I know, if you want to prove from scratch that every finite field admits an irreducible polynomial of every degree $n \in \mathbb{Z}^+$ -- i.e., you don't want to use any field or Galois theory -- then the Mobius function argument is the most elementary and quickest way to go. Sometimes the best way to show that something exists is to count the number of such things and show that the count is positive! –  Pete L. Clark May 13 '12 at 20:41
$\LaTeX$ tip: don't use (\mod p), because the spacing around \mod is incorrect. For the parenthetical version, use \pmod{p} to produce $\pmod{p}$. For the binary relation version, such as $3\bmod 5=2$, use \bmod. –  Arturo Magidin May 13 '12 at 21:39

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$.
Jyrki Lahtonen generalized your proof for $F=\mathbb{F}_{p^m}=GF(p^m)$ and $K=GF(p^mn)=GF((P^m)^n)$. Thanks. –  Zachi Evenor May 13 '12 at 21:32
This proof relies on the existence of the field $\mathbb F_{p^n}$. Sometimes, the existence of $\mathbb F_{p^n}$ is proven using the existence of an irreducible polynomial of degree $n$ over $\mathbb F_p$, and we are caught in a circular argument. To avoid this, the existence of $\mathbb F_{p^n}$ can alternatively be shown as the splitting field of $x^{p^n} - x\in \mathbb F_p[x]$. –  azimut Oct 7 '13 at 17:40