同余、扩展欧几里得与数论四大定理

本文部分参考李煜东《算法竞赛进阶指南》

快速过证明过程，戳这里。

想自己思考，戳这里。

更新记录：

• 2026/07/11：同余部分基本完工

---

概述

数论中通常有四大定理：威尔逊定理、欧拉定理、中国剩余定理、费马小定理。但威尔逊定理涉及阶乘运算，其数值增长极快，在 OI 领域中应用较少，故本文暂不介绍。中国剩余定理涉及同余方程组的求解，相关内容请参见这篇文章

定义

同余
若整数 $a$ 与整数 $b$ 除以正整数 $m$ 的余数相等，则称 $a,b$ 模 $m$ 同余，记为 $a\equiv b(\mathrm{mod}m)$。

同余类
对于任意 $a\in [0,m-1]$，集合 { a + k m ∣ k ∈ Z } \{a + km \mid k \in \mathbb{Z}\} {a+km∣k∈Z} 中的所有数模 $m$ 同余，余数均为 $a$。该集合称为模 $m$ 的一个同余类，简记为 $\bar{a}$。

剩余系
模 $m$ 的同余类共有 $m$ 个，分别为 $\bar{0},\bar{1},\bar{2},\dots ,\overline{m-1}$。它们构成模 $m$ 的完全剩余系。

$1\sim m$ 中与 $m$ 互质的数所代表的同余类共有 $\phi (m)$ 个，它们构成模 $m$ 的简化剩余系。

---

这一部分内容十分重要，请大家务必深入理解。

一、同余

前置结论： 若 $n\mid (a-b)$，则 $a\equiv b(\mathrm{mod}n)$。

证明
设 $a=n{k}_1+c$，$b=n{k}_2+d$，则
$$a-b=n(k_1-k_2)+(c-d)$$
若 $n\mid (a-b)$，则必须有 $c-d=0$，即 $c=d$。因此 $a$ 与 $b$ 除以 $n$ 的余数相同，故 $a\equiv b(\mathrm{mod}n)$。

证毕。

同余的基本性质

1. 自反性

$a\equiv a(\mathrm{mod}n)$

2. 对称性

若 $a\equiv b(\mathrm{mod}n)$，则 $b\equiv a(\mathrm{mod}n)$

3. 传递性

若 $a\equiv b(\mathrm{mod}n)$，$b\equiv c(\mathrm{mod}n)$，则 $a\equiv c(\mathrm{mod}n)$

证明
设 $a-b=n{k}_1$，$b-c=n{k}_2$，则
$$a-c=n(k_1+k_2)$$
因此 $a\equiv c(\mathrm{mod}n)$。

证毕。

4. 同加性

若 $a\equiv b(\mathrm{mod}n)$，则 $a+c\equiv b+c(\mathrm{mod}n)$

证明
设 $a-b=nk$，则 $(a+c)-(b+c)=nk$，故 $a+c\equiv b+c(\mathrm{mod}n)$。

证毕。

5. 同乘性

若 $a\equiv b(\mathrm{mod}n)$，则 $ac\equiv bc(\mathrm{mod}n)$

证明
设 $a-b=nk$，则 $ac-bc=nkc$，故 $ac\equiv bc(\mathrm{mod}n)$。

证毕。

若 $a\equiv b(\mathrm{mod}n)$，$c\equiv d(\mathrm{mod}n)$，则 $ac\equiv bd(\mathrm{mod}n)$

证明
设 $a-b=n{k}_1$，$c-d=n{k}_2$，则
$$ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)=n(k_{1}c+k_{2}b)$$
因此 $ac\equiv bd(\mathrm{mod}n)$。

证毕。

6. 同幂性

若 $a\equiv b(\mathrm{mod}n)$，则 $a^k\equiv b^k(\mathrm{mod}n)$（$k$ 为正整数）

证明
设 $a-b=nk$，由恒等式
$$a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots +a{b}^{k-2}+b^{k-1})$$
可得 $a^k-b^k=nk(\cdots )$，故 $a^k\equiv b^k(\mathrm{mod}n)$。

证毕。

---

二、扩展欧几里得算法

前置知识：欧几里得算法（见链接文章末尾部分）

1. Bézout 定理（裴蜀定理）

对于任意整数 $a,b$，存在一对整数 $x,y$，满足
$$ax+by=\gcd (a,b)$$

证明
在欧几里得算法的最后一步，即 $b=0$ 时，显然存在 $x=1,y=0$，使得
$$a\cdot 1+0\cdot 0=\gcd (a,0)$$

若 $b>0$，则 $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$。假设存在整数 $x,y$ 满足
$$b\cdot x+(a\mathrm{mod}b)\cdot y=\gcd (b,a\mathrm{mod}b)$$
因为 $a\mathrm{mod}b=a-b\lfloor a/b\rfloor$，代入得
$$bx+(a-b\lfloor a/b\rfloor )y=ay+b(x-\lfloor a/b\rfloor y)$$
令 $x^{\prime }=y$，$y^{\prime }=x-\lfloor a/b\rfloor y$，则
$$a{x}^{\prime }+b{y}^{\prime }=\gcd (a,b)$$
对欧几里得算法的递归过程应用数学归纳法，可知 Bézout 定理成立。

证毕。

Bézout 定理的上述证明同时给出了整数 $x$ 和 $y$ 的计算方法，这种方法称为扩展欧几里得算法。

代码实现

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int z = x;
    x = y;
    y = z - y * (a / b);
    return d;
}

扩展欧几里得算法求线性不定方程

对于线性不定方程 $ax+by=c$，由 Bézout 定理可知，方程存在整数解当且仅当 $\gcd (a,b)\mid c$。否则方程无整数解。

先用扩展欧几里得算法求得 $ax+by=\gcd (a,b)$ 的一组特解 $x_0,y_0$，再乘上系数 $\frac{c}{\gcd (a,b)}$，即可得到原方程的一组特解：
$$\{\begin{array}{l}x=\frac{c}{\gcd (a,b)}\cdot x_0\\ y=\frac{c}{\gcd (a,b)}\cdot y_0\end{array}$$

原方程的通解为：
$$x=\frac{c}{\gcd (a,b)}{x}_0+k\cdot \frac{b}{\gcd (a,b)},y=\frac{c}{\gcd (a,b)}{y}_0-k\cdot \frac{a}{\gcd (a,b)}(k\in \mathbb{Z})$$

代码实现

int line_equation(int a, int b, int c, int &x, int &y) {
    int d = exgcd(a, b, x, y);
    if (c % d) return 0;            // 方程无解
    int k = c / d;
    x = x * k;
    y = y * k;                      // 求得一组特解，其余解可由通解公式得到
    return 1;
}

---

2. 乘法逆元

若整数 $b,m$ 互质，且 $b\mid a$，则存在一个整数 $x$，使得
$$\frac{a}{b}\equiv a\cdot x(\mathrm{mod}m)$$
称 $x$ 为 $b$ 在模 $m$ 意义下的乘法逆元，记为 $b^{-1}(\mathrm{mod}m)$。

由上式可知：
$$b\cdot b^{-1}\equiv 1(\mathrm{mod}m)$$

如果模数 $m$ 是质数（此时常用符号 $p$ 表示），且 $b<p$，根据费马小定理，$b^{p-1}\equiv 1(\mathrm{mod}p)$，即 $b\cdot b^{p-2}\equiv 1(\mathrm{mod}p)$。因此，当模数 $p$ 为质数时，$b^{p-2}$ 即为 $b$ 的乘法逆元。

如果只保证 $b$ 与 $m$ 互质，则乘法逆元可通过求解同余方程 $b\cdot x\equiv 1(\mathrm{mod}m)$ 得到（利用扩展欧几里得算法即可）。下一节我们将正式介绍线性同余方程及其求解方法。

有了乘法逆元，在计数类问题中遇到形如 $a/b$ 的除法算式时，可以先将 $a,b$ 分别对模数 $p$ 取模，再计算 $a\cdot b^{-1}\mathrm{mod}p$ 作为结果。当然，前提是必须保证 $b$ 与 $p$ 互质（当 $p$ 是质数时，等价于 $b$ 不是 $p$ 的倍数）。

直接计算 $a/b\mathrm{mod}p$ 时，若 $a$、$b$ 过大，直接相除可能溢出精度，且除法不满足模运算的分配律。因此可将其转化为乘法逆元来求：$a\cdot b^{-1}\mathrm{mod}p$。

代码实现

// 利用费马小定理求 b 在模 m 下的逆元：b^(m-2) % m
int quick_pow(int b, int m) {
    int r = 1, base = b, exp = m - 2;
    while (exp) {
        if (exp & 1) r = r * base % m;
        base = base * base % m;
        exp >>= 1;
    }
    return r % m;
}

---

三、数论四大定理（中的两个）

1. 欧拉定理

若正整数 $a$ 与 $n$ 互质，则
$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

证明
设 $n$ 的简化剩余系为 { a 1 ‾ , a 2 ‾ , … , a φ ( n ) ‾ } \{\overline{a_1}, \overline{a_2}, \dots, \overline{a_{\varphi(n)}}\} {a1​​,a2​​,…,aφ(n)​​}。

对任意 $a_i,a_j$，若 $a\cdot a_i\equiv a\cdot a_j(\mathrm{mod}n)$，则 $a(a_i-a_j)\equiv 0(\mathrm{mod}n)$。因为 $\gcd (a,n)=1$，所以 $a_i-a_j\equiv 0(\mathrm{mod}n)$，即 $a_i\equiv a_j$。故当 $a_i\ne a_j$ 时，$a{a}_i$ 与 $a{a}_j$ 也属于不同的同余类。

又因为简化剩余系关于模 $n$ 乘法封闭，所以 $\overline{a{a}_i}$ 仍在简化剩余系中。因此，集合
{ a 1 ‾ , a 2 ‾ , … , a φ ( n ) ‾ } \{\overline{a_1}, \overline{a_2}, \dots, \overline{a_{\varphi(n)}}\} {a1​​,a2​​,…,aφ(n)​​}
与集合
{ a a 1 ‾ , a a 2 ‾ , … , a a φ ( n ) ‾ } \{\overline{a a_1}, \overline{a a_2}, \dots, \overline{a a_{\varphi(n)}}\} {aa1​​,aa2​​,…,aaφ(n)​​}
都表示 $n$ 的简化剩余系（仅排列顺序可能不同）。

将两个集合中的所有元素分别相乘：
$$a^{\phi (n)}\cdot a_1{a}_2\cdots a_{\phi (n)}\equiv (a{a}_1)(a{a}_2)\cdots (a{a}_{\phi (n)})\equiv a_1{a}_2\cdots a_{\phi (n)}(\mathrm{mod}n)$$
由于 $a_1{a}_2\cdots a_{\phi (n)}$ 与 $n$ 互质，可约去，故
$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

证毕。

推论
若正整数 $a$ 与 $n$ 互质，则对于任意正整数 $b$，有
$$a^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n)$$

证明
设 $b=q\cdot \phi (n)+r$，其中 $0\le r<\phi (n)$，则 $r=b\mathrm{mod}\phi (n)$。
$$a^b=a^{q\cdot \phi (n)+r}=(a^{\phi (n)}{)}^q\cdot a^r\equiv 1^q\cdot a^r\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n)$$

证毕。

2. 费马小定理

若 $p$ 是质数，则对于任意整数 $a$，有
$$a^p\equiv a(\mathrm{mod}p)$$

证明
若 $a$ 不是 $p$ 的倍数，则 $\gcd (a,p)=1$。由欧拉定理取 $n=p$，$\phi (p)=p-1$，得 $a^{p-1}\equiv 1(\mathrm{mod}p)$，两边同乘 $a$ 即得 $a^p\equiv a(\mathrm{mod}p)$。

若 $a$ 是 $p$ 的倍数，则 $a^p\equiv a\equiv 0(\mathrm{mod}p)$，命题显然成立。

证毕。

3. 扩展欧拉定理（降幂公式）

当 $a$ 与 $n$ 不一定互质时，对于 $b>\phi (n)$，有
$$a^b\equiv a^{b\mathrm{mod}\phi (n)+\phi (n)}(\mathrm{mod}n)$$

这意味着即使底数与模数不互质，我们仍然可以将指数缩小到容易计算的范围内。该结论可通过寻找 $a^b\mathrm{mod}n$ 的指数循环节来证明，此处留给学有余力的读者自行思考。

---

应用提示

许多计数类题目要求将答案对一个质数 $p$ 取模后输出。

• 对于 $a+b$、$a-b$、$a\cdot b$ 等运算，可以先将 $a,b$ 对 $p$ 取模后再计算。
• 对于乘方运算 $a^b$，根据欧拉定理的推论，可以先将底数 $a$ 对 $p$ 取模、指数 $b$ 对 $\phi (p)$ 取模，再计算乘方。
• 当 $a$ 与 $p$ 不互质时，若 $b>\phi (p)$，可使用扩展欧拉定理进行降幂。

---

四、习题

The Luckiest Number