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.

  • 0
    "Möbius", or equivalently "Moebius", is the correct spelling. "Mobius" is different.2012-12-28

1 Answers 1

4

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

  • 0
    I [answered](http://math.stackexchange.com/a/800180) a similar [question](http://math.stackexchange.com/q/800118) recently, and while searching for other answers, came across this answer, which also uses inclusion-exclusion. (+1)2014-05-19