Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
3  
$\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)} $$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.