Skip to content

数论进阶

同余、扩展欧几里得、逆元、费马小定理与中国剩余定理。

Updated View as Markdown

在初等数论里,加减乘除都还算听话。一到除法,同余式就不成立了:6 \equiv 0 \pmod 3,但两边同时除以 2 得到 3 \equiv 0 \pmod 3,已经不是同余了。想让除法也有意义,就要引入逆元。

这一章讲的就是模运算下的「除法」,以及围绕它建立起来的几个经典定理。它们是 CSP-S 提高级的正式考点。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
NOI 提高级 2.5.2 初等数论:同余式、欧拉定理与欧拉函数、费马小定理、威尔逊定理、裴蜀定理、模运算意义下的逆元、扩展欧几里得算法、中国剩余定理 全章

同余式

若 a - b 能被 m 整除,就说 a 与 b 模 m 同余,记作:

a \equiv b \pmod m

同余式可以像等式一样做加、减、乘:若 a \equiv b、c \equiv d \pmod m,则

  • a + c \equiv b + d \pmod m
  • a - c \equiv b - d \pmod m
  • a \times c \equiv b \times d \pmod m

唯独除法不能随便用。a \times c \equiv b \times c \pmod m 推不出 a \equiv b \pmod m,除非 c 与 m 互质。要处理除法,就得请出逆元。

裴蜀定理与扩展欧几里得

裴蜀定理:对于不全为零的整数 a、b,存在整数 x、y 使得

ax + by = \gcd(a, b)

也就是说,\gcd(a, b) 是 a 和 b 能线性组合出来的最小正整数。

扩展欧几里得算法不仅求出 \gcd,还顺带求出满足上式的 x 和 y。做法是在辗转相除的回溯过程中,把系数一层层推回去。

// 求 ax + by = gcd(a, b) 的一组解,返回 gcd
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x; // 把上一层的系数调整回来
    return d;
}

推导思路是:设 a % b = a - \lfloor a/b \rfloor \cdot b,代入下一层的等式,整理后就能得到当前层的 x、y。递归到 b = 0 时,ax = a 的解是 x = 1、y = 0,往回一路上推即可。

模意义下的逆元

如果存在整数 x 使得

a \times x \equiv 1 \pmod m

就称 x 是 a 在模 m 意义下的逆元,记作 a^{-1}。它相当于模意义下的倒数:除以 a 就是乘以 a^{-1}。

逆元存在的充要条件是 \gcd(a, m) = 1。不互质时逆元不存在,除法也就没法进行。

用扩展欧几里得求逆元

要求 a^{-1} \pmod m,等价于解 ax + my = 1。这正是扩展欧几里得的任务。

long long inv(long long a, long long m) {
    long long x, y;
    exgcd(a, m, x, y);         // 解出 ax + my = gcd(a, m)
    return (x % m + m) % m;    // 化成 [0, m) 范围内的正整数
}

这个方法对任意满足 \gcd(a, m) = 1 的 m 都适用。

用费马小定理求逆元

费马小定理:若 p 是质数,且 a 不是 p 的倍数,则

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

两边同时乘 a^{-1},得到

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

所以在模质数 p 的情况下,a 的逆元就是 a^{p-2},用快速幂 O(\log p) 就能求出来。

const long long MOD = 1000000007; // 一个大质数

long long inv(long long a) {
    return fastPow(a, MOD - 2, MOD);
}

题面里常见的 10^9+7 和 998244353 都是质数,用这个式子最方便。

欧拉定理与欧拉函数

费马小定理是欧拉定理的特例。欧拉函数 \varphi(n) 表示 1 到 n 中与 n 互质的数的个数。

若 \gcd(a, n) = 1,则

a^{\varphi(n)} \equiv 1 \pmod n

欧拉函数的计算式来自唯一分解定理。若 n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k},则

\varphi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right)

单个数的欧拉函数可以在质因数分解的过程中顺手算出来:

long long phi(long long n) {
    long long res = n;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1); // 先除后乘,避免溢出
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

几个常用值:\varphi(p) = p - 1(p 为质数),\varphi(1) = 1,\varphi(p^k) = p^k - p^{k-1}。

中国剩余定理

中国剩余定理(CRT)解决的是「一个数被几个数除的余数都已知,求这个数」:

\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\vdots \\
x \equiv a_k \pmod{m_k}
\end{cases}

当模数 m_1, m_2, \dots, m_k 两两互质时,在模 M = m_1 m_2 \cdots m_k 的意义下有唯一解。

构造方法:令 M_i = M / m_i,求出 M_i 在模 m_i 下的逆元 t_i,则

x = \sum_{i=1}^{k} a_i M_i t_i \pmod M

记住适用条件就行:模数必须两两互质。不互质时要用扩展中国剩余定理(EXCRT),属于更进阶的内容。

威尔逊定理

p 是质数当且仅当

(p-1)! \equiv -1 \pmod p

这个定理把质数判断和阶乘联系了起来,考试里多以「下列哪个式子等价于 p 是质数」的形式出现。实际编程中很少用它判断质数,因为算阶乘比试除慢得多。

组合数取模

初等数论里求 C_n^m 用的是杨辉三角递推,O(n^2),n 到 10^3 还行,再大就顶不住。模数为质数 p 时,可以用阶乘和逆元把单次查询降到 O(1)(预处理 O(n))。

C_n^m = \frac{n!}{m!(n-m)!} = n! \times (m!)^{-1} \times ((n-m)!)^{-1}

const long long MOD = 1000000007;
const int MAXN = 1000005;
long long fact[MAXN], invFact[MAXN];

void init() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[MAXN - 1] = fastPow(fact[MAXN - 1], MOD - 2, MOD); // 一次快速幂
    for (int i = MAXN - 2; i >= 0; i--) invFact[i] = invFact[i+1] * (i + 1) % MOD;
}

long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invFact[m] % MOD * invFact[n-m] % MOD;
}

只需求出最大的那个阶乘的逆元,其余逆元可以倒着递推出来,省下大量快速幂。

初赛选择题精选

数论进阶是 CSP-S 笔试的常客。下面 8 道题按考点分类编写,覆盖逆元、费马小定理、欧拉函数与欧拉定理、中国剩余定理、威尔逊定理、裴蜀定理与逆元唯一性这些高频考点。先自己做,再看答案与解析。

题 1(逆元存在性)

下列哪个数在模 12 的意义下存在乘法逆元?

A. 4 B. 6 C. 8 D. 5

答案:D

解析:逆元存在的充要条件是与模数互质。\gcd(5, 12) = 1,而 4、6、8 与 12 的最大公约数分别是 4、6、4,都不互质,逆元不存在。

题 2(费马小定理求逆元)

3 在模 7 意义下的逆元是多少?

A. 3 B. 4 C. 5 D. 6

答案:C

解析:模数 7 是质数,用费马小定理:3^{-1} \equiv 3^{7-2} = 3^5 = 243 \equiv 5 \pmod 7。验证:3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 \pmod 7,正确。

题 3(欧拉函数)

欧拉函数 \varphi(12) 的值是( )。

A. 4 B. 6 C. 8 D. 11

答案:A

解析:12 = 2^2 \times 3,代入公式:\varphi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 4。与 12 互质的是 1、5、7、11,正好 4 个。

题 4(中国剩余定理)

满足 x \equiv 2 \pmod 3 且 x \equiv 3 \pmod 5 的最小正整数 x 是( )。

A. 8 B. 13 C. 23 D. 5

答案:A

解析:用 CRT 的构造公式(M = 15)得 x = 8;也可以从小到大验证:8 除以 3 余 2、除以 5 余 3,是最小的解。通解是 8 + 15k。

题 5(威尔逊定理)

由威尔逊定理,6! \bmod 7 的值是( )。

A. 0 B. 1 C. 6 D. 5

答案:C

解析:7 是质数,威尔逊定理给出 (7-1)! = 6! \equiv -1 \pmod 7,而 -1 \bmod 7 = 6。直接算验证:720 = 102 \times 7 + 6,余数正是 6。

题 6(欧拉定理)

若 \gcd(a, n) = 1,则 a^{\varphi(n)} \bmod n 等于( )。

A. 0 B. 1 C. a D. \varphi(n)

答案:B

解析:这正是欧拉定理的内容:若 \gcd(a, n) = 1,则 a^{\varphi(n)} \equiv 1 \pmod n。

特例:当 n 是质数 p 时,\varphi(p) = p - 1,欧拉定理退化成费马小定理 a^{p-1} \equiv 1 \pmod p。费马小定理是欧拉定理的特例,这个包含关系选择题常考。

题 7(扩展欧几里得)

方程 6x + 4y = 1 的整数解的情况是( )。

A. 有无穷多组解 B. 有唯一解 C. 无解 D. 恰有两组解

答案:C

解析:由裴蜀定理,方程 ax + by = c 有整数解的充要条件是 \gcd(a, b) \mid c。

这里 \gcd(6, 4) = 2,而 2 \nmid 1,所以无解。这是裴蜀定理最直接的考法:先算 gcd,再看它能不能整除右边的常数。

反过来,如果 \gcd(a,b) \mid c 成立,那么解有无穷多组(通解是特解加上 (b/g, -a/g) 的整数倍)。

题 8(逆元的唯一性)

在模 7 意义下,3 的逆元是( )。

A. 2 B. 3 C. 5 D. 6

答案:C

解析:逆元 x 要满足 3x \equiv 1 \pmod 7。逐个验证:

  • 3 \times 2 = 6 \equiv 6
  • 3 \times 3 = 9 \equiv 2
  • 3 \times 5 = 15 \equiv 1 ✓
  • 3 \times 6 = 18 \equiv 4

所以逆元是 5。

性质:模 p(p 为质数)意义下,除 0 以外每个数都有唯一的逆元,且逆元的逆元是它自己。这里 5 的逆元也是 3(5 \times 3 = 15 \equiv 1),可以验证这个对称性。

练习

练习 1:用扩展欧几里得求逆元

题目描述

给定 a 和 m(保证 \gcd(a, m) = 1),求 a 在模 m 意义下的逆元(0 到 m - 1 之间的那个)。

输入格式

一行两个整数 a 和 m。

输出格式

输出一个整数,表示 a 模 m 的逆元。

数据范围

  • 1 \le a < m \le 10^5,保证 \gcd(a, m) = 1。

输入输出样例

输入

3 10

输出

7

说明:3 \times 7 = 21 \equiv 1 \pmod{10}。

题目分析

正文扩展欧几里得模板的直接落地:解 ax + my = \gcd(a, m) = 1,把 x 调整到 [0, m) 区间就是逆元。

参考代码

练习 2:欧拉函数

题目描述

给定一个正整数 n,求 \varphi(n) 的值。

输入格式

一个整数 n。

输出格式

输出一个整数,表示 \varphi(n)。

数据范围

  • 1 \le n \le 10^9。

输入输出样例

输入

12

输出

4

题目分析

正文欧拉函数代码的直接落地:质因数分解过程中,每找到一个质因数 p,就把结果乘上 (1 - 1/p),代码里写成先除后乘的 res = res / p * (p - 1)。复杂度 O(\sqrt n),n = 10^9 时约 3 万次运算。

参考代码

练习 3(挑战):同余方程组

题目描述

求最小的非负整数 x,满足:

x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2}

给定两组同余条件,求最小的非负整数解。

输入格式

一行四个整数 a_1、m_1、a_2、m_2。

输出格式

输出一个整数,表示最小的非负解。

数据范围

  • 0 \le a_i < m_i \le 10^5,m_1 与 m_2 互质。

输入输出样例

输入

2 3 3 5

输出

8

题目分析

这是两个方程的中国剩余定理,按正文公式实现即可:

  1. M = m_1 \times m_2,M_1 = m_2,M_2 = m_1;
  2. 用扩展欧几里得求 M_1 模 m_1 的逆元 t_1、M_2 模 m_2 的逆元 t_2;
  3. 答案是 x = (a_1 M_1 t_1 + a_2 M_2 t_2) \bmod M。

验证样例:x = 2 \times 5 \times 2 + 3 \times 3 \times 2 = 38 \equiv 8 \pmod{15},而 8 除以 3 余 2、除以 5 余 3,正确。

限制 m_i \le 10^5 是为了让所有中间乘积都装进 long long;模数更大的场合要用 __int128 或专门的乘法取模技巧。

参考代码

常见易错点

  • 忘记检查 \gcd(a, m) = 1。不互质时逆元不存在,硬套公式会算出一个没有意义的数。
  • 扩展欧几里得递归时 x、y 的传递顺序容易写反,写完后代回去验证 ax + by = \gcd。
  • 求出的逆元可能是负数,要化成 [0, m) 范围:(x % m + m) % m。
  • 费马小定理的指数是 p-2,不是 p-1。a^{p-1} \equiv 1,a^{p-2} \equiv a^{-1}。
  • 中国剩余定理要求模数两两互质,条件不满足时不能直接套公式。
  • 组合数取模的前提是模数为质数且 n < p。n \ge p 时阶乘会变成 0,要用卢卡斯定理。
  • 会用扩展欧几里得求逆元,模数为质数时也可以直接用 a^{p-2}。
  • 会计算欧拉函数 \varphi(n),会解模数互质的同余方程组(CRT 构造法)。

小结

  • 同余式能加减乘,不能随便除;想让除法成立就要用逆元。
  • 裴蜀定理说 ax + by = \gcd(a, b) 一定有整数解,扩展欧几里得负责找出来。
  • 逆元存在当且仅当 \gcd(a, m) = 1,用扩展欧几里得求;模数为质数时也可以直接用 a^{p-2}。
  • 欧拉定理 a^{\varphi(n)} \equiv 1 \pmod n 是费马小定理的推广。
  • 中国剩余定理处理模数两两互质的同余方程组。
  • 组合数取模用阶乘加逆元,一次预处理,O(1) 查询。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close