# 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 $$\frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})q^d$$ 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. –  William D. Dec 19 '11 at 17:13

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