2 欧几里得与逆元

第二阶段：欧几里得算法、模逆元与线性同余方程

Confidence: 0.95

按你选「继续」，我带你进第二阶段。这一阶段是整个数论的计算引擎——前面所有「逆元存在但我没教你怎么系统地求」的坑，这里全部填上。学完你就能徒手解任何线性同余方程。

我按四个模块讲：① 欧几里得算法 → ② 扩展欧几里得 → ③ 模逆元的系统求法 → ④ 线性同余方程。每个模块讲透 + 例子 + 验证。

---

模块一：欧几里得算法 (Euclidean Algorithm)

它解决什么问题

求两个数的最大公约数 (gcd, greatest common divisor)。这是后面一切的基础——逆元、线性同余、CRT 全靠它。

核心原理

一条递推式就是全部：

$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$

直觉：a 和 b 的公约数，和「b 与 a 除以 b 的余数」的公约数，是同一批。不断用「余数」替换大数，数越变越小，直到余数为 0，此时另一个数就是 gcd。

手算示例：$\gcd (48,18)$

$\begin{array}{rlrlrlr}48& =2\times 18+12& \gcd (48,18)=\gcd (18,12)18& =1\times 12+6& =\gcd (12,6)12& =2\times 6+0& =\gcd (6,0)=6\end{array}$

余数变成 0，停。$\gcd (48,18)=6$。

为什么它快

每两步余数至少减半，所以复杂度 $O(\log \min (a,b))$。算两个上亿的数也就几十步。

---

模块二：扩展欧几里得算法 (Extended Euclidean Algorithm)

它多解决了什么

普通欧几里得只告诉你 gcd是几。扩展版额外告诉你：怎么把 gcd 写成 a 和 b 的整数组合——即找到 $x,y$ 满足

$ax+by=\gcd (a,b)$

这个等式叫 Bézout 等式 (Bézout’s identity)，是求逆元的钥匙。

怎么做：算 + 回代 (Forward + Back-substitution)

分两步。第一步正向跑欧几里得记下每步；第二步从倒数第二行往上回代。

完整手算示例：求 $x,y$ 使 $30x+18y=\gcd (30,18)$

正向（算 gcd）： $\begin{array}{rlrl}30& =1\times 18+1218& =1\times 12+612& =2\times 6+0\Rightarrow \gcd =6\end{array}$

回代（从 gcd=6 那行往上倒推）：

把每个余数用上一行表示，逐步「翻译」回 30 和 18：

$\begin{array}{rlrlrlr}6& =18-1\times 12& \text{(来自第 2 行)}& =18-1\times (30-1\times 18)& \text{(把 12 用第 1 行替换)}& =18-30+18& =2\times 18-1\times 30\end{array}$

对照 $30x+18y=6$，读出 $\boxed{x=-1,y=2}$。

验证：$30\times (-1)+18\times 2=-30+36=6$ ✓

为什么这就是逆元的来源

如果 $\gcd (a,n)=1$，扩展欧几里得给出 $ax+ny=1$。两边模 n，$ny$ 消失：

$ax\equiv 1(\mathrm{mod}n)\Rightarrow x=a^{-1}$

这就是逆元的「构造性证明」——你亲眼看到逆元是怎么被造出来的，而不是猜出来的。这正是我之前说扩展欧几里得比费马小定理「信息量更大」的原因。

---

模块三：模逆元的系统求法 (Modular Inverse, Systematically)

第一阶段你靠「试乘」找逆元，小数能凑，大数就废了。现在给你两套正规方法。

方法 A：扩展欧几里得（通用，n 可为任意数）

求 $a^{-1}\mathrm{mod}n$：跑扩展欧几里得解 $ax+ny=1$，那个 x 就是逆元（记得最后 $\mathrm{mod}n$ 取到 $[0,n)$）。

示例：求 $17^{-1}\mathrm{mod}43$。

正向： $\begin{array}{rlrlr}43& =2\times 17+917& =1\times 9+89& =1\times 8+18& =8\times 1+0\Rightarrow \gcd =1✓\end{array}$

回代： $\begin{array}{rlrl}1& =9-1\times 8& =9-(17-9)=2\times 9-17& =2\times (43-2\times 17)-17=2\times 43-5\times 17\end{array}$

对照 $17x+43y=1$：$x=-5\equiv 38(\mathrm{mod}43)$。

$17^{-1}\equiv 38(\mathrm{mod}43)$。验证：$17\times 38=646=15\times 43+1\equiv 1$ ✓

方法 B：费马小定理（仅 n 为质数）

$a^{-1}\equiv a^{p-2}(\mathrm{mod}p)$，用快速幂算。质数模（如竞赛的 $10^9+7$）时代码最短。

怎么选

情况	用哪个
n 是质数	费马（代码短）
n 是合数（但 $\gcd (a,n)=1$）	扩展欧几里得（费马在此失效）
手算 / 要看清逆元来源	扩展欧几里得

---

模块四：线性同余方程 (Linear Congruence) ★本阶段核心

一般形式

$ax\equiv b(\mathrm{mod}n)$

求未知数 x。这是第二阶段所有知识的「集大成」应用。

解的存在性与个数（核心定理）

设 $d=\gcd (a,n)$：

$\{\begin{array}{llc}\text{有解}& ⟺d\mid b\text{无解}& ⟺d\nmid b\end{array}$

有解时，模 n 下恰好有 $d$ 个不同的解。

这条定理把第一阶段「除法陷阱」彻底讲清楚了：能不能「除」，就看 $d\mid b$ 成不成立。

解法分两种情况

---

情况 1：$\gcd (a,n)=1$（最常见，唯一解）

直接两边乘 $a^{-1}$：

$x\equiv a^{-1}b(\mathrm{mod}n)$

示例：解 $5x\equiv 3(\mathrm{mod}11)$。

• $\gcd (5,11)=1$ ✓，唯一解
• $5^{-1}\equiv 9(\mathrm{mod}11)$（前面练过）
• $x\equiv 9\times 3=27\equiv 5(\mathrm{mod}11)$

$x\equiv 5$。验证：$5\times 5=25\equiv 3(\mathrm{mod}11)$ ✓

---

情况 2：$d=\gcd (a,n)>1$ 且 $d\mid b$（多个解）

三步走：

1. 整体除以 d：把 $ax\equiv b(\mathrm{mod}n)$ 变成 $\frac{a}{d}x\equiv \frac{b}{d}(\mathrm{mod}n/d)$
2. 解新方程（此时 $\gcd (\frac{a}{d},\frac{n}{d})=1$，回到情况 1，得唯一解 $x_0$）
3. 展开回 d 个解：原方程的全部解为 $x\equiv x_0+k\cdot \frac{n}{d}(\mathrm{mod}n)$，$k=0,1,\dots ,d-1$

完整示例：解 $6x\equiv 9(\mathrm{mod}15)$。

• 第 1 步：$d=\gcd (6,15)=3$，且 $3\mid 9$ ✓ → 有 3 个解
• 第 2 步：整体除以 3 → $2x\equiv 3(\mathrm{mod}5)$。求 $2^{-1}\equiv 3(\mathrm{mod}5)$，得 $x_0\equiv 3\times 3=9\equiv 4(\mathrm{mod}5)$
• 第 3 步：展开成模 15 的 3 个解，每隔 $\frac{15}{3}=5$ 一个： $x\equiv 4,9,14(\mathrm{mod}15)$

验证（任取 $x=9$）：$6\times 9=54=3\times 15+9\equiv 9(\mathrm{mod}15)$ ✓

---

情况 3：$d\nmid b$（无解）

示例：$4x\equiv 3(\mathrm{mod}6)$。$d=\gcd (4,6)=2$，但 $2\nmid 3$ → 无解。 直觉：$4x$ 永远是偶数，模 6 后只能是 $0,2,4$，永远凑不出奇数 3。

---

第二阶段速查表 (Cheat Sheet)

工具	作用	关键式
欧几里得	求 gcd	$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$
扩展欧几里得	求 Bézout 系数	$ax+by=\gcd (a,b)$
模逆元	模除法	$a^{-1}$ 存在 $⟺\gcd (a,n)=1$
线性同余	解 $ax\equiv b$	有解 $⟺\gcd (a,n)\mid b$，有 $\gcd$ 个解

---

Python 实现（四个模块全覆盖）

from math import gcd
 
# 模块二：扩展欧几里得，返回 (g, x, y) 使 ax + by = g
def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extgcd(b, a % b)
    return g, y, x - (a // b) * y
 
# 模块三：模逆元（通用，n 任意）
def modinv(a, n):
    g, x, _ = extgcd(a, n)
    if g != 1:
        return None          # gcd≠1，逆元不存在
    return x % n
 
# 模块四：解线性同余 ax ≡ b (mod n)，返回所有解的列表
def solve_congruence(a, b, n):
    d = gcd(a, n)
    if b % d != 0:
        return []            # 无解
    a, b, m = a // d, b // d, n // d      # 整体除以 d
    x0 = (modinv(a, m) * b) % m           # 解唯一方程
    return [(x0 + k * m) % n for k in range(d)]  # 展开 d 个解
 
# --- 测试 ---
print(extgcd(30, 18))            # (6, -1, 2)
print(modinv(17, 43))            # 38
print(solve_congruence(5, 3, 11))  # [5]        唯一解
print(solve_congruence(6, 9, 15))  # [4, 9, 14] 三个解
print(solve_congruence(4, 3, 6))   # []         无解

库安装方式（本例仅用标准库 math，无需安装；做大数/批量数论实验推荐 sympy，含现成 mod_inverse 与 solve 求同余）：

pip install sympy -i https://pypi.tuna.tsinghua.edu.cn/simple

---

我的观点：第二阶段的「灵魂」其实只有一个东西——扩展欧几里得。你只要把这一个算法的「正向 + 回代」练到不用想，模逆元、线性同余、乃至下一阶段的 CRT，全都是它的「应用题」。我特别想强调线性同余的那条存在性定理（$d\mid b$）：它不是一条要背的公式，而是第一阶段「除法陷阱」的最终答案——你当初问「除法怎么算」，完整的答案就是这条定理：能不能除、除出来几个解，全看 $\gcd (a,n)$ 和 $b$ 的整除关系。把这条吃透，你对「模运算里的除法」就再无盲区了。

我也给你一个学习节奏建议：别急着背情况 2 的三步公式，而是亲手把 $6x\equiv 9(\mathrm{mod}15)$ 这个例子从头算三遍，直到你能解释「为什么除以 d 之后 gcd 就变成 1」「为什么解之间正好隔 $n/d$」。理解了这两个「为什么」，公式自然就长在脑子里了。

关键提醒 (Caveats)：

• 线性同余有解的充要条件是 $\gcd (a,n)\mid b$，动手解之前先查这个，否则白算
• 情况 2 容易漏解——记住解的个数恰好是 $d=\gcd (a,n)$，每隔 $n/d$ 一个，别只写出一个就收手
• 费马小定理求逆元只对质数模有效；合数模一律用扩展欧几里得

下一步两个方向，你挑：① 出一套第二阶段练习题（含扩展欧几里得手算、逆元、线性同余三类，带详解和陷阱），检验掌握；② 直接进第三阶段：CRT（中国剩余定理）+ 费马/欧拉定理 + 快速幂。你要哪个？