Number of monic irreducible polynomials over a finite field

Let $\mathbb{K}=\mathbb{F}_q$ and $\nu_n$ denote the number of monic irreducible polynomials over $\mathbb{K}$. It holds $$\nu_n=\frac{1}{n}\sum_{d\mid n}\mu\left(\frac{n}{d}\right)q^d$$ What I need to show is something similar:$$\sum_{k\mid n}k\nu_k=q^n$$ So, given the formula of $\nu_n$, we get $$\sum_{k\mid n}k\nu=\sum_{k\mid n}\sum_{d\mid k}\mu\left(\frac{k}{d}\right)q^d$$ How can we simplify and conclude from here?

Solution 1:

Suppose $\mathbb{F}_{q^n}$ is a finite field. Then $$[\mathbb{F}_{q^n} : \mathbb{F}_q ] = n$$

The elements of $\mathbb{F}_{q^n}$ are precisely the roots of $$p_n(x) = x^{q^n} - x \ \ \in \mathbb{F}_q[x]$$ Thus your formula derive from a counting argument, because try to consider all the minimal polynomials over $\mathbb{F}_q$ of the roots of $p_n(x) $.

All such polynomials have degree $k \mid n $ because their roots are contained in the extension $( \mathbb{F}_{q^n} : \mathbb{F}_{q})$ of degree $n$ .

Moreover an irreducible monic polynomial of degree $k \mid n $ has roots wich are in $\mathbb{F}_{q^n}$ because if $\alpha$ is one of its roots, it is in an extension of degree $k$ and so satisfies $$\alpha^{q^{k-1}} -1 = 0$$ because the multiplicative group of a finite field is cyclic.

Then if you count all the roots of the monic irreducible polynomial of degree $k \mid n $ you obtain $|\mathbb{F}_{q^n} | $ i.e. $$\sum_{k\mid n}k\nu_k=q^n$$