# Counting Irreducible Polynomials

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?

• 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
• Note: The Möbius function is defined by $$\mu(n) = \begin{cases} 0 & \text{when } n \text{ has one or more repeated prime factors} \\ 1 & \text{when } n=1 \\ (-1)^k & \text{when } n \text{ has exactly } k \text{ distinct prime factors} \end{cases}$$ – hardmath Nov 20 '17 at 1:24

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