How does the Möbius function work?

In my notes: $$\sum_{d|n} \mu(d)\sigma(d) = (-1)^{k} \prod_{i=1}^{k} p_i$$

where $\mu(d)$ is the Möbius function and $\sigma(d)$ is the sum of all positive divisors of $d$.

And I have no idea how they got the expression on the right hand side. Could anyone help me explain how this works?

Thanks,

-
Hints: 1. When are the only possible $d$ with nonzero $\mu(d)$? 2. For such $d$, how does $\sigma(d)$ look like? In particular, is it multiplicative? 3. Look at the sum on the left again after answering 1 and 2. Can you factorize it? –  Soarer Mar 1 '11 at 5:25
The book? And I assume $k$ is the number of distinct prime divisors of $n$? –  Arturo Magidin Mar 1 '11 at 5:25
Arturo Magidin: I really don't know what is k. I rather change to my notes since I don't have any book for this class. –  Chan Mar 1 '11 at 5:35
@Soarer: Thank you. –  Chan Mar 1 '11 at 5:36
@Arturo, $k$ is the number of distinct prime divisors of $n$. –  Soarer Mar 1 '11 at 5:37

Caveat: This may not be the most direct way of doing it.

Write $n=p_1^{a_1}\cdots p_k^{a_k}$ with $p_i$ pairwise distinct primes. Since the Moebius function is zero at any non-square-free integer, the only divisors that matter are those which are products of some pairwise distinct $p_i$.

Since $$\sigma(p_{i_1}\cdots p_{i_r}) = \prod_{j=1}^r \sigma(p_{i_j}) = \prod_{j=1}^{r}(1+p_{i_j}),$$ then the sum on the left hand side is the sum of these products, with a minus sign if the number of factors is odd, and a plus sign if the number of factors is even.

Let $x_i = 1 + p_i$. Let $S_r(x_1,\ldots,x_k)$ is the $r$th elementary symmetric polynomial on $x_1,\ldots,x_r$; that is, \begin{align*} S_0(x_1,\ldots,x_k) &= 1,\\ S_1(x_1,\ldots,x_k) &= x_1+\cdots + x_k,\\ S_2(x_1,\ldots,x_k) &= x_1x_2 + \cdots + x_1x_k + x_2x_3+\cdots + x_{k-1}x_k,\\ &\vdots\\ S_k(x_1,\ldots,x_k) &= x_1\cdots x_k. \end{align*}

Therefore: $$\sum_{d|n}\mu(d)\sigma(d) = \sum_{r=0}^k (-1)^rS_r(x_1,\ldots,x_k).$$

Now consider the polynomial $(t-x_1)\cdots(t-x_k)$. The coefficient of $t^i$ is precisely $(-1)^{k-i}S_{k-i}(x_1,\ldots,x_k)$. Thus, the sum on the right hand side is this polynomial evaluated at $t=1$. Therefore, $$\sum_{d|n}\mu(d)\sigma(d) = \sum_{r=0}^k(-1)^rS_r(x_1,\ldots,x_k) = (1-x_1)\cdots(1-x_k) = \prod_{i=1}^k(1-x_i).$$ But $1-x_i = 1-(1+p_i) = -p_i$. Therefore, $$\sum_{d|n}\mu(d)\sigma(d) = \prod_{i=1}^k(-p_i) = (-1)^k\prod_{i=1}^kp_i,$$ as claimed.

-
@Arturo Magidin: Many thanks for your very clear explanation. You made me feel less dumb now :P! By the way, I realized you think super fast, probably 10 times faster than mine. I can't believe in about 2 minutes, you could write that much. Amazing! –  Chan Mar 1 '11 at 5:55
@Chan: What do you mean, "about 2 minutes"? Where do you get that from? Certainly, took me longer than that to write it out! And my answer was posted well over half an hour after you posted the question (though I did not see it immediately after you did). –  Arturo Magidin Mar 1 '11 at 5:57
@Chan: Also: keep in mind, this may not be the best way of doing it; it just happens to be the way that it occurred to me to do it just now. –  Arturo Magidin Mar 1 '11 at 5:58
@Arturo Magidin: really? I thought it was much faster than that. Although 2 minutes would be an exaggeration, I don't think it took half an hour though. –  Chan Mar 1 '11 at 6:00
@Arturo Magidin: Ok, fair enough. Probably because I stayed in front of my computer for too long, and did not realized time passed. –  Chan Mar 1 '11 at 6:03

This looks more like a special case of Möbius Inversion Formula. You need to choose an appropriate $f$ and $g$.

Note that $n = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_k^{\alpha_k}$ and $n = p_1 p_2 \ldots p_k$ should give the same answer. (Essentially you are removing the $\mu(d) = 0$ terms on the left side).

Hence, we could just deal with $n = p_1 p_2 \ldots p_k$.

Now let $f(n) = n$ and $g(n) = \displaystyle \sum_{d|n} f(d)$.

$g(n)$ is nothing but the sum of divisors of $n$ i.e. $g(n) = \sigma(n)$.

Note that $\mu(d) = (-1)^k \mu \left( \frac{n}{d} \right)$ when $n = p_1 p_2 \ldots p_k$.

By Möbius Inversion Formula, $$n = \sum_{d|n} \mu(d) g\left( \frac{n}{d} \right) = (-1)^k \sum_{d|n} \mu\left( \frac{n}{d} \right) g \left( \frac{n}{d} \right) = (-1)^k \sum_{d|n} \mu\left( d \right) g \left( d \right)$$

Hence, $$\sum_{d|n} \mu\left( d \right) \sigma \left( d \right) = (-1)^k p_1 p_2 \ldots p_k$$

-
I was pretty sure Moebius inversion could be used, but the circuitous method I came up with ocurred to me before I could figure out what $g$ to use... Thanks! –  Arturo Magidin Mar 1 '11 at 16:35
Ambikasaran: Thank you. Your solution is a bit easier for a novice like me to understand. –  Chan Mar 3 '11 at 15:42

Hint: the Möbius function is only non-zero on squarefree numbers (see here), and it is either $+1$ or $-1$ depending on the number of factors. Then consider: What do the squarefree divisors of $n=p_1^{a_1}\cdots p_r^{a_r}$ look like? What does $\sigma$ (the sum of divisors) of a squarefree number look like?

-