# Number theory Exercise: $\sum_{d \mid n} \mu(d) d(d) = (-1)^{\omega(n)}$ and $\sum_{d \mid n} \mu(d) \sigma (d)$

for positive integer $n$, how can we show

$$\sum_{d | n} \mu(d) d(d) = (-1)^{\omega(n)}$$

where $d(n)$ is number of positive divisors of $n$ and $mu(n)$ is $(-1)^{\omega(n)}$ if $n$ is square free, and $0$ otherwise. Also, what is

$$\sum_{d | n} \mu(d) \sigma (d)$$ where $\sigma(n)$ is the sum of positive divisors of $n$

• Bad form to use the symbol $d$ with two different meanings in one formula. – Gerry Myerson Apr 4 '13 at 12:27
• $d(n)$ is usually written $\tau(n)$. – lhf Apr 4 '13 at 12:38

## 2 Answers

$$\sum_{d\mid n}\mu(d)f(d)$$ $$=\mu(1)d(1)+\sum_{p_i|n}\mu(p_i)f(p_i)+\sum_{p_ip_j|n}\mu(p_ip_j)f(p_ip_j)+\sum_{p_ip_jp_k|n}\mu(p_ip_jp_k)f(p_ip_jp_k)+\cdots+\sum_{p_ip_j\cdots|n}\mu(p_i^{r_1}p_j^{r_j}p_k^{r_k}\cdots)f(p_i^{r_1}p_j^{r_j}p_k^{r_k}\cdots)$$ where $p_i,p_j,p_k$ are distinct primes and at least one of the integers $r_i,r_j,r_k>1$

As $\mu$ is multiplicative, $\mu(p_i^{r_1}p_j^{r_j}p_k^{r_k}\cdots)=\mu(p_i^{r_1})\mu(p_j^{r_j})\mu(p_k^{r_k})\cdots=0$ as at least one of the integers $r_i,r_j,r_k>1$

$$\sum_{d\mid n}\mu(d)f(d)=\mu(1)f(1)+\sum_{p_i|n}\mu(p_i)f(p_i)+\sum_{p_ip_j|n}\mu(p_ip_j)f(p_ip_j)+\sum_{p_ip_jp_k|n}\mu(p_ip_jp_k)f(p_ip_jp_k)+\cdots$$

If $f(n)$ is also multiplicative with $f(1)=1$,

$$\sum_{d\mid n}\mu(d)f(d)$$ $$=\mu(1)f(1)+\sum_{p_i|n}\mu(p_i)f(p_i)+\sum_{p_ip_j|n}\mu(p_i)\mu(p_j)f(p_i)f(p_j)+\sum_{p_ip_jp_k|n}\mu(p_i)\mu(p_j)\mu(p_k)f(p_i)f(p_j)(f)p_k)+\cdots$$

$$=1+\sum_{p_i|n}\mu(p_i)f(p_i)+\sum_{p_ip_j|n}\mu(p_i)\mu(p_j)f(p_i)f(p_j)+\sum_{p_ip_jp_k|n}\mu(p_i)\mu(p_j)\mu(p_k)f(p_i)f(p_j)(f)p_k)+\cdots$$

$$=\prod(1+\mu(p_i)f(p_i))=\prod_{p_i\mid n}(1-f(p_i))$$

As $d$ or $\tau$ is multiplicative with $\tau(1)=1,\tau(p)=1+1=2$ where $p$ is prime

$$\sum_{d\mid n}\mu(d)\tau(d)=\prod_{p_i\mid n}(1-2)=(-1)^{\omega(n)}$$ where $\omega(n)$ is the number of prime factors of $n$

As $\sigma$ is multiplicative with $\sigma(1)=1$ and $\sigma(p)=p+1$ where $p$ is prime

$$\sum_{d\mid n}\mu(d)\sigma(d)=\prod_{p_i\mid n}\{1-(p_i+1)\} = \prod_{p_i\mid n}(-p_i)= (-1)^{\omega(n)}\prod_{p_i\mid n} p_i$$ where $\omega(n)$ is the number of prime factors of $n$

• It would appear that you have left out terms involving $d=p_1p_2$ and $d=p_1p_2p_3$ and the like from your equations. – Gerry Myerson Apr 4 '13 at 12:29
• @GerryMyerson, rectified the horrible mistake. – lab bhattacharjee Apr 4 '13 at 15:17

The sums you ask about will be multiplicative functions, so you need only evaluate them in the case where $n$ is a prime power, then multiply over the primes dividing $n$. Perhaps this is what @lab was getting at in the other answer.