Irreducible factors of a finite-field Frobenius polynomial ($X^{q^n}-X$)

Every monic irreducible polynomial over ${\mathbb{F}}_q$ whose degree divides $n$ divides $X^{q^n}-X$. In particular, if $f$ has degree $n$ and $\alpha$ is one of its roots, then ${\mathbb{F}}_q(\alpha )$ has $q^n$ elements, so ${\alpha }^{q^n}=\alpha$ and the minimal polynomial $f$ divides $X^{q^n}-X$.

Let $N_q(n)$ be the number of monic irreducible polynomials of polynomial degree $n$ over ${\mathbb{F}}_q$. Factoring $X^{q^n}-X$ into all such polynomials whose degrees divide $n$ givesThe Möbius inversion formula therefore gives