Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
You may want to look at the Principle of Inclusion-Exclusion. –  André Nicolas Dec 28 '12 at 17:33
    
@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! –  Zev Chonoles Dec 28 '12 at 17:33
    
@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)? –  user51819 Dec 28 '12 at 17:49
    
"Möbius", or equivalently "Moebius", is the correct spelling. "Mobius" is different. –  Michael Hardy Dec 28 '12 at 17:59
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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