浅谈算数基本定理和约数定理与常见积性函数

发布于 11 天前  24 次阅读


算数基本定理

定义

又名唯一分解定理。

任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积

N = \prod_{i = 1}^{n} p_i^{c_i}

这里 p_{1} < p_2 < \dots < p_n 均为质数,其中指数c_i 是正整数。这样的分解称为 N 的标准分解式.

证明

不会证明下一个

约数定理

其实我觉得算数基本定理应用在约数定理上才是比较常见的

约数个数定理

定义

设正整数 N, 则其可以被分解为 N = \prod_{i=1}^{n} p_i^{c_i}, 那么它的约数个数为 \prod_{i=1}^{n} (c_i+1)

解释和简证

由约数定义, p_1^{c_1}的约数有 p_1^0, p_1^1, p_1^2, \dots, p_1^{c_1},共有c_1 + 1个. 同理可得每个质因数次幂的约数都有 c_k + 1

所以根据乘法原理 N 的约数个数一共有

\prod_{i=1}^{n} c_i + 1

约数和定理

定义

设正整数 N, 则其可以被分解为 N = \prod_{i=1}^{n} p_i^{c_i}, 由约数个数定理已知 N 的正约数有 \prod_{i=1}^{n} c_i + 1个, 那么它的正约数和为

\prod_{i=1}^{n} \sum_{j=1}^{c_i} p_i ^j

证明

已知 N 可以分解质因数为 p_i , 那么对于每一个 p_i, 都有约数p_1^0, p_1^1, p_1^2,\dots, p_1^{c_1}

同理,p_k^{a_k}的约数有:p_k^0, p_k^1, p_k^2,\dots.p_k^{a_k}

N 的约数实际上是在 p_i 的约数中每个p_i 挑一个乘出来

所以由乘法原理可得.

积性函数

定义

若一个定义在正整数域上的函数f(x)对于任意满足gcd(x,y)=1x,y都有f(x \times y)=f(x) \times f(y),则f(x)是积性函数。

常见积性函数

\mu(i) 莫比乌斯函数

\varphi(i) 欧拉函数

\sigma(i) 约数和函数

d(i) 约数个数函数

f(x) = x^k (k \in N)

线性筛相关

挖坑待填


朴实沉毅