Counting total number of monic irreducible polynomials of all degrees $k$ that divide $m$. 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.
 A: 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})$$
