§27.6 Divisor Sums

Notes:: See Apostol (1976, Chapter 2).
Keywords:: number-theoretic functions
Permalink:: http://dlmf.nist.gov/27.6

Sums of number-theoretic functions extended over divisors are of special interest. For example,

27.6.1 $\sum _{{d\divides n}}\mathop{\lambda\/}\nolimits\!\left(d\right)=\begin{cases}1,&n\mbox{ is a square},\\ 0,&\mbox{otherwise}.\end{cases}$

Symbols:: $\mathop{\lambda\/}\nolimits\!\left(n\right)$ : Liouville’s function, $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E1
Encodings:: TeX, pMML, png

If $f$ is multiplicative, then

27.6.2 $\sum _{{d\divides n}}\mathop{\mu\/}\nolimits\!\left(d\right)f(d)=\prod _{{p\divides n}}(1-f(p)),$ $n>1$ .

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer, $n$ : positive integer and $p,p_{1},\ldots$ : prime numbers
Permalink:: http://dlmf.nist.gov/27.6.E2
Encodings:: TeX, pMML, png

Generating functions, Euler products, and Möbius inversion are used to evaluate many sums extended over divisors. Examples include:

27.6.3 $\sum _{{d\divides n}}|\mathop{\mu\/}\nolimits\!\left(d\right)|=2^{{\mathop{\nu\/}\nolimits\!\left(n\right)}},$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $\mathop{\nu\/}\nolimits\!\left(n\right)$ : number of distinct primes dividing $n$ , $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E3
Encodings:: TeX, pMML, png

27.6.4 $\sum _{{d^{2}\divides n}}\mathop{\mu\/}\nolimits\!\left(d\right)=|\mathop{\mu\/}\nolimits\!\left(n\right)|,$

Symbols:: $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E4
Encodings:: TeX, pMML, png

27.6.5 $\sum _{{d\divides n}}\frac{|\mathop{\mu\/}\nolimits\!\left(d\right)|}{\mathop{\phi\/}\nolimits\!\left(d\right)}=\frac{n}{\mathop{\phi\/}\nolimits\!\left(n\right)},$

Symbols:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$ , $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E5
Encodings:: TeX, pMML, png

27.6.6 $\sum _{{d\divides n}}\mathop{\phi _{{k}}\/}\nolimits\!\left(d\right)\left(\frac{n}{d}\right)^{k}=1^{k}+2^{k}+\dots+n^{k},$

Symbols:: $\mathop{\phi _{{k}}\/}\nolimits\!\left(n\right)$ : sum of powers of integers relatively prime to $n$ , $d$ : positive integer, $k$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E6
Encodings:: TeX, pMML, png

27.6.7 $\sum _{{d\divides n}}\mathop{\mu\/}\nolimits\!\left(d\right)\left(\frac{n}{d}\right)^{k}=\mathop{J_{{k}}\/}\nolimits\!\left(n\right),$

Symbols:: $\mathop{J_{{k}}\/}\nolimits\!\left(n\right)$ : Jordan’s function, $\mathop{\mu\/}\nolimits\!\left(n\right)$ : Möbius function, $d$ : positive integer, $k$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E7
Encodings:: TeX, pMML, png

27.6.8 $\sum _{{d\divides n}}\mathop{J_{{k}}\/}\nolimits\!\left(d\right)=n^{k}.$

Symbols:: $\mathop{J_{{k}}\/}\nolimits\!\left(n\right)$ : Jordan’s function, $d$ : positive integer, $k$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.6.E8
Encodings:: TeX, pMML, png