# Sum of Positive Divisors

If $\nu(n)=$ Number of positive divisors of $n,$ $\mu$ is the mobius function and $\sigma(n)$ is the sum of positive divisors.

show that;

1. $\sum_{d|n} \mu(n/d)\nu(d)=1$ for all $n.$

2. $\sum_{d|n} \mu(n/d)\sigma(d)=n$ for all $n.$

-
These are both Dirichlet convolutions. See this for instance. – J. M. Apr 28 '12 at 8:44
The first case corresponds to getting the coefficients of $\zeta(s)$, and the second case corresponds to the coefficients of $\zeta(s-1)$. – J. M. Apr 28 '12 at 8:48
@J.M. Given the (elementary-number-theory) tag, I think an approach through analytic number theory might be overkill. – anon Apr 28 '12 at 8:50
@anon: I was about to write an answer until I saw the tag. That's why I restricted myself to comments instead. :) – J. M. Apr 28 '12 at 8:51

By definition $\nu(n)=\sum_{d|n} 1$ and $\sigma(n)=\sum_{d|n} d$ for every integer $n>0$ so that $\{\nu,1\}$ and $\{\sigma,\operatorname{id}\}$ (with $1:n\mapsto 1$ and $\operatorname{id}:n\mapsto n$) will be both Möbius pairs according to the Möbius inversion formula.

-
It may be worth noting that the Möbius pairs are pairs of functions. I would have written them $\{\nu,\mathbf1\}$ and $\{\sigma,\mathrm{id}\}$ where $\mathbf1$ is the constant function $n\mapsto1$, and $\mathrm{id}$ the identity function $n\mapsto n$. – Marc van Leeuwen Apr 28 '12 at 9:28
Thanks for the comment @Marc. You are right some notations are better : I think that Apostol, for example, would have used $\operatorname{N}$ for the second one. Here I used Andrews' notation (except that $\nu$ should be $\operatorname{d}$...). – Raymond Manzoni Apr 28 '12 at 9:32

Here is a sort of brutish route through multiplicative induction. Recall that an arithmetic function is multiplicative if $f(nm)=f(n)f(m)$ whenever $n$ and $m$ are coprime (it does not need to hold when they share factors; if such is the case we call it completely multiplicative). I'll explain the method in a appreciably higher level of generality; if you follow it you should be able to specialize.

(Ultimately this proves that the Dirichlet convolution sends multiplicative functions to other multiplicative functions.)

Suppose $f$ and $g$ are multiplicative functions. Consider the new, summatory function

$$h(n):=\sum_{d|n} f(d)g(n/d).\tag{\circ}$$

Denote by $D_n$ the set of positive divisors of $n$. Let $n,m$ be coprime natural numbers. If $d|nm$, we can look at the prime factorization of $d$ and split into two parts: that which appears in the factorization of $n$, and that which appears in the factorization of $m$. In other words,

$$D_{nm}=\{ab:a\in D_n,b\in D_m\}.$$

We can use this to decompose the original sum:

$$\begin{array}{c l} h(nm) & =\sum_{d|nm}f(nm/d)g(d) \\ & =\sum_{a|n}\sum_{b|m} f\left(\frac{nm}{ab}\right)g(ab) \\ & = \sum_{a|n}\sum_{b|m}f\left(\frac{n}{a}\right)f\left(\frac{m}{b}\right)g(a)g(b) \\ & = \left(\sum_{a|n}f(n/a)g(a)\right)\left(\sum_{b|m}f(m/b)g(b)\right) \\ & = h(n)h(m). \end{array}$$

This demonstrates any function expressible in the form $(\circ)$ (in which $f,g$ are multiplicative, recall) is itself multiplicative. The functions $\nu$ and $\sigma$ (which are the divisor functions $\sigma_0$ and $\sigma_1$ resp.) are therefore multiplicative. It therefore suffices to prove $(1)$ and $(2)$ hold for prime powers $n=p^r$, which is trivial since $\mu(p^r/d)$ is zero except when $d=p^r$ and $d=p^{r-1}$.

-