4
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2014 at 12:31

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ would the downvoter care to comment? $\endgroup$
    – robjohn
    May 18, 2014 at 19:18
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .