数论函数

积性函数

设整数集合 $D$ 满足条件：若 $m,n \in D$，则 $mn \in D$。定义在集合 $D$ 上的数论函数 $f(n)$ 称为 积性函数，如果满足

$f(mn)=f(m)f(n),\quad (m,n)=1,m,n\in D$

$f(n)$ 称为完全积性函数，如果满足：

$f(mn)=f(m)f(n),\quad m,n\in D$

积性函数的证明我们通常从标准素因数分解式开始。

除数函数 $\tau$

$\tau(a)$ 或 $d(a)$ 表示 $a$ 的所有正除数的个数。

$\tau(a)=(\alpha_1+1) \cdots(\alpha_s+1)=\tau(p_1^{\alpha_1})\cdots\tau(p_s^{\alpha_s})$

$\tau(a)$ 是积性函数，若 $m,n$ 互质，那么 $m,n$ 的标准素因数分解式中质数底数都不同，显然 $\tau(m,n)=\tau(m)\tau(n)$。

$\tau(a)$ 是不是完全积性函数，答案是否定的，因为 $\tau(4)\not=\tau(2)^2$。

除数和函数 $\sigma$

$\sigma(a)$ 表示 $a$ 的所有正除数之和。

显然：

$\sigma(a)=\frac{p_1^{\alpha_1+1}-1}{p_1-1} \times \cdots=\sigma(p_1^{\alpha_1})\cdots\sigma(p_s^{\alpha_s})$

同上。

欧拉（Euler）函数 $\varphi$

$\varphi(a)=\sum_{i=1}^a [(i,a)=1]$

还是从标准素因数分解式中出发，考虑 $p_1$ 这一个因子，互质的占总体的比例为 $1-\frac{1}{p_1}$，那么剩下也是同理。（其实这不能算严谨证明）

$\varphi(a)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_s})$

其他的小性质：

若 $n$ 为奇数，则 $\varphi(2n)=\varphi(n)$

原因是 2 与 $n$ 互质而且 $\varphi(2)=1$。

若 $p$ 为质数，$n=p^k$，则 $\varphi(n)=p^k-p^{k-1}$

由计算式出发。

若 $n>2$，则 $\varphi(n)$ 为偶数

若 $i$ 与 $n$ 互质，则 $n-i$ 与 $n$ 互质，而 $n-i=i$ 时，$i=n/2$，$n$ 为大于 $2$ 的偶数，显然 $i$ 与 $n$ 不互质。

若 $n>1$，则小于等于 $n$ 且与 $n$ 互质的数的和为 $\frac{n\times\varphi(n)}{2}$

同上，配对即可。

重要性质

$\sum_{d|n}\varphi(d)=n$

这种表达形式的常见思路是变换求和符号，自己起个名字叫“桶变换”，枚举 $d$，使得 $\gcd(k,n)=d$，其中 $k<n$。

记 $f(d)=\sum_{k=1}^{n-1}[\gcd(k,n)=d]$，那么

$n=\sum_{d=1}^n f(d)$

因为恰好将 $1,\cdots ,n$ 的所有 $k$ 覆盖了一遍。

同时 $\gcd(k,n)=d \Rightarrow \gcd(k/d,n/d)=1$。

那么 $f(d)=\varphi(n/d)$。

$n=\sum_{d=1}^nf(d)=\sum_{d|n}f(d)=\sum_{d|n}\varphi(n/d)=\sum_{d|n}\varphi(d)$

之后会使用莫比乌斯变换证明。

Legendre 符号

咕

莫比乌斯函数 $\mu$

$\mu(n)=\left\{\begin{matrix} 1& n=1\\[2ex] (-1)^s& n=p_1\times p_2 \times \cdots \times p_s = \prod\limits_{i=1}^{s}p_i(\forall p_i \neq p_j)\\[2ex] 0& \rm others\\ \end{matrix}\right.$

$\mu(n)$ 的语言描述

如果 $n$ 存在一个 $p^2$ 的因数，则 $\mu(n)=0$。

否则，设 $s_n$ 为 $n$ 的素因数个数，$\mu(n)=(-1)^{s_n}$，特别地，$s_0=1$。

证明 $\mu(n)$ 是积性函数

若 $\mu(n)$ 存在大于 $1$ 的平方因子，$\mu(n)=0$，则 $\mu(nm)=0$。

若 $\mu(n)$，$\mu(m)$ 均不为 $0$，因为 $n,m$ 互质，则 $n,m$ 的质因子互不重合。

则 $\mu(nm)=(-1)^{s_ns_m}=(-1)^{s_n}(-1)^{s_m}=\mu(n)\mu(m)$。

显然满足积性的条件。

莫比乌斯函数的性质、莫比乌斯变换

对于给定的数论函数，考虑 $F(n)=\sum_{d|n}f(d)$。

那么：

$\begin{aligned}\tau(n) &= \sum_{d|n}1\\\sigma(n) &= \sum_{d|n}d\\n &= \sum_{d|n}\varphi(d)\\ [n=1] &= \sum_{d|n}\mu(d)\end{aligned}$

对于最后一个等式，我们分类讨论。

1. $n=1$，由定义 $\mu(1)=1$。

2. 对于 $n>1$，将 $n$ 分解为 $p_1^{\alpha_1}\cdots p_s^{\alpha_s}$。

   显然只有 $\alpha_i=0/1$ 的情况我们需要考虑。

   $\sum_{d|n}\mu(d)=\sum_{j=0}^s \binom{j}{s}(-1)^j=(1-1)^s=0$。

常见数论函数的符号

$\begin{aligned} \varepsilon(n)&=[n=1]\\ Id_k(n)&=n^k,Id(n)=n\\ one(n)&=1 \end{aligned}$

这两个函数都是积性函数。

狄利克雷卷积

$(f*g)(n)=\sum_{xy=n}f(x)g(y)$

也可以写作：

$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)$

积性函数的狄利克雷卷积

若 $f,g$ 均为积性函数，证明 $(f*g)$ 也为积性函数。

由定义出发，我们想要证明 $(f*g)(nm)=(f*g)(n)\times (f*g)(m)$。

$\begin{aligned} (f*g)(nm) &= \sum_{d|nm}f(d)g(\frac{nm}{d})\\ (f*g)(n) &= \sum_{d_1|n}f(d_1)g(\frac{n}{d_1})\\ (f*g)(m) &= \sum_{d_2|m}f(d_2)g(\frac{m}{d_2}) \end{aligned}$

不妨枚举 $d_1,d_2$，令 $d=d_1\times d_2$。

$\begin{aligned} f(d_1)f(d_2)g(\frac{n}{d_1})g(\frac{m}{d_2}) &= f(d_1d_2)g(\frac{nm}{d_1d_2})\\ &=f(d)g(\frac{nm}{d}) \end{aligned}$

对每一项都这么做，即可证明 $(f*g)(nm)=(f*g)(n)\times (f*g)(m)$。

数论函数的关系

$(Id*one)(n)=\sum_{d|n}Id(d)=\sigma(n)\\ (\varphi*one)(n)=\sum_{d|n}\varphi(n)=Id(n)\\$

狄利克雷卷积的性质

交换律、结合律、对加法有分配律。

单位元：

$\varepsilon*f=f$

逆元：

$f*f^{-1}=\varepsilon$

莫比乌斯反演

对于上述的变换，有反演：

$f(n)=\sum_{d|n}F(d)\mu(n/d)=\sum_{d|n}F(n/d)\mu(d)$

如何证明：

$\begin{aligned}\sum_{d|n}\mu(d)F(n/d) &= \sum_{d|n}\mu(d)\sum_{j|(n/d)}f(j)\\&=\sum_{d|n} \mu(n/d)\sum_{j|d} f(j) \\&=\sum_{j|n}f(j)\sum_{k|j} \mu(n/k) \\&=\sum_{j|n}f(j)\sum_{k|(n/j)} \mu(k) \\&=\sum_{j|n}f(j)[n/j=1]\\&=f(n)\end{aligned}$

总结：

1. 从定义出发。
2. 改变求和顺序。（$d \leftrightarrow n/d$）
3. 交换求和符号。

莫比乌斯反演的狄利克雷卷积形式表示

$F=f*one \Leftrightarrow f=F*\mu$

证明 $\varphi$ 是积性函数

等价于 $\varphi(n)=\sum_{d|n} \mu(d)n/d$。

这相当于 $\varphi(n)=(Id*\mu)(n)$，是积性函数。

特殊值的分析

研究 $f(n)$，需要研究 $n$ 的分解，也就转化为研究 $f(p^\alpha)$。

$\begin{aligned} f(p^\alpha) &= \sum_{d|p^\alpha}\mu(d)F(n/d) \\ &=\mu(1)F(p^\alpha)+\mu(p)F(p^{\alpha-1})\\ &=F(p^\alpha)-F(p^{\alpha-1}) \end{aligned}$

比如说，对于 $f(x)=\varphi(x)$：

$\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}\\ \varphi(a)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_s})$

对于 $f(x)=\sigma(x)$：

$\sigma(p^\alpha)=\frac{p^{\alpha+1}-1}{p-1}\\ \sigma(a)=\prod_{i=1}^s\frac{p_1^{\alpha_i+1}-1}{p_i-1}$

只要是积性函数，都可以类似推出。

同时，我们可以一瞥莫比乌斯函数定义的意义：舍去 $p$ 的次数大于 $2$ 的项，因为这些项都可以从 $1,p$ 推出。

证明 $\varphi$ 的重要性质

$\begin{aligned} \sum_{d|p^\alpha}\varphi(d) &= \varphi(1)+\sum_{i=1}^\alpha \varphi(p^i)\\ &= 1+p^{\alpha} -1\\ &=p^\alpha \end{aligned}$

根据 $Id,one,\varphi$ 都是积性函数，得 $\varphi$ 的重要性质。