---
title: "数论进阶"
description: "同余、扩展欧几里得、逆元、费马小定理与中国剩余定理。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 数论进阶

![](https://img.dailyup.xyz/optimized/8207672303825-ed8f6027-9c7c-447f-872d-d139fdc5444e.jpg)

在初等数论里，加减乘除都还算听话。一到除法，同余式就不成立了：$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$。做法是在辗转相除的回溯过程中，把系数一层层推回去。

```cpp
// 求 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$。这正是扩展欧几里得的任务。

```cpp
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)$ 就能求出来。

```cpp
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)$$

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

```cpp
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}$$

```cpp
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)$ 区间就是逆元。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/number-theory-advanced/index.md

### 练习 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 万次运算。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/number-theory-advanced/index.md

### 练习 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` 或专门的乘法取模技巧。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/maths/number-theory-advanced/index.md

## 常见易错点

- 忘记检查 $\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)$ 查询。

Source: https://cppguide.xyz/maths/number-theory-advanced/index.mdx
