积性函数的相关概念

积性函数： 对于任意的 $a,b$ 互质，都会有 $f(ab)=f(a)f(b)$，则称 $f(x)$ 是积性函数。

常见的积性函数有：欧拉函数、莫比乌斯函数、最大公约数等等，这里简单证明一下两个欧拉函数和莫比乌斯函数，其他函数的证明方法也都是类似的。

证明莫比乌斯函数是积性函数：

对于任意的 $a,b$ 互质，我们先将 $a$ 和 $b$ 质因数分解，得到 $a=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k},b=q_1^{\beta_1}q_2^{\beta_2}q_t^{\beta_t}$。由于 $a$ 和 $b$ 互质，所以 $p_1 \sim p_k$ 和 $q_1 \sim q_t$ 两两不同。因此 $ab=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k}q_1^{\beta_1}q_2^{\beta_2}q_t^{\beta_t}$。

然后我们看一下 $\mu{(ab)}$ 是多少，可以发现但凡 $\alpha_1 \sim \alpha_k$ 和 $\beta_1 \sim \beta_t$ 中有一个 $\geq 2$，那么 $\mu{(ab)}$ 就是 $0$。而此时 $\mu{(a)}\mu{(b)}$ 也是 $0$，因此此时 $\mu{(ab)}=\mu{(a)}\mu{(b)}$。

剩下的情况就是 $\alpha_1 \sim \alpha_k$ 和 $\beta_1 \sim \beta_t$ 都在 $0 \sim 1$ 之间，可以发现此时 $\mu{(ab)}=(-1)^{k+t}$，而 $\mu{(a)}=(-1)^k,\mu{(b)}=(-1)^t$，所以此时也满足 $\mu{(ab)}=\mu{(a)}\mu{(b)}$。

综上分析可知，莫比乌斯函数是积性函数。

证明欧拉函数的积性函数：

对于任意的 $a,b$ 互质，我们先将 $a$ 和 $b$ 质因数分解，得到 $a=p_1^{\alpha_1}p_2^{\alpha_2}…p_k^{\alpha_k},b=q_1^{\beta_1}q_2^{\beta_2}q_t^{\beta_t}$。由于 $a$ 和 $b$ 互质，所以 $p_1 \sim p_k$ 和 $q_1 \sim q_t$ 两两不同。因此 $\phi{(ab)}=ab(1-\frac{1}{p_1})…(1-\frac{1}{p_k})(1-\frac{1}{q_1})…(1-\frac{1}{q_t})$，可以发现 $\phi{(a)}=a(1-\frac{1}{p_1})…(1-\frac{1}{p_k}),\phi{(b)}=b(1-\frac{1}{q_1})…(1-\frac{1}{q_t})$，因此满足 $\phi{(ab)}=\phi{(a)}\phi{(b)}$。

所以，欧拉函数是积性函数。