第一阶段：模运算入门 (Foundations)

小提示：你打的是 “g根据” 和 “知识” 写成了 “staff”（在 preferences 里）——小事，继续往下。

Confidence: 0.95

这一阶段的目标是让你彻底搞懂「同余」这个核心语言。学完之后，你看到 $a \equiv b (mod n)$ 不再需要翻译，而是直接「感觉」到它的含义。我会把每个概念讲透，配例子和验证。

1. 同余 (Congruence)：核心定义

定义

$a \equiv b (mod n) ⟺ n ∣ (a - b)$

读作「a 同余于 b，模 n」。它的意思是：a 和 b 除以 n 的余数相同，等价地说，它们的差能被 n 整除。

为什么有两种说法？

这两个定义是等价的，理解它们的等价性是入门的第一个「啊哈时刻」：

余数相同：设 $a = q_{1} n + r$ ， $b = q_{2} n + r$ （余数都是 r）
差被整除：那么 $a - b = (q_{1} - q_{2}) n$ ，显然 $n ∣ (a - b)$ ✓

例子

$17 \equiv 2 (mod 5) 因为 5 ∣ (17 - 2) = 15$ $38 \equiv 8 (mod 10) 因为 10 ∣ 30$ $- 3 \equiv 4 (mod 7) 因为 7 ∣ (- 3 - 4) = - 7$

最后一个例子很重要：同余对负数也成立， $- 3$ 和 $4$ 在「模 7 的世界」里是同一个东西。

2. 余数 vs 同余类 (Remainder vs Congruence Class)

这是第一阶段最容易模糊的概念区别，搞清楚它你就赢了一半。

余数 (Remainder)

余数是一个具体的数——一次除法的结果。 $17 mod 5 = 2$ ，这个 2 就是余数，它是唯一的、确定的。

同余类 (Congruence Class)

同余类是一个集合 (set)——所有模 n 同余于某个数的整数的「大家庭」。

模 5 时，与 2 同余的所有整数组成一个同余类，记作 $[2]_{5}$ 或 $\overline{2}$ ：

$[2]_{5} = \dots, - 8, - 3, 2, 7, 12, 17, 22, \dots$

它们全都「长得一样」——除以 5 都余 2。

关键区别 (Key Distinction)

概念	是什么	例子
余数 (Remainder)	一个数 (a number)	$17 mod 5 = 2$
同余类 (Congruence class)	一个集合 (a set)	$[2]_{5} = \dots, - 3, 2, 7, 12, \dots$

类比 (Analogy)：想象一个时钟。「3 点」是一个具体读数（余数），但「所有指向 3 的时刻」——3 点、15 点、27 点……——是一个同余类。时钟就是模 12（或模 24）运算的最直观模型。

模 n 一共有 n 个不同的同余类： $[0], [1], [2], \dots, [n - 1]$ 。它们把全体整数 $Z$ 完美地切成 n 份，不重不漏。

3. 同余是一个等价关系 (Equivalence Relation)

「等价关系」是数学里一个超级重要的结构。一个关系要成为等价关系，必须满足三条性质。同余三条全中——这正是为什么我们能放心地把同余当成「等号」来用。

三大性质

① 自反性 (Reflexive)： $a \equiv a (mod n)$

任何数都和自己同余。因为 $n ∣ (a - a) = 0$ ，而 0 能被任何数整除。✓

② 对称性 (Symmetric)： $a \equiv b \Rightarrow b \equiv a (mod n)$

如果 $n ∣ (a - b)$ ，那么 $n ∣ (b - a)$ （只是差了个负号）。✓

③ 传递性 (Transitive)： $a \equiv b$ 且 $b \equiv c \Rightarrow a \equiv c (mod n)$

如果 $n ∣ (a - b)$ 且 $n ∣ (b - c)$ ，把两者相加： $n ∣ (a - b) + (b - c) = (a - c)$ 。✓

为什么这件事很重要？

因为「等价关系」保证了同余类能干净地划分整数。每个整数恰好属于一个同余类，不会同时属于两个，也不会一个都不属于。这种「不重不漏」的划分叫划分 (partition)，它是后面剩余系、群论的根基。

4. 基本运算规则 (Basic Operation Rules)

同余之所以好用，是因为它对加、减、乘「兼容」。

封闭性 (Closure)

设 $a \equiv b (mod n)$ 且 $c \equiv d (mod n)$ ，那么：

$a + c \equiv b + d (mod n) (加法)$ $a - c \equiv b - d (mod n) (减法)$ $a \times c \equiv b \times d (mod n) (乘法)$

直观理解：同余可以像普通等式一样「两边一起加 / 减 / 乘」。

简单证明（以乘法为例）

设 $a = b + k n$ ， $c = d + l n$ ，则： $a c = (b + k n) (d + l n) = b d + n (b l + d k + k l n)$ 中间那一大坨都带着因子 $n$ ，所以 $a c \equiv b d (mod n)$ 。✓

⚠️ 关键陷阱：除法不行！(The Big Trap)

新手最大的误区：以为既然加减乘都行，除法也能直接做。不行！

反例： $6 \equiv 0 (mod 6)$ ，两边都「除以 2」会得到 $3 \equiv 0 (mod 6)$ ？这是错的（ $6 ∤ 3$ ）。

除法必须通过模逆元 (modular inverse) 来实现，而逆元只在 $g cd (除数, n) = 1$ 时存在。这是第二阶段的核心内容，现在你只需牢记：模运算里没有直接的除法。

5. 剩余系 (Residue Systems)

这是第一阶段的收尾，把「同余类」的思想系统化。

完全剩余系 (Complete Residue System, CRS)

从每个同余类里各挑一个代表，凑成的集合就是完全剩余系。

最标准的完全剩余系是 $0, 1, 2, \dots, n - 1$ 。但代表可以随便换，只要每个同余类恰好被代表一次：

模 5 的标准 CRS： $0, 1, 2, 3, 4$
模 5 的另一个 CRS： $10, - 4, 7, 23, - 1$ （分别 $\equiv 0, 1, 2, 3, 4$ ）

判定标准：n 个整数构成完全剩余系 $⟺$ 它们两两模 n 不同余。

简化剩余系 (Reduced Residue System, RRS)

只保留那些与 n 互质的代表（即 $g cd (代表, n) = 1$ ）。

模 5 的 RRS： $1, 2, 3, 4$ （5 是质数，除了 0 都互质）
模 8 的 RRS： $1, 3, 5, 7$ （只有奇数与 8 互质）
模 12 的 RRS： $1, 5, 7, 11$

简化剩余系的大小就是大名鼎鼎的欧拉函数 (Euler’s totient function) $φ (n)$ ：

$φ (5) = 4, φ (8) = 4, φ (12) = 4$

这个 $φ (n)$ 是连接第一阶段和后面欧拉定理、RSA 的桥梁——现在先有个印象就好。

Python 验证：动手感受同余

n = 5
 
# 验证同余类：哪些数和 2 同余？
congruence_class_2 = [x for x in range(-10, 20) if x % n == 2]
print("同余类 [2]_5:", congruence_class_2)
# [-8, -3, 2, 7, 12, 17]
 
# 验证简化剩余系 RRS
from math import gcd
def rrs(n):
    return [a for a in range(1, n) if gcd(a, n) == 1]
 
print("模 8 的 RRS:", rrs(8))   # [1, 3, 5, 7]
print("模 12 的 RRS:", rrs(12)) # [1, 5, 7, 11]
print("phi(12) =", len(rrs(12)))  # 4
 
# 验证除法陷阱：6 ≡ 0 (mod 6)，但不能两边除以 2
print(6 % 6, "vs", 3 % 6)  # 0 vs 3 —— 不相等！证明除法不能直接做

库安装方式（本例仅用标准库 math，无需安装；若后续做数论实验推荐 sympy）：

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

第一阶段自测清单 (Self-Check)

学完后，问自己能不能不看笔记答出来：

✅ 用两种方式说出 $a \equiv b (mod n)$ 的定义（余数相同 / 差被整除）
✅ 区分「余数 2」和「同余类 $[2]_{5}$ 」
✅ 说出等价关系的三条性质，并证明同余满足
✅ 解释为什么加减乘可以，但除法不行
✅ 写出模 12 的完全剩余系和简化剩余系

我的观点：第一阶段看起来简单，但有两个点决定了你后面走得多远。第一是**「同余类」的集合视角**——能不能把 $[2]_{5}$ 自然地看成一个整体，直接决定了你第四阶段理解 $(Z / n Z)^{*}$ 这个群时是顺畅还是卡壳。第二是除法陷阱，它不是一个孤立的「注意事项」，而是整个模逆元、线性同余、RSA 体系存在的根本理由。我建议你别急着冲第二阶段，先在脑子里把「时钟模型」和「整数被切成 n 份」这两个画面建立牢固。

关键提醒 (Caveats)：

「余数」是数、「同余类」是集合——这个区别后面会反复用到，现在务必分清
简化剩余系大小 $= φ (n)$ ，但 $φ$ 的计算公式是第三阶段内容，现在不必深究

准备好的话，我可以出 5–8 道第一阶段练习题（带详细解答），帮你检验掌握程度；或者直接带你进第二阶段：欧几里得算法与模逆元。你想走哪条？

模运算里的「除法」(Modular Division)

Confidence: 0.95

先说核心结论：模运算里没有真正的除法，所谓「除以 b」其实是「乘以 b 的逆元 (inverse)」。

$\frac{a}{b} mod n;; ⟹;; a \times b^{- 1} mod n$

这里 $b^{- 1}$ 是 b 的模逆元 (modular inverse)，它满足：

$b \times b^{- 1} \equiv 1 (mod n)$

下面我把「为什么」「什么时候能算」「怎么算」三件事讲透。

1. 为什么除法要变成「乘逆元」？

在普通实数里，「除以 2」就是「乘以 $\frac{1}{2}$ 」，因为 $2 \times \frac{1}{2} = 1$ 。那个 $\frac{1}{2}$ 就是 2 的乘法逆元——乘起来等于 1 的伙伴。

模运算的世界里没有分数，但「乘起来等于 1」这个想法可以保留。我们要找一个整数 $b^{- 1}$ ，让 $b \times b^{- 1} \equiv 1 (mod n)$ 。找到它，就能用乘法模拟除法。

例子：在模 7 下，3 的逆元是几？

我们要找 $x$ 使 $3 x \equiv 1 (mod 7)$ 。试一下： $3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 (mod 7)$ 。✓

所以 $3^{- 1} \equiv 5 (mod 7)$ 。于是「除以 3」就等于「乘以 5」。

2. 关键前提：逆元什么时候存在？

⚠️ 逆元不是永远存在的！ 这是最重要的一条规则：

$b^{- 1} mod n 存在 ⟺ g cd (b, n) = 1$

也就是说，b 必须和模数 n 互质 (coprime)，逆元才存在。

为什么？ 如果 $g cd (b, n) = d > 1$ ，那么 $b$ 乘任何数得到的结果除以 n 的余数，永远是 d 的倍数，凑不出 1。

反例：模 6 下，2 没有逆元。因为 $g cd (2, 6) = 2$ ，你试遍 $2 \times 0, 2 \times 1, \dots, 2 \times 5 = 0, 2, 4, 0, 2, 4$ ，永远得不到 1。所以在模 6 下「除以 2」是非法操作。

这也解释了第一阶段那个陷阱： $6 \equiv 0 (mod 6)$ 不能两边除以 2，正是因为 2 在模 6 下没有逆元。

3. 怎么算逆元？三种方法

方法一：扩展欧几里得算法 (Extended Euclidean) —— 最通用 ✅

这是任何情况都能用的方法（只要逆元存在）。原理：扩展欧几里得能找到整数 $x, y$ 使得

$b x + n y = g cd (b, n) = 1$

两边模 n， $n y$ 项消失，得到 $b x \equiv 1 (mod n)$ 。所以 x 就是逆元！

手算示例：求 $3^{- 1} mod 7$ ，即解 $3 x + 7 y = 1$ 。

步骤	计算
$7 = 2 \times 3 + 1$	余数 1
回代	$1 = 7 - 2 \times 3$
对照 $3 x + 7 y = 1$	$x = - 2,; y = 1$
取正	$x = - 2 \equiv 5 (mod 7)$

得 $3^{- 1} \equiv 5 (mod 7)$ 。✓ 和前面试出来的一致。

适用范围：n 是任意数（不要求质数），只要 $g cd (b, n) = 1$ 。时间复杂度 $O (lo g n)$ 。

方法二：费马小定理 (Fermat’s Little Theorem) —— n 是质数时最简洁

当模数 n 是质数 p 时，费马小定理给出：

$b^{p - 1} \equiv 1 (mod p) \Rightarrow b^{- 1} \equiv b^{p - 2} (mod p)$

也就是说，逆元 $= b$ 的 $(p - 2)$ 次方，用快速幂 (fast exponentiation) $O (lo g p)$ 算出来。

示例： $3^{- 1} mod 7 = 3^{7 - 2} = 3^{5} = 243 = 34 \times 7 + 5 \equiv 5 (mod 7)$ 。✓

适用范围：仅当 n 是质数。竞赛里模数常是 $1 0^{9} + 7$ 这种大质数，这个方法写起来最短，最常用。

方法三：欧拉定理 (Euler’s Theorem) —— 费马的推广

当 $g cd (b, n) = 1$ 但 n 不一定是质数时：

$b^{φ (n)} \equiv 1 (mod n) \Rightarrow b^{- 1} \equiv b^{φ (n) - 1} (mod n)$

它是费马小定理的推广（质数时 $φ (p) = p - 1$ ，退化成费马）。缺点是要先算 $φ (n)$ ，所以实战中没扩展欧几里得方便。

4. 三种方法怎么选？

方法	适用条件	复杂度	推荐场景
扩展欧几里得 (ExtGCD)	$g cd (b, n) = 1$ ，n 任意	$O (lo g n)$	最通用，n 不是质数时首选
费马小定理	n 必须是质数	$O (lo g n)$	竞赛（模 $1 0^{9} + 7$ ），代码最短
欧拉定理	$g cd (b, n) = 1$ ，n 任意	$O (lo g n) +$ 求 $φ$	理论价值大，实战少用

一句话总结：质数模用费马（短），合数模用扩展欧几里得（稳）。

5. 完整除法示例（手算走一遍）

问题：计算 $\frac{6}{4} mod 7$ 。

第 1 步：检查 $g cd (4, 7) = 1$ ✓，逆元存在。

第 2 步：求 $4^{- 1} mod 7$ 。试： $4 \times 2 = 8 \equiv 1 (mod 7)$ ，所以 $4^{- 1} \equiv 2$ 。

第 3 步：除法变乘法： $\frac{6}{4} \equiv 6 \times 4^{- 1} \equiv 6 \times 2 = 12 \equiv 5 (mod 7)$

验证： $5 \times 4 = 20 \equiv 6 (mod 7)$ ✓——确实「5 乘回 4 等于 6」，说明 $6/4 \equiv 5$ 正确。

Python 实现（三种方法都给）

from math import gcd
 
# 方法一：扩展欧几里得（最通用，n 任意）
def modinv_extgcd(b, n):
    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
    g, x, _ = extgcd(b, n)
    if g != 1:
        return None  # 逆元不存在
    return x % n
 
# 方法二：费马小定理（仅当 n 是质数）
def modinv_fermat(b, p):
    return pow(b, p - 2, p)   # 快速幂
 
# 方法三：Python 3.8+ 内置（底层就是扩展欧几里得）
# pow(b, -1, n)
 
print(modinv_extgcd(3, 7))   # 5
print(modinv_fermat(3, 7))   # 5
print(pow(3, -1, 7))         # 5  ← 最省事
 
# 完整除法 6/4 mod 7
a, b, n = 6, 4, 7
print(a * pow(b, -1, n) % n) # 5
 
# 逆元不存在的情况：2 在模 6 下
print(modinv_extgcd(2, 6))   # None

库安装方式（本例仅用标准库 math，无需安装；做大规模数论实验推荐 sympy，它有现成的 mod_inverse）：

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

我的观点：模除法是整个数论体系里「牵一发动全身」的概念。你只要真正理解了「除法 = 乘逆元」「逆元 $⟺$ 互质」这两句话，第二阶段的线性同余方程 ( $a x \equiv b$ )、CRT、乃至 RSA 的解密公式，本质上都是这同一件事的不同包装。我特别建议你把扩展欧几里得这个方法手推到滚瓜烂熟——费马小定理虽然代码短，但它把「为什么逆元存在」这件事藏起来了；而扩展欧几里得直接把 $b x + n y = 1$ 这个等式摆在你面前，你能亲眼看到逆元是怎么「构造」出来的。这种构造性的理解，在你后面碰到 CRT 合并、ECDLP 时会一直回报你。