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?

• I just did a search for other proofs of this formula and found this answer, which also uses inclusion-exclusion. – robjohn May 19 '14 at 12:31

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

• would the downvoter care to comment? – robjohn May 18 '14 at 19:18

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 $$\delta_{a}(n) = \begin{cases} 1 & \text{if n = a,}\\ 0 & \text{if n \ne a.} \end{cases}$$

Recall also that $$\tag{mu} \sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{if n = 1,}\\ 0 & \text{if n > 1.} \end{cases}$$ 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

1. $\delta_{1} = 1 * \mu$ (this is (mu)),
2. $\delta_{a} * \delta_{b} = \delta_{ab}$,
3. $\delta_{1} * f = f$.

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