4
$\begingroup$

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\limits_{d|n} \mu(n/d)\nu(d)=1$ for all $n.$

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

  • 0
    @anon: I was about to write an answer until I saw the tag. That's why I restricted myself to comments instead. :)2012-04-28

2 Answers 2

5

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.

  • 0
    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}$...).2012-04-28
3

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}$.