# Prove that $\frac{n}{\phi(n)} = \sum\limits_{d \mid n} \frac{\mu^2(d)}{\phi(d)}$

I am trying to show that: $$\frac{n}{\phi(n)} = \sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)}$$ 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.

-
Related post: math.stackexchange.com/questions/388299/… – Martin Sleziak Oct 26 '15 at 16:13

Prove both sides (of the original equation) are multiplicative, then prove they're equal for prime powers.

-
$\mu(d)$ and $\phi(d)$ multiplicative. Hence $\sum_{d \mid n} \frac{\mu^2(d)}{\phi(d)}$ also multiplicative. Left and right side are multiplicative. For $p^k$: $$\dfrac{p^k}{p^k-p^{k-1}}=1+\dfrac 1{p-1}$$ – aska langley Aug 15 '12 at 6:56

$$\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)}$$

-
This is Exercise 3, Chapter 2, Apostol's - Introduction to Analytical Number Theory – nature1729 May 31 '14 at 19:13