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?

  • $\begingroup$ I just did a search for other proofs of this formula and found this answer, which also uses inclusion-exclusion. $\endgroup$ – 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 $$

  • $\begingroup$ would the downvoter care to comment? $\endgroup$ – 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 \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

  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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.