省选-数学-积性函数

定义

积性函数：

$\forall (a,b),\gcd(a,b)=1,f(ab)=f(a)f(b)$

完全积性函数：

$\forall (a,b),f(ab)=f(a)f(b)$

常见积性函数

莫比乌斯函数

有平方因子显然，否则：

$\mu(mn) = (-1)^{r+s} = (-1)^r (-1)^s = \mu(m) \mu(n)$

欧拉函数

$$\varphi(k)=k\prod_{p\mid k}\left(1-\frac1p\right),$$ $$\varphi(mn)=mn\prod_{p\mid mn}\left(1-\frac1p\right)=mn\prod_{p\mid m}\left(1-\frac1p\right)\prod_{p\mid n}\left(1-\frac1p\right)=\varphi(m)\varphi(n).$$

其他

单位函数：$\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)$ 通常简记作 $d(n)$ 或 $\tau(n)$，$\sigma_{1}(n)$ 通常简记作 $\sigma(n)$。