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

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'$$
