16
$\begingroup$

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.

  • 0
    @LeonMeier: Good catch; alas, five years later it is too late for me to edit the comment.2017-06-27

1 Answers 1

27

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$.

  • 25
    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]$.2013-10-07