第3章整除性 (Divisibility)

一、导读

3.1 本章学习目标

在本章结束时，你将能够：

理解整除关系的定义和基本性质
运用欧几里得算法高效计算最大公约数
掌握贝祖等式：理解 gcd(a,b) = ax + by 的意义和求解方法
理解素数的分布规律和素数定理
应用算术基本定理进行因数分解
使用同余运算解决模算术问题
理解中国剩余定理及其在密码学中的应用

3.2 为什么本章如此重要

数论常被称为"数学的皇后"，而整除性是数论的基础。对于计算机科学家而言，数论不再是纯理论的学科，而是有着广泛的实际应用：

密码学：RSA 加密算法依赖于大整数分解的困难性

哈希函数：散列表的设计需要理解模运算

随机数生成：伪随机数生成器基于数论原理

错误检测与纠正：校验码（如 ISBN、信用卡号）使用模运算

算法设计：许多算法（如快速幂、模逆元）依赖数论技巧

《具体数学》将数论放在早期章节，是因为它为后续的求和、二项式系数、特殊数等内容提供了基础工具。理解整除性和素数，是掌握离散数学的关键。

对于程序员而言，数论提供了一种精确处理整数的方式。与浮点数不同，整数运算是精确的，这使得数论算法在需要高精度的场景中不可或缺。

3.3 核心问题引导

在阅读本章之前，请思考以下问题：

如何判断一个数是否能被另一个数整除？整除关系有哪些基本性质？

欧几里得算法为什么能高效计算最大公约数？它的时间复杂度是多少？

什么是贝祖等式？如何用扩展欧几里得算法求解 ax + by = gcd(a,b)？

素数有无穷多个吗？如何证明？

算术基本定理说每个整数有唯一的素因数分解，这个"唯一"如何保证？

同余运算与普通算术有何异同？为什么 a ≡ b (mod m) 如此有用？

中国剩余定理解决了什么问题？它在实际中有何应用？

费马小定理和欧拉定理的内容是什么？它们如何用于快速幂计算？

二、核心概念详解

3.1 整除关系与基本性质

定义

设 a, b 是整数，b ≠ 0。如果存在整数 k 使得 a = bk，则称 b 整除 a，记作 b | a。

此时：

b 是 a 的因数（divisor）或约数
a 是 b 的倍数（multiple）

通俗地说，b | a 意味着 a 除以 b 没有余数。

基本性质

性质 1：自反性

对任意整数 a ≠ 0，有 a | a（因为 a = a × 1）。

性质 2：传递性

如果 a | b 且 b | c，则 a | c。

证明：a | b 意味着 b = ak₁，b | c 意味着 c = bk₂。所以 c = ak₁k₂，即 a | c。

性质 3：线性组合

如果 a | b 且 a | c，则 a | (bx + cy) 对任意整数 x, y 成立。

证明：b = ak₁，c = ak₂，所以 bx + cy = a(k₁x + k₂y)，即 a | (bx + cy)。

性质 4：大小关系

如果 a | b 且 b ≠ 0，则 |a| ≤ |b|。

性质 5：零的整除

对任意非零整数 a，有 a | 0（因为 0 = a × 0）。但 0 不整除任何非零整数。

带余除法

定理（带余除法）：对任意整数 a 和正整数 b，存在唯一的整数 q 和 r，使得：

$$a = bq + r, \quad 0 \leq r < b$$

其中：

q 称为商（quotient），记作 q = ⌊a/b⌋
r 称为余数（remainder），记作 r = a mod b

直观理解：这就是我们小学学的"除法"：a 除以 b，得到商 q 和余数 r。

存在性证明：考虑序列 ..., a-2b, a-b, a, a+b, a+2b, ...。其中必有元素落在 [0, b) 区间内，取最小的非负元素即为 r。

唯一性证明：假设有两组 (q₁, r₁) 和 (q₂, r₂) 满足条件，则 bq₁ + r₁ = bq₂ + r₂，即 b(q₁-q₂) = r₂-r₁。由于 |r₂-r₁| < b，只有 r₁ = r₂ 且 q₁ = q₂。

3.2 最大公约数与欧几里得算法

最大公约数的定义

设 a, b 是不全为零的整数。最大公约数（Greatest Common Divisor, GCD）是能同时整除 a 和 b 的最大正整数，记作 gcd(a, b)。

例如：gcd(12, 18) = 6，因为 6 是能同时整除 12 和 18 的最大整数。

特殊情况：

gcd(a, 0) = |a|
gcd(0, 0) 通常定义为 0
如果 gcd(a, b) = 1，称 a 和 b 互质（coprime 或 relatively prime）

欧几里得算法

欧几里得算法（Euclidean Algorithm）是计算 gcd 的高效方法，基于以下观察：

关键引理：gcd(a, b) = gcd(b, a mod b)

证明：设 a = bq + r，其中 r = a mod b。

如果 d | a 且 d | b，则 d | (a - bq) = r，所以 d | r。
如果 d | b 且 d | r，则 d | (bq + r) = a，所以 d | a。
因此，a 和 b 的公因数集合等于 b 和 r 的公因数集合，最大值也相等。

算法步骤：

输入 a, b（假设 a ≥ b > 0）

计算 r = a mod b

如果 r = 0，返回 b

否则，令 a = b, b = r，回到步骤 2

示例：计算 gcd(252, 105)

252 = 105 × 2 + 42    → gcd(252, 105) = gcd(105, 42)
105 = 42 × 2 + 21     → gcd(105, 42) = gcd(42, 21)
42 = 21 × 2 + 0       → gcd(42, 21) = 21

所以 gcd(252, 105) = 21。

时间复杂度分析

欧几里得算法的效率非常高。拉梅定理（Lamé's Theorem）指出：

定理：欧几里得算法计算 gcd(a, b)（a > b > 0）所需的除法次数不超过 5 × log₁₀ b。

更精确地，最坏情况发生在 a 和 b 是连续的斐波那契数时。设 F_n 是第 n 个斐波那契数，则计算 gcd(F_n, F_{n-1}) 需要 n-2 次除法。

由于 F_n ≈ φⁿ/√5（其中 φ = (1+√5)/2 ≈ 1.618），所以算法的时间复杂度为 O(log min(a, b))。

代码实现

python

def gcd_euclidean(a, b):
    """欧几里得算法计算最大公约数"""
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

# 测试
print(f"gcd(252, 105) = {gcd_euclidean(252, 105)}")  # 21
print(f"gcd(100, 75) = {gcd_euclidean(100, 75)}")    # 25
print(f"gcd(17, 13) = {gcd_euclidean(17, 13)}")      # 1 (互质)

3.3 贝祖等式与扩展欧几里得算法

贝祖等式

贝祖等式（Bézout's Identity）是数论中最优美的结果之一：

定理：设 a, b 是不全为零的整数，d = gcd(a, b)。则存在整数 x, y 使得：

$$ax + by = d$$

此外，d 是形如 ax + by 的最小正整数。

直观理解：gcd(a, b) 不仅可以定义为"最大公因数"，还可以定义为"a 和 b 的线性组合能表示的最小正整数"。这两种定义是等价的。

示例：gcd(252, 105) = 21。我们可以找到 x, y 使得 252x + 105y = 21。

通过观察：252 - 2×105 = 42，105 - 2×42 = 21。

回溯：21 = 105 - 2×42 = 105 - 2×(252 - 2×105) = 5×105 - 2×252。

所以 x = -2, y = 5 是一组解：252×(-2) + 105×5 = -504 + 525 = 21。✓

扩展欧几里得算法

扩展欧几里得算法不仅计算 gcd(a, b)，还找到满足贝祖等式的 x 和 y。

算法思想：在欧几里得算法的每一步，维护当前余数表示为 a 和 b 的线性组合。

代码实现：

python

def extended_gcd(a, b):
    """
    扩展欧几里得算法
    返回 (gcd, x, y) 使得 a*x + b*y = gcd
    """
    if b == 0:
        return a, 1, 0
    
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

# 测试
g, x, y = extended_gcd(252, 105)
print(f"gcd(252, 105) = {g}")
print(f"252 * {x} + 105 * {y} = {252 * x + 105 * y}")

g, x, y = extended_gcd(35, 15)
print(f"\ngcd(35, 15) = {g}")
print(f"35 * {x} + 15 * {y} = {35 * x + 15 * y}")

算法正确性证明：

基础情况：b = 0 时，gcd(a, 0) = a，且 a×1 + 0×0 = a。成立。

归纳步骤：假设 extended_gcd(b, a mod b) 返回 (g, x₁, y₁)，满足 bx₁ + (a mod b)y₁ = g。

由于 a mod b = a - ⌊a/b⌋×b，代入得：

$$bx_1 + (a - \lfloor a/b \rfloor b)y_1 = g$$

$$ay_1 + b(x_1 - \lfloor a/b \rfloor y_1) = g$$

所以 x = y₁，y = x₁ - ⌊a/b⌋y₁ 满足 ax + by = g。证毕。

应用：模逆元

贝祖等式的一个重要应用是计算模逆元。

定义：设 a, m 是正整数，gcd(a, m) = 1。如果存在整数 x 使得 ax ≡ 1 (mod m)，则 x 称为 a 模 m 的乘法逆元，记作 a⁻¹ mod m。

求解方法：由贝祖等式，存在 x, y 使得 ax + my = 1。两边模 m 得 ax ≡ 1 (mod m)。所以 x mod m 就是 a 的模逆元。

python

def mod_inverse(a, m):
    """计算 a 模 m 的乘法逆元"""
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError(f"{a} 和 {m} 不互质，逆元不存在")
    return x % m

# 测试：计算 3 模 11 的逆元
inv = mod_inverse(3, 11)
print(f"3 模 11 的逆元是 {inv}")
print(f"验证: 3 * {inv} mod 11 = {(3 * inv) % 11}")  # 应该是 1

3.4 素数与算术基本定理

素数的定义

素数（Prime Number）是大于 1 的正整数，且只有 1 和自身两个正因数。

前几个素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

合数（Composite Number）是大于 1 但不是素数的正整数，即可以分解为两个较小整数的乘积。

注意：1 既不是素数也不是合数。

素数的无穷性

定理（欧几里得）：素数有无穷多个。

证明（反证法）：假设素数只有有限个，设为 p₁, p₂, ..., pₙ。

考虑数 N = p₁p₂...pₙ + 1。

N 不能被任何 pᵢ 整除（因为 N mod pᵢ = 1）。所以 N 要么是素数，要么有不在 {p₁, ..., pₙ} 中的素因数。无论哪种情况，都与假设矛盾。

因此，素数有无穷多个。证毕。

这个证明不仅证明了素数的无穷性，还提供了一个构造新素数的方法（虽然得到的 N 不一定是素数）。

算术基本定理

算术基本定理（Fundamental Theorem of Arithmetic）：

定理：每个大于 1 的正整数都可以唯一地表示为素数的乘积（不计因数的顺序）。

即，对任意 n > 1，存在唯一的素数 p₁ < p₂ < ... < pₖ 和正整数 e₁, e₂, ..., eₖ，使得：

$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$

示例：

12 = 2² × 3¹
60 = 2² × 3¹ × 5¹
100 = 2² × 5²

存在性证明：对 n 进行归纳。

n = 2 时，2 是素数，结论成立。
假设对所有小于 n 的数结论成立。
如果 n 是素数，结论成立。
如果 n 是合数，则 n = ab，其中 1 < a, b < n。由归纳假设，a 和 b 都可以分解为素数乘积，所以 n 也可以。

唯一性证明：需要使用欧几里得引理：如果 p 是素数且 p | ab，则 p | a 或 p | b。

假设有两种分解：n = p₁p₂...pₖ = q₁q₂...qₘ。

由于 p₁ | q₁q₂...qₘ，由欧几里得引理，p₁ 必整除某个 qⱼ。由于 qⱼ 也是素数，所以 p₁ = qⱼ。消去 p₁ 和 qⱼ，继续这个过程，最终得到 k = m 且两组素数相同（可能顺序不同）。证毕。

素因数分解算法

试除法是最简单的素因数分解算法：

python

def prime_factorization(n):
    """试除法进行素因数分解"""
    if n <= 1:
        return {}
    
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    
    return factors

# 测试
for n in [12, 60, 100, 97, 360]:
    factors = prime_factorization(n)
    factor_str = " × ".join(f"{p}^{e}" for p, e in sorted(factors.items()))
    print(f"{n:4d} = {factor_str}")

输出：

12 = 2^2 × 3^1
  60 = 2^2 × 3^1 × 5^1
 100 = 2^2 × 5^2
  97 = 97^1
 360 = 2^3 × 3^2 × 5^1

时间复杂度：O(√n)，对于大整数效率很低。这也是 RSA 加密安全性的基础：目前没有已知的多项式时间素因数分解算法。

3.5 同余运算

同余的定义

设 a, b 是整数，m 是正整数。如果 m | (a - b)，则称 a 与 b 模 m 同余，记作：

$$a \equiv b \pmod{m}$$

通俗地说，a 和 b 除以 m 的余数相同。

等价定义：a ≡ b (mod m) 当且仅当 a mod m = b mod m。

基本性质

性质 1：自反性

a ≡ a (mod m)

性质 2：对称性

如果 a ≡ b (mod m)，则 b ≡ a (mod m)

性质 3：传递性

如果 a ≡ b (mod m) 且 b ≡ c (mod m)，则 a ≡ c (mod m)

这三条性质说明同余是一个等价关系，它将整数划分为 m 个等价类：[0], [1], ..., [m-1]。

性质 4：加法保持

如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则 a + c ≡ b + d (mod m)

性质 5：乘法保持

如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则 ac ≡ bd (mod m)

性质 6：幂保持

如果 a ≡ b (mod m)，则 aⁿ ≡ bⁿ (mod m) 对任意正整数 n 成立

这些性质使得同余运算可以像普通算术一样进行加减乘运算。

应用：快速幂取模

计算 aⁿ mod m 时，直接计算 aⁿ 可能溢出。利用同余性质，可以在每一步取模：

python

def fast_pow_mod(base, exp, mod):
    """快速幂取模：计算 base^exp mod mod"""
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp >> 1
        base = (base * base) % mod
    return result

# 测试：计算 3^100 mod 17
print(f"3^100 mod 17 = {fast_pow_mod(3, 100, 17)}")

# 验证（用小指数）
print(f"3^4 mod 17 = {fast_pow_mod(3, 4, 17)}")  # 81 mod 17 = 13
print(f"3^4 = {3**4}, 81 mod 17 = {81 % 17}")

时间复杂度：O(log n)，远优于朴素方法的 O(n)。

3.6 费马小定理与欧拉定理

费马小定理

费马小定理（Fermat's Little Theorem）：

定理：如果 p 是素数，a 是任意整数且 p ∤ a，则：

$$a^{p-1} \equiv 1 \pmod{p}$$

等价形式：对任意整数 a，有 $a^p \equiv a \pmod{p}$。

应用：费马小定理可用于素性测试和模逆元计算。

示例：p = 7, a = 3。

3⁶ = 729 = 7 × 104 + 1，所以 3⁶ ≡ 1 (mod 7)。✓

模逆元的快速计算：如果 p 是素数且 p ∤ a，则 a^{p-2} ≡ a⁻¹ (mod p)。

python

def mod_inverse_fermat(a, p):
    """使用费马小定理计算模逆元（p 必须是素数）"""
    return fast_pow_mod(a, p - 2, p)

# 测试：计算 3 模 7 的逆元
inv = mod_inverse_fermat(3, 7)
print(f"3 模 7 的逆元是 {inv}")
print(f"验证: 3 * {inv} mod 7 = {(3 * inv) % 7}")  # 应该是 1

欧拉函数

欧拉函数（Euler's Totient Function）φ(n) 定义为不超过 n 且与 n 互质的正整数的个数。

计算公式：如果 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$，则：

$$\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) = n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdots \frac{p_k-1}{p_k}$$

特殊值：

φ(1) = 1
φ(p) = p - 1（p 是素数）
φ(pᵉ) = pᵉ - pᵉ⁻¹ = pᵉ⁻¹(p-1)

示例：φ(12) = φ(2² × 3) = 12 × (1-1/2) × (1-1/3) = 12 × 1/2 × 2/3 = 4。

与 12 互质的数：1, 5, 7, 11，共 4 个。✓

欧拉定理

欧拉定理（Euler's Theorem）是费马小定理的推广：

定理：如果 gcd(a, m) = 1，则：

$$a^{\phi(m)} \equiv 1 \pmod{m}$$

当 m 是素数时，φ(m) = m-1，欧拉定理退化为费马小定理。

应用：RSA 加密算法的安全性基于欧拉定理。

三、程序员的视角

3.1 在算法分析中的应用

哈希函数

哈希表的设计依赖模运算：hash(key) = key mod m。选择合适的 m（通常是素数）可以减少冲突。

随机数生成

线性同余生成器（LCG）使用递推关系：X_{n+1} = (aXₙ + c) mod m。参数的选择影响随机性质量。

循环检测

Floyd 判圈算法和 Brent 算法使用模算术检测链表或序列中的循环。

3.2 常见陷阱与误区

陷阱 1：负数的模运算

在不同编程语言中，负数取模的结果可能不同：

Python: -7 mod 3 = 2
C/C++: -7 % 3 = -1

避免方法：始终确保结果为非负：(a % m + m) % m。

陷阱 2：整数溢出

在大数运算中，中间结果可能溢出。使用模运算时，应在每一步取模。

陷阱 3：误用费马小定理

费马小定理要求 p 是素数。对于合数 m，a^{m-1} ≡ 1 (mod m) 不一定成立。

3.3 与其他层级的联系

密码学：RSA、Diffie-Hellman、椭圆曲线加密都基于数论
编码理论：纠错码使用有限域（基于素数幂）
计算机科学理论：素性测试、因数分解的复杂度是 P vs NP 问题的核心

四、代码实战

4.1 示例一：完整的数论工具库

python

class NumberTheory:
    """数论工具库"""
    
    @staticmethod
    def gcd(a, b):
        """最大公约数"""
        while b:
            a, b = b, a % b
        return a
    
    @staticmethod
    def lcm(a, b):
        """最小公倍数"""
        return abs(a * b) // NumberTheory.gcd(a, b)
    
    @staticmethod
    def extended_gcd(a, b):
        """扩展欧几里得算法"""
        if b == 0:
            return a, 1, 0
        g, x1, y1 = NumberTheory.extended_gcd(b, a % b)
        return g, y1, x1 - (a // b) * y1
    
    @staticmethod
    def mod_inverse(a, m):
        """模逆元"""
        g, x, _ = NumberTheory.extended_gcd(a, m)
        if g != 1:
            raise ValueError("逆元不存在")
        return x % m
    
    @staticmethod
    def is_prime(n):
        """简单的素性测试"""
        if n < 2:
            return False
        if n < 4:
            return True
        if n % 2 == 0 or n % 3 == 0:
            return False
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        return True
    
    @staticmethod
    def prime_factors(n):
        """素因数分解"""
        factors = {}
        d = 2
        while d * d <= n:
            while n % d == 0:
                factors[d] = factors.get(d, 0) + 1
                n //= d
            d += 1
        if n > 1:
            factors[n] = factors.get(n, 0) + 1
        return factors
    
    @staticmethod
    def euler_totient(n):
        """欧拉函数"""
        result = n
        factors = NumberTheory.prime_factors(n)
        for p in factors:
            result -= result // p
        return result
    
    @staticmethod
    def fast_pow_mod(base, exp, mod):
        """快速幂取模"""
        result = 1
        base %= mod
        while exp > 0:
            if exp & 1:
                result = (result * base) % mod
            exp >>= 1
            base = (base * base) % mod
        return result

# 测试
nt = NumberTheory()
print("=== 数论工具库测试 ===")
print(f"gcd(252, 105) = {nt.gcd(252, 105)}")
print(f"lcm(12, 18) = {nt.lcm(12, 18)}")
print(f"3 模 11 的逆元 = {nt.mod_inverse(3, 11)}")
print(f"97 是素数吗？{nt.is_prime(97)}")
print(f"60 的素因数分解: {nt.prime_factors(60)}")
print(f"φ(12) = {nt.euler_totient(12)}")
print(f"3^100 mod 17 = {nt.fast_pow_mod(3, 100, 17)}")

4.2 示例二：RSA 加密演示

python

import random

class SimpleRSA:
    """简化的 RSA 加密演示"""
    
    def __init__(self, p, q):
        """初始化：选择两个素数 p 和 q"""
        self.p = p
        self.q = q
        self.n = p * q
        self.phi = (p - 1) * (q - 1)
        
        # 选择公钥指数 e
        self.e = 65537  # 常用值
        while NumberTheory.gcd(self.e, self.phi) != 1:
            self.e += 2
        
        # 计算私钥指数 d
        self.d = NumberTheory.mod_inverse(self.e, self.phi)
    
    def encrypt(self, message):
        """加密"""
        return NumberTheory.fast_pow_mod(message, self.e, self.n)
    
    def decrypt(self, ciphertext):
        """解密"""
        return NumberTheory.fast_pow_mod(ciphertext, self.d, self.n)

# 测试
p, q = 61, 53  # 小素数用于演示
rsa = SimpleRSA(p, q)
print(f"\n=== RSA 加密演示 ===")
print(f"p = {p}, q = {q}")
print(f"n = {rsa.n}, φ(n) = {rsa.phi}")
print(f"公钥: (e={rsa.e}, n={rsa.n})")
print(f"私钥: (d={rsa.d}, n={rsa.n})")

message = 42
ciphertext = rsa.encrypt(message)
decrypted = rsa.decrypt(ciphertext)
print(f"原始消息: {message}")
print(f"加密后: {ciphertext}")
print(f"解密后: {decrypted}")
print(f"验证: {'成功' if message == decrypted else '失败'}")

五、深入思考

5.1 历史背景

数论的历史可以追溯到古希腊。欧几里得（Euclid, 约公元前 300 年）在《几何原本》中给出了欧几里得算法和素数无穷性的证明。费马（Pierre de Fermat, 1607-1665）提出了费马小定理等多个猜想。欧拉（Leonhard Euler, 1707-1783）系统发展了数论，引入了欧拉函数和欧拉定理。

现代数论与密码学的结合始于 1970 年代。RSA 算法（Rivest-Shamir-Adleman, 1977）将数论从纯数学推向了实际应用的前沿。

5.2 未解决的问题

黎曼假设：素数分布的精确规律仍是数学中最大的未解之谜

哥德巴赫猜想：每个大于 2 的偶数都可以表示为两个素数之和

孪生素数猜想：存在无穷多对相差 2 的素数

P vs NP：素因数分解是否有多项式时间算法？

5.3 延伸阅读

《数论导引》 - Hardy & Wright

经典数论教材，深入全面。

《具体数学》第 4 章 - Graham, Knuth, Patashnik

本章内容的源头。

《算法导论》第 31 章 - Cormen et al.

数论算法的计算视角。

"Prime Numbers: A Computational Perspective" - Crandall & Pomerance

素数的计算方法和应用。

六、实验笔记

实验一：素数筛法的性能比较

目标：比较埃拉托斯特尼筛法和试除法在生成素数时的效率。

步骤：

实现埃拉托斯特尼筛法

实现试除法

比较两种方法生成前 10000 个素数的时间

分析空间复杂度和时间复杂度

预期结果：筛法在生成大量素数时远快于试除法。

实验二：RSA 加密的实际应用

目标：实现完整的 RSA 加密系统，包括密钥生成、加密、解密。

步骤：

实现大素数生成

实现密钥生成

实现加密和解密

测试不同长度的密钥对性能的影响

思考题：

为什么实际 RSA 使用 2048 位或更长的密钥？
如何选择安全的素数 p 和 q？

七、本章小结

本章介绍了整除性、素数、同余等数论基础概念。

关键公式：

贝祖等式：ax + by = gcd(a, b)
欧拉函数：$\phi(n) = n \prod_{p|n} (1 - 1/p)$
费马小定理：$a^{p-1} \equiv 1 \pmod{p}$（p 是素数）
欧拉定理：$a^{\phi(m)} \equiv 1 \pmod{m}$（gcd(a,m)=1）

核心算法：

欧几里得算法：O(log n) 计算 gcd

扩展欧几里得算法：求解贝祖等式

快速幂取模：O(log n) 计算 aⁿ mod m

试除法：O(√n) 素因数分解

重要定理：

算术基本定理：素因数分解的唯一性
素数有无穷多个
中国剩余定理（将在后续习题中探讨）

八、习题

基础题

习题 3.1：计算 gcd(1071, 462) 并找到 x, y 使得 1071x + 462y = gcd。

习题 3.2：对 n = 84 进行素因数分解。

习题 3.3：计算 7¹⁰⁰ mod 13。

习题 3.4：计算 φ(36)。

进阶题

习题 3.5：[ME] 证明：如果 a ≡ b (mod m) 且 c ≡ d (mod m)，则 ac ≡ bd (mod m)。

习题 3.6：[ME] 使用中国剩余定理求解：x ≡ 2 (mod 3)，x ≡ 3 (mod 5)，x ≡ 2 (mod 7)。

习题 3.7：证明威尔逊定理：p 是素数当且仅当 (p-1)! ≡ -1 (mod p)。

挑战题

习题 3.8：[HM25] 实现 Miller-Rabin 素性测试算法，并测试其准确性。

习题 3.9：[HM30] 研究 Pollard's rho 因数分解算法：

(a) 解释算法原理
(b) 实现算法
(c) 分析期望时间复杂度

习题 3.10：[HM40] 证明二次互反律：对于不同的奇素数 p, q，有 $(\frac{p}{q})(\frac{q}{p}) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}$，其中 $(\frac{a}{p})$ 是勒让德符号。

本章完

第3章 整除性 (Divisibility)

一、导读

3.1 本章学习目标

3.2 为什么本章如此重要

3.3 核心问题引导

二、核心概念详解

3.1 整除关系与基本性质

定义

基本性质

带余除法

3.2 最大公约数与欧几里得算法

最大公约数的定义

欧几里得算法

时间复杂度分析

代码实现

3.3 贝祖等式与扩展欧几里得算法

贝祖等式

扩展欧几里得算法

应用：模逆元

3.4 素数与算术基本定理

素数的定义

素数的无穷性

算术基本定理

素因数分解算法

3.5 同余运算

同余的定义

基本性质

应用：快速幂取模

3.6 费马小定理与欧拉定理

费马小定理

欧拉函数

欧拉定理

三、程序员的视角

3.1 在算法分析中的应用

哈希函数

随机数生成

循环检测

3.2 常见陷阱与误区

陷阱 1：负数的模运算

陷阱 2：整数溢出

陷阱 3：误用费马小定理

3.3 与其他层级的联系

四、代码实战

4.1 示例一：完整的数论工具库

4.2 示例二：RSA 加密演示

五、深入思考

5.1 历史背景

5.2 未解决的问题

5.3 延伸阅读

六、实验笔记

实验一：素数筛法的性能比较

实验二：RSA 加密的实际应用

七、本章小结

八、习题

基础题

进阶题

挑战题

第3章整除性 (Divisibility)