How many irreducible polynomials of degree six are there over \(\FF_2\)?
Solution
Let \(N_q(n)\) denote the number of monic irreducible polynomials of degree \(n\) over \(\FF_q\).
1. One has\[ q^n=\sum_{d\mid n} d\,N_q(d). \]
The polynomial \(x^{q^n}-x\) has as its roots exactly the elements of \(\FF_{q^n}\) and is squarefree. Its irreducible factors over \(\FF_q\) are exactly the monic irreducibles whose degrees divide \(n\). Each degree-\(d\) irreducible contributes \(d\) roots, so comparison of degrees gives the formula.
2. Möbius inversion gives\[ N_q(n)=\frac1n\sum_{d\mid n}\mu(d)q^{n/d}. \]
Apply ordinary Möbius inversion to the identity in 1.
3. For \(q=2\) and \(n=6\),\[ N_2(6)=9. \]
The divisors of \(6\) are \(1,2,3,6\), with Möbius values \(1,-1,-1,1\). Hence \[ N_2(6) = \frac16\left(2^6-2^3-2^2+2\right) = \frac{64-8-4+2}{6} =9. \]
Thus there are exactly \(9\) monic irreducible degree-\(6\) polynomials over \(\FF_2\).