Proof of $ \phi(n) = \sum_{n|d} \mu(d) \cdot\frac nd $ I'd like to prove $\phi(m)=\sum_{m|d}\mu(d)\cdot\frac md$.
If I'm right then we have for euler-phi


*

*$\phi(n) = \sum_{m \leq n,\gcd(m,n)=1} 1$


Which means: as long as $m$ is less or equal than $n$ and their greatest common divisor is $1$, $\phi$ does count $1$ and sums up all "$1$". Should be right so far.
Maybe we can continue like this


*

*set $1 = f(n)$ and we have

*$\sum_{m \leq n, \gcd(m,n)=1} f(m) = \ldots$ ?


After some steps I should get a true equality and then I could do the steps backwards to prove the statement.
Or maybe there's a much better way?
 A: For each prime $p\mid n$, let $F_p$ be the set of integers not greater than $n$ which are divisible by $p$. Then $|F_p|=\frac np$. Furthermore, if $d=p_1p_2p_3\dots p_k$ is a product of distinct primes, each dividing $n$, then
$$
|F_{p_1}\cap F_{p_2}\cap\dots\cap F_{p_k}|=\frac nd
$$
and $-\mu(d)=(-1)^{k-1}$.
Using the principle of inclusion-exclusion, we get that the number of integers no greater than $n$ that share a factor with $n$ is
$$
\begin{align}
n-\phi(n)
&=\sum_{\substack{k\ge1\\p_j\mid n}}(-1)^{k-1}|F_{p_1}\cap F_{p_2}\cap\dots\cap F_{p_k}|\\
&=-\sum_{\substack{d\mid n\\d\gt1}}\mu(d)\frac nd
\end{align}
$$
Thus, the number of integers no greater than $n$ which do not share a factor with $n$ is
$$
\begin{align}
\phi(n)
&=n+\sum_{\substack{d\mid n\\d\gt1}}\mu(d)\frac nd\\[6pt]
&=\mu(1)\frac n1+\sum_{\substack{d\mid n\\d\gt1}}\mu(d)\frac nd\\[6pt]
&=\sum_{d\mid n}\mu(d)\frac nd
\end{align}
$$

An Alternate Proof
Note that
$$
\frac{\phi(n)}{n}=\prod_{\substack{p\mid n\\p\text{ prime}}}\left(1-\frac1p\right)
$$
is a multiplicative function. Furthermore, for each prime $p$,
$$
\frac{\phi(p^n)}{p^n}=1-\frac1p=\sum_{d\mid p^n}\frac{\mu(d)}{d}
$$
Since $n\mapsto\frac1n$ is a multiplicative function, so is $\frac1n$ times the convolution of $\mu$ and the identity:
$$
\frac1n\sum\limits_{d\mid n}\mu(d)\frac{n}{d}=\sum\limits_{d\mid n}\frac{\mu(d)}{d}
$$
Therefore, as two multiplicative functions that agree on the powers of primes,
$$
\frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}
$$
and therefore
$$
\phi(n)=\sum_{d\mid n}\mu(d)\frac nd
$$
A: Perhaps it is worth noting the theorem that 

if $f, g$ are complex-valued, say, functions on the positive natural numbers, and
  $$
f(n) = \sum_{d \mid n} g(d),
$$
  then
  $$
g(n) = \sum_{d \mid n} \mu(d) f\left(\frac{n}{d}\right).\tag{Moebius-inversion}
$$

Now $n = \sum_{d\mid n} \phi(d)$ easily comes from counting orders of elements in a cyclic group of order $n$, from which the required formula follows.
To prove the theorem, introduce the
  convolution of two functions $f, g$ as $$f * g (n) = \sum_{d, e, d e
  = n} f(d) g(e).$$ One shows readily that convolution is commutative and associative. 
Define
  the constant function $1$, which evaluates to $1$ for all $n$, and 
  the Dirac delta as
  \begin{equation}
    \delta_{a}(n) =
    \begin{cases}
      1 & \text{if $n = a$,}\\
      0 & \text{if $n \ne a$.}
    \end{cases}
  \end{equation}
Recall also that
\begin{equation}\tag{mu}
    \sum_{d \mid n} \mu(d) =
    \begin{cases}
      1 & \text{if $n = 1$,}\\
      0 & \text{if $n > 1$.}
    \end{cases}
  \end{equation}
This is because if $n = p_{1}^{e_{1}} \cdots p_{k}^{e_{k}} \ne 1$, with $p_{i}$ distinct primes, and $e_{i} > 0$, then
$$
\sum_{d \mid n} \mu(d) = \sum_{i=0}^{k} (-1) ^{i}\dbinom{k}{i} = (1 -1) ^{k} = 0.
$$
Now the following steps are immediate


*

*$\delta_{1} =  1 * \mu$ (this is  (mu)),

*$\delta_{a} * \delta_{b} = \delta_{ab}$,

*$\delta_{1} * f = f$.


Finally, $$\mu * f = \mu *(g * 1) = g * (\mu * 1) = g * \delta_{1} = g,$$ which is (Moebius-inversion).
