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

  • 1
    $\begingroup$ You may want to look at the Principle of Inclusion-Exclusion. $\endgroup$ – André Nicolas Dec 28 '12 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$ – Zev Chonoles Dec 28 '12 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 '12 at 17:49
  • $\begingroup$ "Möbius", or equivalently "Moebius", is the correct spelling. "Mobius" is different. $\endgroup$ – Michael Hardy Dec 28 '12 at 17:59

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

| cite | improve this answer | |
  • $\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 '14 at 12:27

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.