算术基本定理基础

算术基本定理基础

算术基本定理

​ 对于任意的实数 $x$ 有：（部分虚数不满足，例如 $\sqrt{-5}$）

$x=p_1^{\alpha_1}~p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

​ 其中对于任意的 $p_i$ 都是质数，且 $p_i,\alpha_i \in \mathbb{N}$。

约数函数 $\tau$

​ $\tau(x)$ 表示 $x$ 的所有约数个数，由算术基本定理易知：

$\tau(x)=\prod_{i=1}^{k} {(\alpha_i+1)}$

​ 注意到对于 $p_i$ 的幂次可以为 $[~0~,~\alpha_i~]$，共 $\alpha_i + 1$ 种。

约数和函数 $\sigma$

​ $\sigma(x)$ 表示 $x$ 的所有正约数的和。

$\sigma(x)=\sum_{d|x}d$

$\sigma(x)=\sum_{e_1}^{\alpha_1} \cdots \sum_{e_k=0}^{\alpha_k}p_1^{e_1}\cdots p_k^{e_k}$

$\sigma(x)=\prod_{i=1}^{k} \sum_{j=0}^{\alpha_i}p_i~^{j}$

​ 这时我们利用等比数列求和处理，易知：

$\sigma(x)=\prod_{i=1}^{k}\frac{p_i^{\alpha_i+1}-1}{p_i-1}$

积性性质

​ 注意到：

$\tau({p_i}^{\alpha_i})=\alpha_i+1$

$\sigma({p_i}^{\alpha_i})=\frac{p_i^{\alpha_i+1}-1}{p_i-1}$

​ 所以则有：

$\tau(x)=\prod_{i=1}^{k} \tau({p_i}^{\alpha_i})$

$\sigma(x)=\prod_{i=1}^{k} \sigma({p_i}^{\alpha_i})$

​ 显而易见的，约数函数 $\tau(x)$ 和约数和函数 $\sigma(x)$ 是积性函数，但并非完全积性函数。

一个巧妙的例子

$\sum_{d|n}\frac{1}{d}$

​ 求上式。考虑到算数基本定理不计次序，我们可以感性的理解：

$\sum_{d|n} \frac{1}{d} = \sum_{d|n}\frac{1}{ \frac{n}{d} } = \frac{1}{n} \sum_{d|n}d = \frac{\sigma(n)}{n}$