Seeking for a proof on the relation between Euler totient and Möbius function

Question

Can someone help me prove the relation

$\varphi\left(n\right)={\displaystyle \sum_{d|n}}d\mu\left(n/d\right)$, where $\mu$ is the Möbius function defined by $$ \mu\left(n\right)=\begin{cases} 1 & \mbox{if }n=1\\ \left(-1\right)^{t} & \mbox{if }n\mbox{ is a product of }t\mbox{ distinct primes}\\ 0 & \mbox{if }p^{2}\mbox{ divides }n\mbox{ for some prime }p. \end{cases} $$

Answer 1

This follows from the identity $\sum_{d\mid n}\mu (d)=\lfloor \frac{1}{n}\rfloor$. Indeed, denoting the greatest common divisor of $n$ and $k$ by $(n,k)$, we have \begin{align*} \phi(n) & = \sum_{k=1}^n \left\lfloor \frac{1}{(n,k)} \right\rfloor = \sum_{k=1}^n \sum_{d\mid (n,k)} \mu(d) = \sum_{k=1}^n \sum_{\substack{d\mid n\\ d\mid k}}\mu(d) \\ & = \sum_{d\mid n}\sum_{q=1}^{n/d}\mu(d)=\sum_{d\mid n}\mu(d)\Biggl( \sum_{q=1}^{n/d}1\Biggr) = \sum_{d\mid n}\mu(d)\frac{n}{d}=\sum_{d\mid n}d\mu \left(\frac{n}{d}\right). \end{align*}

Answer 2

$$ \forall n \geq 1 , g(n) = \sum_{d \mid n} f(d) \Rightarrow f(n) = \sum_{d \mid n} \mu(d) g \left(\frac{n}{d} \right) $$

$$ n = \sum_{d \mid n}\varphi(d) \Rightarrow \varphi(n) = \sum_{d \mid n} \frac{n\mu(d)}{d} = \sum_{d \mid n} d\mu \left( \frac{n}{d} \right) $$

proof of Möbius inversion formula is here http://www.proofwiki.org/wiki/M%C3%B6bius_Inversion_Formula

Answer 3

Hint: $$\varphi(p_1^{m_1}p_2^{m_2}\ldots p_k^{m_k}) = p_1^{m_1}p_2^{m_2}\ldots p_k^{m_k} \prod_{i=1}^k \left( 1 - \frac{1}{p_k}\right)$$ and $d \mid n$ iff $d=p_1^{r_1}p_2^{r_2}\ldots p_k^{r_k}$ for $0 \le r_i \le m_i$.