Prove that $\sum_{d|n} \mu(d)\sigma(d) = (-1)^{k} \prod_{i=1}^{k} p_i$ 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,
 A: 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.
A: 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$$
A: 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?
