Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

1 Answer 1

up vote 4 down vote accepted

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 poltnomials 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 poof though.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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