# Number of irreducible polynomials over a finite field

Over a finite field, there are of course only finitely many irreducible monic polynomials. But how do you count them? Let $q = p^n$ be a power of a prime and let $N_q(d)$ denote the number of monic irreducible polynomials of degree $d$ over $\F_q$. The key to finding $N_q(d)$ is the following fact: the product of all the monic, irreducible polynomials of degree $d$ with $d \mid n$ in the finite field $\mathbb{F}_q$ is the polynomial
$$x^{q^n} – x.$$
So let's say $f_1,f_2,\dots, f_k$ are all the irreducible monic polynomials of degree $d$ with $d\mid n$. By taking degrees on both sides of the equation $x^{q^n} -x = f_1f_2\cdots f_k$, we get the formula
$$q^n = \sum_{d\mid n} dN_q(d).$$
Hey this is pretty good! For example, if $q = 2$ and $n = 3$ then the formula reads
$$8 = N_2(1) + 3N_2(3)$$
Now, $N_q(1)$ is always easy to figure out. All monic linear polynomials are irreducible so $N_q(1) = q$. Therefore, $N_2(3) = 2$. In fact, these two polynomials are: $x^3 + x + 1$ and $x^3 + x^2 + 1$. Okay, what about if $q = 3$ and $n = 6$? Then our formula tells us that
$$3^6 = N_3(1) + 2N_3(2) + 3N_3(3) + 6N_3(6).$$
So we now have to recursively compute: if we did that we would get that $N_3(1) = 1$, and this gives $2N_3(2) = 6$. Finally, $3N_3(3) = 24$. Therefore, we would calculate that $N_3(6) = 116$. It would not be too hard to write such a recursive algorithm and I encourage the reader to try it.

However, there is an easier way to compute $N_q(n)$. It involves the Moebius function. It is a function $\mu$ on the positive integers that is define as follows:
$$\mu(n) = \left\{ \begin{matrix}1 & \text{if n=1}\\(-1)^k & \text{if n is the product of k distinct primes}\\ 0 & \text{if p^2\mid n for some prime p}\end{matrix}\right.$$
The key feature of the Moebius function is the following theorem.

Moebius Inversion Formula. Let $f$ and $g$ be functions on the natural numbers taking values in the integers. Then $f(n) = \sum_{d\mid n}g(d)$ if and only if
$$g(n) = \sum_{d\mid n} \mu(n/d)f(d).$$

The proof of this formula is not difficult. In fact, it uses just one fact: that $\sum_{d\mid n}\mu(d)$ is actually the characterstic function of 1. Once you prove this, just plug and chug and exchange the order of summation until something good happens. Now, the usefulness behind this theorem is that the $g(n)$ is something that you don't want to compute recursively in a formula like $\sum_{d\mid n} g(d)$ and $f$ is a much easier function to compute. In this case, if you set $f(n) = q^n$ and $g(n) = nN_q(n)$, then we get the formula:
$$N_q(n) = \frac{1}{n}\sum_{d\mid n}\mu(n/d)q^d.$$
This is way better for two reasons. First, the function $\mu(d)$ is much easier to compute. Going back to our example of $q = 3$ and $n =6$ we get:
$$N_3(6) = \frac{1}{6}\sum_{d\mid 6} \mu(6/d)3^d\\ =\frac{1}{6}[ 3\mu(6) + 9\mu(3) + 27\mu(2) + 729\mu(1)]\\ =\frac{1}{6}[3 – 9 – 27 + 729] = 116$$
Great, it's the same as before! Second, you might have also caught onto the following: because $\mu(n) = 0$ when $n$ is divisible by the square of a prime, many terms are zero for non-squarefree divisors. For example, if $p$ is a prime then:
$$N_q(p^k) = \frac{q^{p^{k-1}}(q^{p^k – p^{k-1}} -1)}{p^k}$$
Now that's a slightly odd formula. But rest assured, it's an integer. Of course it is for $q$ a power of $p$. But recall that Euler's generalisation of Fermat's theorem is that $m\mid a^{\phi(m)} – 1$ where $\phi(m)$ is Euler's phi-function; in particular $\phi(p^k) = p^k – p^{k-1}$. This theorem reassures us that our formula for $N_q(p^k)$ is always an integer! Derive it yourself if you don't believe me!

Here is a slightly larger example of computing the number of monic irreducible polynomials over a finite field: $N_7(1000)$ is:

125325663996571831810755483238273420616498507508098617146349500752097059
631738116432448839054351520763198615919551594076685828989467263022761790
838270854579830015111246661203984624358929832571615718014704096305668097
507613273663023226895250541385927158426088684494082416768617708189592286
936039922311125683719215046689156738352590137241554510185855964549927575
493247391132548534378497978806084951085874202011836362315727419755541133
539265598662010268853908446650053267647882140003847245396211558511666138
351408604025658319560903137861986931774056513054992087504513932489592904
750312027070174260604667797393373317631218936520756499523524624293929096
937248615255468427121487099712898741460729427585000351321745490397384481
841582252267895651271719909180553709603533883653411804420518449012909723
742333024025195501907575991506219735996520910112240