Why is the following relation counting monic irreducible polynomials of all degrees $d$ that divide $m$ true?
\begin{equation} \sum_{d\ |\ m}\left(\frac{1}{d} \sum_{c\ |\ d} \mu(d/c)\ p^{c}\right) = \frac{1}{m} \sum_{d\ |\ m} \phi\!\left(\frac{m}{d}\right)\ p^{d}, \end{equation}
where $\mu(n)$ is the Möbius function and $\phi(n)$ is Euler's totient function.
Background: one can express the degree of the polynomial $x^{p^m}-x$ over $\mathbb{F}_{p}$ ($p$ = prime) as the sum of the degrees of the monic irreducible factors of $x^{p^m}-x$ as $$ \begin{equation} p^m = \sum_{d\ |\ m} d\ I_d, \end{equation} $$ where the sum runs over all divisors $d$ of $m$, and $I_d$ is the number of minimal polynomials of degree $d$ which are factors of $x^{p^m}-x$.
By Möbius inversion on gets the number of monic irreducible polynomials of degree $m$ as, \begin{equation} I_m =\frac{1}{m} \sum_{d\ |\ m} \mu(d)\ p^{m/d}= \frac{1}{m} \sum_{d\ |\ m} \mu\!\left(\frac{m}{d}\right)\ p^{d}. \end{equation}
Now, if I sums up the monic irreducible polynomials of all degrees $d$ that divide $m$ one has, \begin{equation} \sum_{d\ |\ m} I_d =\sum_{d\ |\ m}\left(\frac{1}{d} \sum_{c\ |\ d} \mu(d/c)\ p^{c}\right) = \frac{1}{m} \sum_{d\ |\ m} \phi\!\left(\frac{m}{d}\right)\ p^{d}, \end{equation} where $\phi(n)$ is Euler's totient function counting the number of integers less than $n$ that are relatively prime to $n$ given by, \begin{equation} \phi(n) = |{\{0 \leq i < n\ | \gcd(i, n) = 1\}}|. \end{equation}
I verified the above relation in Matlab. I initially thought that $\sum_{d\ |\ n} \phi(d) = n$ would be of help, but could not come up with a decent proof. Any suggestions are greatly appreciated. Thanks.
Let's start from :
$$\sum_{d\ |\ m} I_d =\sum_{d\ |\ m}\left(\frac{1}{d} \sum_{c\ |\ d} \mu(d/c)\ p^{c}\right)=\sum_{d\ |\ m} \sum_{c\ |\ d} \left(\frac{1}{d}\mu(d/c)\ p^{c}\right) $$
Then invert the double sum (change of variable $(d,c)\mapsto(c,\frac{d}{c})=(c,e)$), you get
$$\sum_{d\ |\ m} \sum_{c\ |\ d} \left(\frac{1}{d}\mu(d/c)\ p^{c}\right)=\sum_{c\ |\ m} \sum_{e\ |\ \frac{m}{c}} \left(\frac{1}{ce}\mu(e)\ p^{c}\right) $$
$$\sum_{d\ |\ m} I_d =\sum_{c\ |\ m}\frac{p^c}{c} \sum_{e\ |\ \frac{m}{c}} \left(\frac{\mu(e)}{e}\right) $$
Now this is a well known result that :
$$\phi(n)=\sum_{d\ |\ n}\mu(d)\frac{n}{d} $$
It is just the Moebius formula applied to the identity (you gave us) :
$$\sum_{d\ |\ n}\phi(d)=n$$
So we see in particular that :
$$\sum_{e\ |\ \frac{m}{c}} \left(\frac{\mu(e)}{e}\right)=\frac{c}{m}\sum_{e\ |\ \frac{m}{c}} \left(\mu(e)\frac{m}{ce}\right)=\frac{c}{m}\phi(\frac{m}{c})$$
Finally :
$$\sum_{d\ |\ m} I_d =\sum_{c\ |\ m}\frac{p^c}{c}\frac{c}{m}\phi(\frac{m}{c})=\frac{1}{m}\sum_{c\ |\ m}p^c\phi(\frac{m}{c})$$