I and some friends just came up with this. (We came up with some ideas for the proof, after coming across the formula on the internet.) This is the coolest application of the Möbius inversion formula that I’ve seen so far.

Let be a prime power and any positive integer. We wish to count the number of monic irreducible polynomials of degree over the finite field .

Note that the zeros of

are precisely the elements of degree over , where the product is taken over monic irreducible polynomials . Further, we have the following:

**Lemma 1. **Let be relatively prime polynomials over a field . Then and have no common zeros.

*Proof.* Since is a PID, there are polynomials such that . If is a common zero of and in some extension , then divides in , a contradiction.

**Lemma 2. **If is irreducible over a field , then has distinct zeros.

*Proof.* Note that any multiple zero of must be a common zero of and its formal derivative . Since is irreducible over , it follows that and are relatively prime over . Now apply lemma 1 to and .

It follows that the zeros of

are all distinct and are precisely the elements of the union of all the subfields of , which is just . This implies

,

since is the splitting field of over . Now a comparison of the degrees of both sides reveals that

.

Finally, Möbius inversion gives

.