# 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! –  Jyrki Lahtonen Mar 19 '13 at 4:54
Do you know that $\mathbb F(q^r)\subset\mathbb F(q^s)$ if and only if $r|s$? –  Lubin Mar 19 '13 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 '13 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. –  JoeDub Mar 19 '13 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. –  Jyrki Lahtonen Mar 19 '13 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)$).

-
Somehow it wasn't clicking that I was examining polynomial degrees. When you put it that way, it's quite clear to me now what is happening. –  JoeDub Mar 19 '13 at 5:14