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

I'm investigating irreducible polynomials over finite fields at the moment, and I wanted to know if there is a formula for the number of irreducible polynomials of degree n over a fixed finite field $\mathbb{F}_q$. Wolfram MathWorld gives the formula \begin{equation} \frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})q^d \end{equation} However, neither it nor the OEIS page it links to offers any proof for this as far as I can tell, and I'm kind of confused by the presence of a divisor sum; I don't see why such a sum would appear in dealing with these polynomials.

So how does one prove this formula?

share|cite|improve this question
This question has been answered previously on this site. See for example here – Dilip Sarwate Dec 19 '11 at 15:53
Anyhow, this looks like the Mobius inversion formula. If $f(n)$ is the number of irreducible polynomials, this formula suggests that $q^n= \sum_{d|n} df(d) $, which doesn't look obvious to me... – N. S. Dec 19 '11 at 15:56
@N.S.: That's obvious once you know that $x^{q^n}-x$ is the product of all the (monic) irreducible polynomials over $\mathbb{F}_q$ of degree dividing $n$. – Chris Eagle Dec 19 '11 at 16:05
@Dilip: Sorry; for some reason I didn't notice. Thanks for pointing that out. – Will Dana Dec 19 '11 at 17:13
up vote 8 down vote accepted

Let $N_q(n)$ be the number of irreducible monic polynomials in $\mathbb{F}_q[x]$ of degree $n$. First prove that $$q^n = \sum_{d|n} d\cdot N_q(d).$$ Then, you can use the additive version of the Möbius inversion formula with $H(n)=q^n$ and $h(n)=nN_q(n)$, so that $H(n)=\sum_{d|n} h(d)$ implies that $h(n)=\sum_{d|n}\mu(\frac{n}{d})H(d)$.

share|cite|improve this answer
I always liked to show my students this, whenever I taught algebra. – Lubin Dec 20 '11 at 3:56
It is indeed a very neat application of Mobius inversion! – Álvaro Lozano-Robledo Dec 20 '11 at 4:06
Thank you for pointing this out. – Will Dana Dec 20 '11 at 6:32

You may also have a look at A Classical Introduction to Modern Number theory, by Ireland and Rose, page 84.

share|cite|improve this answer
Thank you; that's a very helpful resource. – Will Dana Dec 20 '11 at 6:32

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.