§27.6 Divisor Sums

ⓘ

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

27.6.1		$\sum_{d\mathbin{\|}n}\lambda\left(d\right)=\begin{cases}1,&n\mbox{ is a square}% ,\\ 0,&\mbox{otherwise}.\end{cases}$
ⓘ Symbols: $\lambda\left(\NVar{n}\right)$ : Liouville’s function, $d$ : positive integer and $n$ : positive integer Permalink: http://dlmf.nist.gov/27.6.E1 Encodings: TeX, pMML, png See also: Annotations for §27.6 and Ch.27

If $f$ is multiplicative, then

27.6.2		$\sum_{d\mathbin{\|}n}\mu\left(d\right)f(d)=\prod_{p\mathbin{\|}n}(1-f(p)),$
$n>1$ .
ⓘ Symbols: $\mu\left(\NVar{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 See also: Annotations for §27.6 and Ch.27

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

27.6.3	$\displaystyle\sum_{d\mathbin{\|}n}\|\mu\left(d\right)\|$	$\displaystyle=2^{\nu\left(n\right)},$
ⓘ Symbols: $\mu\left(\NVar{n}\right)$ : Möbius function, $\nu\left(\NVar{n}\right)$ : number of distinct primes dividing a number, $d$ : positive integer and $n$ : positive integer Permalink: http://dlmf.nist.gov/27.6.E3 Encodings: TeX, pMML, png See also: Annotations for §27.6 and Ch.27
27.6.4	$\displaystyle\sum_{d^{2}\mathbin{\|}n}\mu\left(d\right)$	$\displaystyle=\|\mu\left(n\right)\|,$
ⓘ Symbols: $\mu\left(\NVar{n}\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer Permalink: http://dlmf.nist.gov/27.6.E4 Encodings: TeX, pMML, png See also: Annotations for §27.6 and Ch.27
27.6.5	$\displaystyle\sum_{d\mathbin{\|}n}\frac{\|\mu\left(d\right)\|}{\phi\left(d\right)}$	$\displaystyle=\frac{n}{\phi\left(n\right)},$
ⓘ Symbols: $\phi\left(\NVar{n}\right)$ : Euler’s totient, $\mu\left(\NVar{n}\right)$ : Möbius function, $d$ : positive integer and $n$ : positive integer Permalink: http://dlmf.nist.gov/27.6.E5 Encodings: TeX, pMML, png See also: Annotations for §27.6 and Ch.27

27.6.6		$\sum_{d\mathbin{\|}n}\phi_{k}\left(d\right)\left(\frac{n}{d}\right)^{k}=1^{k}+2% ^{k}+\dots+n^{k},$
ⓘ Symbols: $\phi_{\NVar{k}}\left(\NVar{n}\right)$ : sum of powers of integers relatively prime to a number, $d$ : positive integer, $k$ : positive integer and $n$ : positive integer Permalink: http://dlmf.nist.gov/27.6.E6 Encodings: TeX, pMML, png See also: Annotations for §27.6 and Ch.27

27.6.7		$\sum_{d\mathbin{\|}n}\mu\left(d\right)\left(\frac{n}{d}\right)^{k}=J_{k}\left(n% \right),$
ⓘ Symbols: $J_{\NVar{k}}\left(\NVar{n}\right)$ : Jordan’s function, $\mu\left(\NVar{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 See also: Annotations for §27.6 and Ch.27

27.6.8		$\sum_{d\mathbin{\|}n}J_{k}\left(d\right)=n^{k}.$
ⓘ Symbols: $J_{\NVar{k}}\left(\NVar{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 See also: Annotations for §27.6 and Ch.27