9
$\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.

$\endgroup$
1

2 Answers 2

7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is Exercise 3, Chapter 2, Apostol's - Introduction to Analytical Number Theory $\endgroup$
    – nature1729
    May 31, 2014 at 19:13
6
$\begingroup$

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

$\endgroup$
1
  • 4
    $\begingroup$ $\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}$$ $\endgroup$
    – user37274
    Aug 15, 2012 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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