7
$\begingroup$

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.

  • 0
    Related post: http://math.stackexchange.com/questions/388299/sum-d-mid-n-$f$rac-mu2dd-prod-pn-left1-frac1p-right2015-10-26

2 Answers 2

5

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

  • 4
    $\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}$2012-08-15
4

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

  • 0
    This is Exercise 3, Chapter 2, Apostol's - Introduction to Analytical Number Theory2014-05-31