第41章 初等数论

初等数论是研究整数性质的数学分支，其内容在程序设计中有着广泛应用，如密码学、算法优化、数据校验等。本章对应 GESP C++ 五级知识块 1：初等数论，覆盖大纲要求的全部考点：素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性，以及欧几里得算法、唯一分解定理、埃氏筛法与线性筛法。

41.1 基本概念与性质

41.1.1 整除

定义：设 $a$、$b$ 为整数，且 $b \neq 0$，若存在整数 $k$ 使得 $a = b \times k$，则称 $b$ 整除 $a$（或 $a$ 能被 $b$ 整除），记作 $b \mid a$。此时 $b$ 是 $a$ 的约数（因数），$a$ 是 $b$ 的倍数。

性质：

1. 若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$（传递性）。
2. 若 $a \mid b$ 且 $a \mid c$，则对任意整数 $m$、$n$，有 $a \mid (m \times b + n \times c)$。
3. 若 $a \mid b$ 且 $b \mid a$，则 $a = \pm b$。
4. 若 $b \mid a$，则 $b \mid a \times k$（$k$ 为任意整数）。

记忆要点：整除是"无余数的倍数关系"，是约数、倍数、素数、合数等概念的共同基础。

41.1.2 素数与合数

• 素数（质数）：大于 1 的整数，若除了 1 和自身外没有其他正约数，则称为素数（如 2、3、5、7）。
• 合数：大于 1 的非素数整数（如 4、6、8、9）。
• 特殊规定：1 既不是素数也不是合数。

性质：

1. 大于 2 的素数都是奇数。
2. 任何大于 1 的整数都能分解为素数的乘积（算术基本定理）。

41.1.3 最大公约数与最小公倍数

最大公约数（GCD）：设 $a$、$b$ 为整数，若 $d$ 是同时整除 $a$ 和 $b$ 的最大正整数，则 $d$ 称为 $a$ 和 $b$ 的最大公约数，记作 $\gcd(a,b)$。

• 性质：$\gcd(a,b) = \gcd(b, a \bmod b)$（辗转相除法的理论基础）。
• 互质定义：若 $\gcd(a, b) = 1$，则称 $a$ 和 $b$ 互质（互素）。

最小公倍数（LCM）：设 $a$、$b$ 为正整数，若 $m$ 是同时是 $a$ 和 $b$ 的最小正倍数，则 $m$ 称为 $a$ 和 $b$ 的最小公倍数，记作 $\operatorname{lcm}(a, b)$。

• 性质：对任意正整数 $a$、$b$，有 $a \times b = \gcd(a, b) \times \operatorname{lcm}(a, b)$。

41.1.4 奇偶性

• 偶数：能被 2 整除的整数（$n \bmod 2 = 0$）；奇数：被 2 除余 1 的整数（$n \bmod 2 = 1$）。
• 运算规律（模 2 下恒成立）：
  • 偶 ± 偶 = 偶，奇 ± 奇 = 偶，偶 ± 奇 = 奇；
  • 偶 × 任意 = 偶，奇 × 奇 = 奇。
• 考试常见用途：判断整除性、构造配对、二分答案中的步长奇偶讨论、异或性质（$a \oplus a = 0$，奇偶计数）等。

41.1.5 约数与倍数

• $d$ 是 $n$ 的约数 ⇔ $n \bmod d = 0$。
• 约数总是成对出现：若 $d \mid n$，则 $\frac{n}{d}$ 也是约数，因此只需枚举到 $\sqrt{n}$ 即可找出所有约数。
• 一个数的约数个数、约数之和可通过质因数分解快速求得（见 41.4.2）。

41.2 核心算法与实现

41.2.1 辗转相除法（欧几里得算法）求 GCD

辗转相除法不断用"余数"替换"较大数"，直到余数为 0，最后一个非零余数就是最大公约数。

// 迭代版：求 a 和 b 的最大公约数（a、b 为非负整数，且不同时为 0）
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 递归版本
int gcdRecursive(int a, int b) {
    if (b == 0) return a;
    return gcdRecursive(b, a % b);
}

复杂度：每次取模至少让数值折半，时间复杂度 $O(\log(\min(a,b)))$。

41.2.2 最小公倍数（LCM）的计算

// 求 a 和 b 的最小公倍数（a、b 为正整数）
int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 先除后乘，避免 a*b 溢出
}

41.2.3 素数判定（试除法）

判断一个数 $n$ 是否为素数，只需检查 $2 \sim \lfloor\sqrt{n}\rfloor$ 之间的整数能否整除 $n$。

// 判断 n 是否为素数（n >= 2）
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false; // 偶数一定不是素数
    for (int i = 3; i * i <= n; i += 2) { // 只检查奇数
        if (n % i == 0) return false;
    }
    return true;
}

41.2.4 埃氏筛法（筛选素数）

埃氏筛法是筛选 $1 \sim n$ 所有素数的算法，时间复杂度 $O(n \log \log n)$。

// 返回标记数组，isPrime[i] 为 true 代表 i 是素数
vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    return isPrime;
}

41.2.5 线性筛法（欧拉筛法）

线性筛时间复杂度 $O(n)$，每个合数只会被其最小质因数标记一次，无重复操作。

// 线性筛，返回 1~n 内所有素数列表
vector<int> linearSieve(int n) {
    vector<bool> isComposite(n + 1, false);
    vector<int> primes; // 存储素数
    for (int i = 2; i <= n; ++i) {
        if (!isComposite[i]) {
            primes.push_back(i); // i 是素数
        }
        // 用已找到的素数筛除合数
        for (int p : primes) {
            if (i * p > n) break;
            isComposite[i * p] = true;
            if (i % p == 0) break; // p 是 i 最小质因数，停止循环
        }
    }
    return primes;
}

优势：

1. 不会重复标记合数（如 6 仅被 2 标记，不会再被 3 标记），大数据效率更高；
2. 可同步记录每个数字最小质因数，方便质因数分解。

41.2.6 分解质因数

算术基本定理：任意大于 1 整数可唯一分解为素数乘积。

#include <map>
// 将 n 分解，返回 {质因数: 指数} 映射
map<int, int> primeFactorization(int n) {
    map<int, int> factors;
    // 处理 2 的倍数
    while (n % 2 == 0) {
        factors[2]++;
        n /= 2;
    }
    // 处理奇数因子
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors[i]++;
            n /= i;
        }
    }
    // 剩余大于 2 的素数
    if (n > 2) {
        factors[n]++;
    }
    return factors;
}

41.3 同余与模运算

41.3.1 同余定义

若整数 $a$ 和 $b$ 除以 $m$ 余数相同，则称 $a$ 与 $b$ 模 $m$ 同余，记作 $a \equiv b \pmod{m}$，等价于 $m \mid (a - b)$。

41.3.2 模运算性质

1. $(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m$
2. $(a - b) \bmod m = \big((a \bmod m) - (b \bmod m) + m\big) \bmod m$（加 $m$ 避免负数）
3. $(a \times b) \bmod m = \big((a \bmod m) \times (b \bmod m)\big) \bmod m$

快速幂（模幂运算）

高效计算 $a^b \bmod m$，时间 $O(\log b)$：

long long fastPower(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        b /= 2;
    }
    return result;
}

41.3.3 同余方程简介

最简同余方程 $a x \equiv b \pmod{m}$，有解充要条件：$\gcd(a, m) \mid b$。 若 $\gcd(a, m) = 1$，存在模逆元 $a^{\phi(m)-1} \pmod{m}$。

41.4 常用数论定理

41.4.1 算术基本定理

任意大于 1 整数 $n$ 可唯一分解：

其中 $p_1 < p_2 < \dots < p_m$ 为素数，$k_i$ 为对应指数。

41.4.2 唯一分解定理推论

设 $a = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$，$b = p_1^{b_1} p_2^{b_2} \dots p_k^{b_k}$，则

• 因数个数公式：若 $n$ 分解后指数为 $k_1, k_2, \dots, k_m$，则因数总数为 $(k_1+1)(k_2+1)\dots(k_m+1)$。
• 示例：$12 = 2^2 \times 3^1$，因数个数 $(2+1)(1+1) = 6$。

41.4.3 欧拉定理

若 $\gcd(a, m) = 1$，则 $a^{\phi(m)} \equiv 1 \pmod{m}$，$\phi(m)$ 代表 $1 \sim m$ 中和 $m$ 互质数字总数。

41.4.4 费马小定理

若 $p$ 是素数，且 $a$ 不被 $p$ 整除，则 $a^{p-1} \equiv 1 \pmod{p}$。 费马小定理是欧拉定理 $m$ 为素数时的特例（$\phi(p) = p-1$）。

41.5 注意事项

1. 数据溢出：大数运算使用 long long 替代 int。
2. 边界：0 不能作为除数；1 非素数；2 是唯一偶素数。
3. 模负数：C++ 中负数取模结果为负，需 (x % m + m) % m 转正。
4. 筛法选择：小规模判断素数用试除，大范围批量筛素数用线性筛。
5. 奇偶性：涉及整除、配对、异或计数时优先考虑奇偶性简化。

41.6 选择题练习

1. 下列关于素数的说法，正确的是： A. 1 是素数 B. 大于 2 的素数都是奇数 C. 所有偶数都是合数 D. 素数只有有限个

   查看答案

   答案：B。1 既不是素数也不是合数（A 错）；2 是偶数但不是合数（C 错）；素数有无穷多个（D 错）；除 2 外素数均为奇数，故 B 正确。

2. 用辗转相除法求 $\gcd(48, 18)$，最后一个非零余数是： A. 2 B. 3 C. 6 D. 12

   查看答案

   答案：C。$48 = 18 \times 2 + 12$，$18 = 12 \times 1 + 6$，$12 = 6 \times 2 + 0$，最后一个非零余数为 6，故 $\gcd(48,18)=6$。

3. 已知 $\gcd(a,b)=6$ 且 $a \times b = 720$，则 $\operatorname{lcm}(a,b)$ 等于： A. 120 B. 60 C. 720 D. 4320

   查看答案

   答案：A。由 $a \times b = \gcd(a,b) \times \operatorname{lcm}(a,b)$，得 $720 = 6 \times \operatorname{lcm}(a,b)$，所以 $\operatorname{lcm}(a,b) = 120$。

4. 在 C++ 中，表达式 (-7) % 3 的结果最接近于以下哪个"转正"处理？ A. 2 B. -1 C. 1 D. -2

   查看答案

   答案：B。C++ 中 (-7) % 3 的结果为 -1（符号与被除数相同）。要得到正余数 2，需写成 (-7 % 3 + 3) % 3。本题问"表达式本身的结果"，故选 B。

5. 用试除法判断 $n$ 是否为素数，只需检查到： A. $n/2$ B. $\lfloor\sqrt{n}\rfloor$ C. $n-1$ D. $\lfloor n/3 \rfloor$

   查看答案

   答案：B。若 $n$ 有大于 $\sqrt{n}$ 的因子，则其对应配对因子必小于 $\sqrt{n}$，故只需检查到 $\lfloor\sqrt{n}\rfloor$ 即可。