转载自https://oi-wiki.org/math/mobius/
积性函数
定义
若 $gcd(x,y)=1$ 且 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。
性质
若 $f(x)$ 和 $f(y)$ 均为积性函数，则以下函数为积性函数：
$h(x) = f(x^p)$
$h(x) = f^p(x)$
$h(x) = g(x)f(x)$
$h(x) = sum_{d|x} f(d)g(frac{x}{d})$
后面两条性质非常重要，会经常用。它说明了两个积性函数的乘积仍是积性函数、两个积性函数的Dirichlet卷积仍是积性函数。
例如，egin{aligned}
h(x_1x_2) &= sum_{d|x_1x_2} f(d)g(frac{x_1x_2}{d}) \
&= f(1)g(15) + f(3)g(5) + f(5)g(3) + f(15)g(1) \
&= [f(1)g(3) + f(3)g(1)]*[f(1)g(5)+f(5)g(1)] \
&= h(3)h(5)
end{aligned}
例子
- 单位函数：$varepsilon(n) = [n=1]$
- 恒等函数：$id_k(n) = n^k$，$id_1(n)$ 通常简记作 $id(n)$
- 常数函数：$1(n)=1$
- 除数函数：$sigma_k(n) = sum_{d|n}d^k$，$sigma_0(n)$ 通常记作 $d(n)$ 或者 $ au(n)$（表示约数的个数），$sigma_1(n)$ 通常记作 $sigma(n)$
- 莫比乌斯函数：$mu(n)$
Dirichlet卷积
定义
定义两个数论函数 $f,g$的Dirichlet卷积为
$$(f*g)(n) = sum_{d|n}f(d)g(frac{n}{d})$$
性质
Dirichlet卷积满足交换律和结合律
其中 $varepsilon$ 为Dirichlet卷积的单位元（任何函数卷 $varepsilon$ 都为本身）
例子
$displaystyle varepsilon = mu * 1 Leftrightarrow varepsilon (n) = sum_{d|n}mu (d)$
$displaystyle d = 1*1 Leftrightarrow d(n) = sum_{d|n}1$
$displaystyle sigma = ID*1 Leftrightarrow sigma (n) = sum_{d|n}d$
$displaystyle ID = varphi * 1 Leftrightarrow ID(n) = sum _{d|n} varphi (d)$
$displaystyle varphi = mu * ID Leftrightarrow varphi (n) = sum_{d|n}dcdot mu(frac{n}{d})$
还有一个常用来消 $d$ 的，
$ncdot d = ID*ID Leftrightarrow ncdot d(n) = sum_{d|n}ID(d) cdot ID(frac{n}{d})$
证明
1、证 $displaystyle varepsilon (n) = sum_{d|n}mu(d)$.
解：设 $displaystyle n = prod_{i=1}^k{p_i}^{c_i}, {n}' = prod_{i=1}^k p_i$
那么 $displaystyle sum_{d|n}mu (d) = sum_{d|{n}'} mu (d) = sum_{i=0}^k inom{k}{i}(-1)^i = (1-1)^k$.
当 $k=0$ 即 $n=1$ 时值为1否则为0，这就证明了 $displaystyle sum_{d|n}mu (d) = [n=1]$.
2、证 $n = sum_{d|n}varphi (d)$
解：将 $n$ 质因数分解，$displaystyle n = prod_{i=1}^k{p_i}^{c_i}$
首先，因为 $varphi$ 为积性函数，所以 $varphi * 1$ 也是积性函数，
所以 $(varphi * 1)(n) = (varphi * 1)({p_1}^{c_1}) cdot (varphi * 1)({p_2}^{c_2})cdot ... cdot (varphi * 1)({p_k}^{c_k})$.
故我们只要证明当 ${n}' = p^c$ 时，$displaystyle varphi *1 = sum_{d|{n}'} varphi (frac{{n}'}{d}) =ID$ 成立即可。
因为 $p$ 是质数，于是 $d = p^0, p^1, ..., p^c$.
因此：
$$egin{aligned}
varphi *1 &= sum_{d|n}varphi (frac{n}{d}) \
&= sum_{i=0}^c varphi(p^i) \
&= 1 + p^0cdot (p-1) + p^1cdot (p-1) + ... + p^{c-1}(p-1) \
&= p^c
end{aligned}$$
该式子两边同时卷积 $mu$ 可得 $varphi = ID * mu$，即 $varphi (n) = sum_{d|n}dcdot mu (frac{n}{d})$