积性函数
积性函数
定义
若函数 $f(n)$ 满足 $f(1)=1$ 且 $\forall x,y \in \mathbb{N}^+,\gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。
若函数 $f(n)$ 满足 $f(1)=1$ 且 $\forall x,y \in \mathbb{N}^+$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为完全积性函数。
性质
若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：
- $h(x)=f(x^p)$
- $h(x)=f^p(x)$
- $h(x)=f(x)g(x)$
- $h(x)=\sum_{d \mid x}f(x)g(\frac{x}{d})$
设 $x=\prod p_i^{k_i}$，
- 若 $F(x)$ 为积性函数，则有 $F(x)=\prod F(p_i^{k_i})$。
- 若 $F(x)$ 为完全积性函数，则有 $F(x)=\prod F(p_i)^{k_i}$。
定理
定理 1.1：
如果 $f$ 是积性函数，那么 $F(n)=\sum_{d\mid n}f(d)$ 也是积性函数。
证明：
当 $\gcd(n,m)=1$ 时，$nm$ 的因子必能写成 $n$ 的因子 $d_1$ 与 $m$ 的因子 $d_2$ 之积，
所以 $F(nm)=\sum_{i\mid n}\sum_{j\mid m}f(ij)=\sum_{i\mid n}f(i)\sum_{j\mid m}f(j)=F(n)F(m)$。
例子
- 单位函数：$\varepsilon(n)=[n=1]$（完全积性）
- 恒等函数：$\operatorname{id}_k(n)=n^k$，$\operatorname{id}_1(n)$ 通常简记作 $\operatorname{id}(n)$（完全积性）
- 常数函数：$1(n)=1$（完全积性）
- 除数函数：$\sigma_{k}(n)=\sum_{d\mid n}d^k$，$\sigma_{0}(n)$ 通常简记为 $\operatorname{d}(n)$ 或 $\tau(n)$，$\sigma_{1}(n)$ 通常简记为 $\sigma(n)$
- 欧拉函数：$\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1]$
- 莫比乌斯函数：$\mu(n)=\begin{cases}
1 & n=1 \
0 & \exists d>1,d^2\mid n \
(-1)^k & k;为;n;的不同质因子个数
\end{cases}$
Dirichlet 卷积
定义
对于两个数论函数 $f(x)$ 和 $g(x)$，则它们的 Dirichlet 卷积得到的结果 $h(x)$ 定义为：
$$h(x)=\sum_{d\mid x}f(d)g(x/d)=\sum_{ab=x}f(a)g(b)$$
简记为：$h=f*g$。
性质
- 交换律：$fg=gf$。
- 结合律：$(fg)h=f(gh)$。
- 分配律：$(f+g)h=fh+g*h$。
- 等式的性质：$f=g$ 的充要条件是 $fg=gh$，其中数论函数 $h(x)$ 要满足 $h(1)\neq 0$。
- 单位元：单位函数 $\varepsilon$ 是 Dirichlet 卷积运算中的单位元，即对于任何数论函数 $f$，都有 $f*\varepsilon=f$。
定理
定理 2.1：
两个积性函数的 Dirichlet 卷积也是积性函数。
证明：
设两个积性函数为 $f(x)$ 和 $g(x)$，再记 $h=f*g$。
设 $\gcd(a,b)=1$，则 $h(a)=\sum_{d_1\mid a}f(a)g(a/d_1),h(b)=\sum_{d_2\mid b}f(b)g(b/d_2)$，
所以 $h(a)h(b)=\sum_{d_1\mid a}f(a)g(a/d_1)\sum_{d_2\mid b}f(b)g(b/d_2)=\sum_{d\mid ab}f(d)g(ab/d)=h(ab)$。
例子
- $\varepsilon=\mu *1\iff\varepsilon(n)=\sum_{d\mid n}\mu(d)$
- $d=1*1\iff d(n)=\sum_{d\mid n}1$
- $\sigma=\operatorname{id}*1\iff \sigma(n)=\sum_{d\mid n}d$
- $\varphi=\mu*\operatorname{id}\iff\varphi(n)=\sum_{d\mid n}{d\cdot\mu(n/d)}$
欧拉函数
定理
定理 3.1：
$n=\sum_{d\mid n} \varphi(d)$。
证明：
$f(n)=\sum_{d\mid n} \varphi(d)$ 为积性函数。
证明：当 $\gcd(n,m)=1$ 时，
$\begin{aligned}
& f(n)f(m) \
= & \sum_{i\mid n}\varphi(i)\sum_{j\mid m}\varphi(j) \
= & \sum_{i\mid n}\sum_{j\mid m}(\varphi(i)\varphi(j)) \
= & \sum_{i\mid n}\sum_{j\mid m}\varphi(ij) \
= & \sum_{d\mid nm}\varphi(d) \
= & f(nm)
\end{aligned}$
证毕。
那么根据算术基本定理 $n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$，
由 $f$ 是积性函数可知 $f(n)=f(p_1^{c_1})f(p_2^{c_2})\cdots f(p_k^{c_k})$，
又因为 $f(p^c)=\varphi(1)+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^c)=1+(p-1)+(p^2-p)+\cdots+(p^c-p^{c-1})=p^c$，
所以 $f(n)=f(p_1^{c_1})f(p_2^{c_2})\cdots f(p_k^{c_k})=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}=n$。
定理 3.2：
$\varphi(n)=\sum_{d\mid n}(\mu(d)(n/d))$。
证明：
根据定理 3.1 可得 $\varphi1=\operatorname{id}\iff \varphi\varepsilon=\operatorname{id}*\mu\iff \varphi(n)=\sum_{d\mid n}(\mu(d)(n/d))$。
莫比乌斯函数
定义
$\mu$ 为莫比乌斯函数，定义为：
$$\mu(n)=
\begin{cases} 1 & n=1 \
0 & \exists d>1,d^2\mid n \
(-1)^k & k;为;n;的不同质因子个数
\end{cases}$$
定理
定理 4.1：
$\mu(n)$ 是积性函数。
证明：
假设 $\gcd(n,m)=1$
- 当 $n=1$ 或 $m=1$ 时，若 $n=1$，$\mu(nm)=\mu(n)\mu(m)=\mu(m)$，$m=1$ 时同理；
- 当 $n$ 和 $m$ 中至少有一个数含有平方质因子时，$nm$ 也有平方质因子，$\mu(nm)=\mu(n)\mu(m)=0$；
- 当 $n,m$ 都没有平方质因子且都不为 $1$ 时，假设 $n$ 有 $p$ 个不同质因子个数，$m$ 有 $q$ 个不同质因子个数，$\mu(nm)=(-1)^{p+q}=(-1)^p+(-1)^q=\mu(n)\mu(m)$。
定理 4.2：
$F(n)=\sum_{d \mid n}{\mu(d)}=\begin{cases}1 & n=1 \0 & n>1\end{cases}=\varepsilon(n)=[n=1]$
证明：
当 $n=1$ 时，$F(1)=\sum_{d \mid 1}{\mu(d)}=\mu(1)=1$；
当 $n>1$ 时，因为 $\mu(n)$ 是积性函数，所以 $\mu(n)$ 的因数和函数 $F(n)=\sum_{d \mid n}{\mu(d)}$ 也是积性函数,
现在假设 $p$ 是质数，$F(n)=F(p_1^{k_1})F(p_2^{k_2})\cdots F(p_t^{k_t})$，
而 $F(p^k)=\sum_{d \mid p^k}{\mu(d)}=\mu(1)+\mu(p)+\mu(p^2)+\cdots+\mu(p^k)=1+(-1)+0+\cdots+0=0$，
所以 $F(n)=0$。
定理 4.3：
若 $f$ 是数论函数，$F(n)=\sum_{d \mid n}{f(d)}$，则 $f(n)=\sum_{d \mid n}\mu(d)F(n/d)$。
证明：
$\sum_{d \mid n}\mu(d)F(n/d)=\sum_{d \mid n}\mu(d)\sum_{e \mid (n/d)}{f(e)}=\sum_{e \mid n}f(e)\sum_{d \mid (n/e)}{\mu(d)}$，
根据定理 4.2，当 $e=n$ 时，$\sum_{d \mid (n/e)}{\mu(d)}=1$，否则为 $0$，
所以 $\sum_{e \mid n}(f(e)\sum_{d \mid (n/e)}{\mu(d)})=f(n)$。
参考资料
初等数论及其应用（原书第 6 版）