Seeking for a proof on the relation between Euler totient and Möbius function 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}
$$
 A: 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*}
A: Alternatively, you can note that $n = \phi \ast u$ where $u = 1$ for all n, and $\ast$ denotes the Dirichlet product, and use the Mobius inversion formula, so
$n = \phi \ast u\\
n \ast \mu = \phi \ast u \ast \mu = \phi \ast I = \phi$ 
where $I$ is the identity function, and so
$\phi = n \ast \mu = \sum_{d|n} d \, \mu \left( \frac{n}{d} \right)$
by definition of the Dirichlet convolution.
A: Let $n = p_1^{e_1}p_2^{e_2}\ldots p_m^{e_k}$ for some primes $\{p_1, \ldots, p_m\}$. By definition $\phi(n)$ equals the number of elements in the set $\{0,1,\ldots,n-1\}$ that have no common divisor with $n$. We will count the number of elements that will be excluded in this setup, i.e. the number of elements of the set $S$ that do have a common divisor with $n$. In order for this to be true such a number $a$ has to be a multiple of one of the primes $p_1,\ldots,p_m$. If we denote by $S_d$ the set of multiples of $d$ in $\{0,1,\ldots,n-1\}$ then we can write $S = \bigcup_{p \in \{p_1, \ldots, p_m\}}S_p$. We will use the inclusion - exclusion principle to calculate the number of elements of $S$. Note that $\#S_d = \frac{n}{d}$ (which we will denote by $d'$) for any divisor $d$ of $n$, and that for $p_i \neq p_j$ we have $S_{p_ip_j} = S_{p_i} \bigcap S_{p_j}$. The the inclusion -  exclusion principle goes like this: $\#S = \#S_{p_1} + \#S_{p_2} + \ldots \#S_{p_m} - \#S_{p_1p_2} - \ldots -\#S_{p_ip_j} \ldots + \#S_{p_ip_jp_k}\ldots$. Remark that the summation goes over the divisors of $n$ that are square free and $>1$. We can also write this as $\#S = \sum_{d | n, d >1} d'\mu(d).(-1)$ since $\mu$ kills the non square free divisors. Finally : $$\phi(n) = n - \#S = n - \sum_{d | n, d >1} d'\mu(d).(-1) = n + \sum_{d | n, d >1} d'\mu(d) =\\ \sum_{d | n} d'\mu(d) = \sum_{d | n} d\mu(d')$$ Since $d$ and $d'$ are interchangeable and $1' = n$, $\mu(1) = 1$.
Example: $n = 225 = 3^25^2$. Then $S_3 = \{0, 3, 6, \ldots, 222\}$, $S_5 = \{0, 5, 10, \ldots, 220\}$ and $S_{15} = S_3 \bigcap S_5 = \{0, 15, 30, \ldots, 210\}$. Now $\#S_3 = 3' = 3.5^2$, $\#S_5 = 5' = 3^2.5$ and $\#S_{15} = 15' = 3.5$. Then the inclusion - exclusion principle gives: $$\#S = \#S_3 + \#S_5 - \#S_{15} = -(\mu(3)3'+\mu(5)5'+\mu(15)15') = -(\mu(3)3'+\mu(5)5'+ \mu(9)9' + \mu(15)15' + \mu(25)25' + \mu(45)45' + \mu(75)75' + \mu(225)225') = -\sum_{d \in \{3, 5, 9, 15, 25, 45, 75, 225\}}\mu(d)d' $$ Now $$\phi(n) = n - \#S = n + \sum_{d \in \{3, 5, 9, 15, 25, 45, 75, 225\}}\mu(d)d' = \sum_{d \in \{1, 3, 5, 9, 15, 25, 45, 75, 225\}}\mu(d)d'$$
A: 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$.
A: $$ \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 
