Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $\nu(n)=$ Number of positive divisors of $n,$ $\mu$ is the Möbius 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.$

share|cite|improve this question
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.

share|cite|improve this answer
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}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.