Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
@HailieMathison I think the following is one way to answer your question. Let $n>0$ be given. Since $k$ divides $kn$, we know that $F_{p^k}$ embeds in $F_{p^{kn}}$. Knowing that $F_{p^{kn}}^*$ is cyclic, let $\alpha\in F_{p^{kn}}^*$ generate $F_{p^{kn}}^*$. Then we must have $F_{p^k}(\alpha)=F_{p^{kn}}$ and thus the minimal polynomial of $\alpha$ over $F_{p^k}$ has degree $[F_{p^{kn}}:F_{p^k}]=n$. – caffeinemachine Mar 14 at 13:54
up vote 8 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 polynomials 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 proof though.

share|cite|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.