I am trying to show that:
\begin{equation}
\frac{n}{\phi(n)} = \sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)}
\end{equation}
where $\phi(n)$ is Euler's totient function and $\mu$ is the Möbius function.
The identity clearly holds for $n=1$, so if we write $n=p_1^{a_1} \cdots p_k^{a_k}$ for the prime decomposition of $n$, the left-hand side becomes:
\begin{eqnarray*}
\frac{n}{\phi(n)} & = & \frac{p_1^{a_1} \cdots p_k^{a_k}}{\phi(p_1^{a_1}) \cdots \phi(p_k^{a_k})} \\
& = & \frac{p_1^{a_1} \cdots p_k^{a_k}}{(p_1^{a_1-1})(p_1-1) \cdots (p_k^{a_k})(p_k-1)} \\
& = & \frac{p_1 \cdots p_k}{(p_1-1)\cdots (p_k-1)}
\end{eqnarray*}
Whereas the right-hand side becomes:
\begin{eqnarray*}
\sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)} & = & \sum_{\substack{d \mid n \\ p^2 \nmid d}} \frac{1}{\phi(d)} \\
& = & 1 + \frac{1}{\phi(p_1)} + \dots + \frac{1}{\phi(p_k)} + \frac{1}{\phi(p_1 p_2)} + \dots + \frac{1}{\phi(p_{k-1}p_k)} \\
& + & \dots + \frac{1}{\phi(p_1 \cdots p_k)} \\
& = & 1 + \frac{1}{p_1 – 1} + \dots + \frac{1}{p_k – 1} + \frac{1}{(p_1 – 1)(p_2 – 1)} + \dots + \frac{1}{(p_{k-1}-1)(p_k-1)} \\
& + & \dots + \frac{1}{(p_1 – 1) \cdots (p_k – 1)}
\end{eqnarray*}
I am unsure of how to proceed from this point however. Any help would be much appreciated.
Best Answer
$$\sum_{d|n}\frac{\mu^2(d)}{\phi(d)}=1+\frac{1}{p_1-1}+\frac{1}{p_2-1}+\cdots+\frac{1}{(p_1-1)(p_2-1)+\cdots}$$
$$=(1+\frac{1}{p_1-1})(1+\frac{1}{p_2-1})\cdots=\prod_{p_i|n}(1+\frac{1}{p_i-1})=\prod_{p_i|n}(\frac{1}{1-1/p_i}) $$
$$ =\frac{n}{\phi(n)} $$