8
$\begingroup$

$$\varphi(n)=\sum_{d\mid n}d\cdot \mu\left(\frac{n}{d}\right)=n\sum_{d\mid n}\frac{\mu(d)}{d}$$

This describes the totient function in terms of the Möbius function. I understand what the Möbius function does but I don't understand this derivation at all. Is there an easy way to understand why this is so?

I'm not looking for some lengthy mathematical proof, but rather an intuitive understanding. I've seen plenty of papers showing the proof, but I just don't get what's happening.

$\endgroup$
4
  • 1
    $\begingroup$ You may want to look at the Principle of Inclusion-Exclusion. $\endgroup$ Dec 28, 2012 at 17:33
  • $\begingroup$ @user51819: While I'm glad my answer was helpful, you don't have to accept my answer so quickly - there may be other perspectives on this identity (or simply better explanations of the one I described) that will be useful to you! $\endgroup$ Dec 28, 2012 at 17:33
  • $\begingroup$ @ZevChonoles Sorry, I figured it was a sufficient explanation. Would you perhaps be willing to contribute an example of what you mean to make things even clearer? Say phi(24)? $\endgroup$
    – user51819
    Dec 28, 2012 at 17:49
  • $\begingroup$ "Möbius", or equivalently "Moebius", is the correct spelling. "Mobius" is different. $\endgroup$ Dec 28, 2012 at 17:59

1 Answer 1

4
$\begingroup$

$\varphi(n)$ counts the number of integers $k$ between $1$ and $n$ that are relatively prime to $n$.

The term $d=n$ gives us our starting value of $n\cdot\mu(\frac{n}{n})=n\cdot 1=n$, i.e. all of the integers $1\leq k\leq n$.

For each prime $p$ dividing $n$, the term $d=\frac{n}{p}$ throws out the multiples of $p$ from among the numbers between $1$ and $n$; specifically, there are $\frac{n}{p}$ multiples of $p$ between $1$ and $n$, and the $d=\frac{n}{p}$ term in the sum contributes $\frac{n}{p}\cdot\mu(p)=-\frac{n}{p}$.

Unfortunately, the result is still not quite right - for any distinct prime divisors $p_1$ and $p_2$ of $n$, we counted as if we had to remove multiples of $p_1p_2$ twice, when of course we only remove them once. The terms $d=\frac{n}{p_1p_2}$ correct for this, because they contribute $\frac{n}{p_1p_2}\cdot \mu(p_1p_2)=\frac{n}{p_1p_2}$, the number of multiples of $p_1p_2$ between $1$ and $n$.

But then we must account for the numbers between $1$ and $n$ that we originally triple-counted, and which our correction above over corrects for, etc. - the alternating nature of the Möbius function is what makes it do this the way we need.

$\endgroup$
1
  • $\begingroup$ I answered a similar question recently, and while searching for other answers, came across this answer, which also uses inclusion-exclusion. (+1) $\endgroup$
    – robjohn
    May 19, 2014 at 12:27

You must log in to answer this question.

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