# Monic Irreducible Polynomials over Finite Field

Let $F=\mathbb{F}_{q}$ be a finite field (so $q=p^k$ for some prime $p$ and positive integer $k$), and let $\varphi(d)$ denote the number of monic irreducible polynomials of degree $d$ in $F[X]$. I'm supposed to show that $\displaystyle{\sum_{d \mid n} d \varphi(d) = q^n}$.

I see there are previous questions about this topic and even a paper, but all (save one) seem to employ the use of the Möbius function and Möbius inversion - both topics I have not covered yet in class. There is also this answer, but it appears to hinge upon the extension having prime degree. Is there some way to show this without explicitly coming up with a formula for the number of irreducible monic polynomials of a given degree in $F[X]$?

Any help would be greatly appreciated.

• Consider elements $\alpha\in F$ and their minimal polynomials $m_\alpha(x)$ over the prime field. What degrees are possible for $m_\alpha$? Why do they all appear as $m_\alpha$ for some $\alpha$? How many elements of $F$ share the same minimal polynomial? Derive an equation! Mar 19, 2013 at 4:54
• Do you know that $\mathbb F(q^r)\subset\mathbb F(q^s)$ if and only if $r|s$? Mar 19, 2013 at 4:54
• As an aside, Mobius inversion is employed after that formula is already attained (to find $\varphi$ explicitly) - it is not used to obtain it.
– anon
Mar 19, 2013 at 4:56
• @Lubin, Do you mean $\mathbb{F}_{q^r} \subset \mathbb{F}_{q^s}$ iff $r \mid s$? If so, then yes, I do know that. Mar 19, 2013 at 4:57
• Joe, $m_\alpha$ is not the minimal polynomial over $F$, but over the prime field of $p$ elements. Nevertheless, they do not share roots, but have as many roots as is indicated by their degree. Mar 19, 2013 at 5:04

The splitting field of $X^{q^n}-X$ is ${\bf F}_{q^n}$. Every irreducible $\pi(X)$ of degree $d$ splits in ${\bf F}_{q^n}$ and every element of ${\bf F}_{q^n}$ is a root of $X^{q^n}-X$, and thus $\pi(X)\mid(X^{q^n}-X)$. Furthermore $X^{q^n}-X$ has no repeated roots so each irreducible $\pi(X)$ of degree $d\mid n$ must appear in its factorization precisely once. Therefore we have the conclusion
$$X^{q^n}-X=\prod_{d\mid n}\prod_{\deg\pi=d}\pi(X).$$
Taking degrees yields $\displaystyle q^n=\sum_{d\mid n}d\varphi(d)$ (and from here Möbius inversion yields $\varphi(d)$).