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
Let be Euler’s function, i.e., the number of positive integers not exceeding that are coprime to . A famous identity goes as follows:
where the sum is taken over all positive divisors of . Here is a counting argument for a proof.
Let . For each divisor of , let us count the number of elements with . When , this is just . What about when ? If is odd then clearly there is no such . Otherwise, implies that and must both be even. Moreover, this happens iff . Hence, as before, the number of such is .
This works in general: for any , the number of elements such that is . So summing over all , which is the same as summing over all , gives the total number of elements of , which is . This proves the desired result.
This begs for a generalisation. I will add it here when I come up with one. (I really need to sleep now!)