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

  • 4
    $p$ has no roots, but why is it irreducible?2012-05-13
  • 4
    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.2012-05-13
  • 0
    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.2012-05-13
  • 0
    To @Jyrki , I think there is more elementary proof, that doesn't use Mobius function.2012-05-13
  • 6
    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!2012-05-13
  • 4
    $\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`.2012-05-13
  • 0
    @LeonMeier: Good catch; alas, five years later it is too late for me to edit the comment.2017-06-27

1 Answers 1

23

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

  • 0
    Jyrki Lahtonen generalized your proof for $F=\mathbb{F}_{p^m}=GF(p^m)$ and $K=GF(p^mn)=GF((P^m)^n)$. Thanks.2012-05-13
  • 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