数论基础知识及拓展

wenqinghua1001 · 2025-07-04 08:55:02 · 算法·理论

教学内容：

1. 整除的性质和特征
2. 质数与合数的性质
3. 公约数与公倍数
4. 同余的性质
5. 数论分块

教学难点：

1. 质数与合数的性质
2. 同余的性质
3. 数论分块的性质和问题的转化
4. 拓展欧几里得和唯一分解定理
5. 欧拉函数与同余四则运算
6. 逆元与矩阵快速幂

1. 整除性质和特征

1.1 整除的定义\ 1.2 整除的性质\ 1.3 整除的特征

1.1 整除的定义

设 a，b 是整数，b \ne 0，如果存在整数 c，使得 a=b \times c 成立，则称 a 被 b 整除，a 是 b 的倍数，b 是 a 的约数（因数或除数），并且使用记号 b \mid a。

1.1.1 约数的正负

约数有正约数和负约数，我们只讨论正约数。

1.1.2 约数的有限性

对于任意非零整数 a，约数的个数是有限的。

1.1.3 约数总有一

\begin{aligned} f(a) &= ({p_1}^0+{p_1}^1+ \cdots +{p_1}^{c_1}) \times ({p_2}^0+{p_2}^1+ \cdots +{p_2}^{c_2}) \times \cdots \times ({p_k}^0+ \cdots+{p_k}^{ck}) \ &=\sum{j=0}^{c_1}{p1}^j \times \sum{j=0}^{c_2}{p2}^j \times \cdots \times \sum{j=0}^{c_k}{pk}^j \ &=\prod{i=1}^{k} \sum_{j=0}^{c_i} {p_i}^j \end{aligned}

\begin{aligned} f(a) &= ({p_1}^0+{p_1}^1+ \cdots +{p_1}^{c_1}) \times ({p_2}^0+{p_2}^1+ \cdots +{p_2}^{c_2}) \times \cdots \times ({p_k}^0+ \cdots+{p_k}^{ck}) \ &=\sum{j=0}^{c_1}{p1}^j \times \sum{j=0}^{c_2}{p2}^j \times \cdots \times \sum{j=0}^{c_k}{pk}^j \ &=\prod{i=1}^{k} \sum_{j=0}^{c_i} {p_i}^j \end{aligned}

证明：设 a=d \times x，b=d \times y，则 (a,b)=d，\begin{bmatrix} a,b \end{bmatrix}=d \times x \times y，则 (a,b) \times \begin{bmatrix} a,b \end{bmatrix} = d \times d \times x \times y= (d \times x) \times (d \times y)=a \times b。

3.2.2 关系二：大小

看一眼就知道。

3.2.3 关系三：倍数关系

3.2.4 关系四：加减

显而易见。

3.3 更相减损术

3.3.1 回顾辗转相除法

原理：(a,b)=(a,a \bmod b)。

int gcd1(int a,int b){
    for(int c;b>0;c=a%b,a=b,b=c);
    return a;
}
int gcd2(int a,int b){
    if(b==0) return a;
    return gcd2(b,a%b);
}

3.3.2 更相减损术的介绍与拓展

注意，更相减损术并不比辗转相除法慢，元素多的时候反而比辗转相除法快。

原理：(a,b)=(a,\lvert b-a \rvert)，保证 b \ge a。

拓展：

模运算的除法：

结论：

最后，对任意的正整数 n，其不同商的个数不会超过 2 \times \sqrt{n}。

5.2.2 性质二：连续整除

性质：