Gauss's Formula

Theorem (Gauss’s formula)

Let $p$ be prime. If $N_{d}$ denotes the number of monic irreducible polynomials of degree $d$ (where $d\le n$ ) in $\mathbb{F}_{p}[x]$ then $p^{n}=\sum_{d|n}dN_{d}$ which by the Möbius Inversion Formula gives us $\begin{align*} nN_{n}&=\sum_{d|n}\mu(d)p^{\frac{n}{d}}\\ &\iff\\ N_{n}&=\frac{1}{n}\sum_{d|n}\mu(d)p^{\frac{n}{d}} \end{align*}$ where $\mu$ is the Möbius Function.

Cor

$N_{n}\ge 1$ for every value of $n\ge1$ . i.e. For every value of $n$ , there is an irreducible polynomial of degree $n$ in $\mathbb{F}_{p}[x]$ .

Intuition

This gives us an analytic formula $N_{n}=\frac{1}{n}\sum_{d|n}\mu(d)p^{\frac{n}{d}}$ giving us a way to find the number of monic irreducible polynomials of degree $n$ in $\mathbb{F}_{p}[x]$ .