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.

  • 9
    $\begingroup$ $p$ has no roots, but why is it irreducible? $\endgroup$ May 13 '12 at 19:50
  • 4
    $\begingroup$ 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. $\endgroup$ May 13 '12 at 20:05
  • $\begingroup$ 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. $\endgroup$ May 13 '12 at 20:39
  • 7
    $\begingroup$ 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! $\endgroup$ May 13 '12 at 20:41
  • 5
    $\begingroup$ $\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. $\endgroup$ 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$.

  • $\begingroup$ Jyrki Lahtonen generalized your proof for $F=\mathbb{F}_{p^m}=GF(p^m)$ and $K=GF(p^mn)=GF((P^m)^n)$. Thanks. $\endgroup$ May 13 '12 at 21:32
  • 42
    $\begingroup$ 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]$. $\endgroup$
    – azimut
    Oct 7 '13 at 17:40
  • $\begingroup$ Note that $\alpha$ does not need to be a generator of the multiplicative group of $K$ for its minpoly to be a degree $n$ irreducible polynomial. For example, if $K = \mathbb{F}_{2^4} / \mathbb{F}_2$ has 12 degree $4$ elements (one way to see this is because there are 3 irreducible polynomial of degree $4$), but $\phi(2^4 -1)=8$. $\endgroup$
    – eatfood
    Nov 21 '19 at 18:09
  • $\begingroup$ @eatfood: You mean, "one need not choose $\alpha$ to be a generator of the multiplicative group of $K$". Because I choose it to be such a generator, so it does need to be a generator. $\endgroup$ Nov 21 '19 at 18:12
  • $\begingroup$ @ArturoMagidin Yup that is what i meant. I used to have the misconception that only the generators of the multiplicative group had minpoly of degree $4$, but recently learnt (from else where on this site) that there exists elements that don't generate the multiplicative group, but still have minpoly degree $4$. I can't edit my comment anymore though. $\endgroup$
    – eatfood
    Nov 21 '19 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.