第 2 章：同余

这一章的核心思想简单到只有一句话：

我们不关心一个数有多大，只关心它除以 m 余几。

17 和 5 看起来差别很大，但除以 6 都余 5。所以在“模 6 的世界”里，17 和 5 就是完全等价的兄弟。这就叫同余。

这章学好了，后面期末必考大题的“RSA 算法”和“中国剩余定理”全是小菜一碟！

---

一、同余：长得不同，余数一样

a ≡ b (mod m)，读作“a 和 b 模 m 同余”。

这两个意思完全等价，考场上随便切：

• 意思 A（看余数）：a 和 b 除以 m，余数一模一样。
• 意思 B（做差法）：a - b 能被 m 整除（即 m 能整除 a - b）。

💥 考场开挂建议：判断题直接用做差法，秒杀！

例题：35 ≡ 11 (mod 8) 成不成立？

做差法：35 - 11 = 24。24 能被 8 整除吗？能（8×3=24）！成立！ （比你分别算 35÷8 和 11÷8 快多了）

---

二、完全剩余系：每种余数各派一个代表

模 m 的余数只有 m 种可能：0, 1, 2, ..., m-1。 所谓“完全剩余系”，就是从每种余数里各挑一个代表，凑够 m 个数、且余数互不相同。

判断方法就两条（按顺序看）：

1. 数量够不够 m 个？（不够直接叉掉）
2. 模 m 之后，余数有没有重复/遗漏？

例题：{12, 15, 18, 21, 24, 27} 是模 8 的完全剩余系吗？

模 8 需要 8 个数。题目只给了 6 个 → 直接否！连算都不用算。

---

三、简化剩余系 & 欧拉函数：只留和 m 互素的精英

完全剩余系是“全都要”。简化剩余系是**“只留跟 m 互素的那些”**。

什么是互素？（复习第1章）

两个数的最大公约数 gcd = 1，就叫互素。比如 3 和 10 互素，6 和 10（都能被2除）就不互素。

以模 10 为例： 本来有 10 个数：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 把跟 10 不互素的（偶数和5）全踢掉，剩下的简化剩余系是 {1, 3, 7, 9}。

这 4 个数的个数，有个专门的神级名字叫欧拉函数：

φ(10) = 4 —— 表示 1 到 10 里，有 4 个数跟 10 互素。

---

四、欧拉函数 φ(n)：一条公式，一个口诀

怎么算任意一个大数 n 的 φ(n)？

公式（必背）： 先打碎成标准分解式 n = p₁^a₁ × p₂^a₂ × ...

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ...

🚨 考场防错口诀：只看底座，不管头上顶着几！ 公式里只带入出现了哪些素数（p），千万别把指数（a）带进去算！

例题：计算 φ(3000)

第一步：分解 3000

3000 = 3 × 1000 = 3 × 2³ × 5³ 底座出现的素数只有：2, 3, 5。（指数的 3 直接无视！）

第二步：套公式

φ(3000) = 3000 × (1 - 1/2) × (1 - 1/3) × (1 - 1/5)

💡 考场计算技巧：连环相乘，别通分！

= 3000 ÷ 2 × 1 = 1500 = 1500 ÷ 3 × 2 = 1000 = 1000 ÷ 5 × 4 = 800 答案就是 800！

---

五、降幂大法：费马小定理 & 欧拉定理

这俩定理本质是同一个东西，作用只有一个：把大得吓人的指数变小。

1. 费马小定理（模数 p 是素数时用）

前提：p 是素数，且 a 不是 p 的倍数（即互素）。

a^(p-1) ≡ 1 (mod p)

例题：算 5³⁰ mod 23 23 是素数 → 费马生效：5²² ≡ 1 (mod 23) 把 30 拆成 22 + 8：

5³⁰ = 5²² × 5⁸ ≡ 1 × 5⁸ ≡ 5⁸ (mod 23) (看，指数直接从 30 降到了 8！)

2. 欧拉定理（模数 m 不是素数时用）

前提：a 和 m 互素。

a^φ(m) ≡ 1 (mod m)

例题：算 5²⁸ mod 22 22 不是素数，先算 φ(22) = 22 × (1-1/2) × (1-1/11) = 10 欧拉生效：5¹⁰ ≡ 1 (mod 22) 把 28 拆成 20 + 8：

5²⁸ = (5¹⁰)² × 5⁸ ≡ 1² × 5⁸ ≡ 5⁸ (mod 22)

搞不清用哪个？

其实费马就是欧拉的青春版。素数 p 的欧拉函数 φ(p) 正好等于 p-1。所以遇到题，只要两者互素，统一找 φ(m) 当周期去降指数，绝对不会错！

---

六、模重复平方算法：指数再大也不怕

指数降完了，如果是 2⁴⁰ 这种还是很大怎么办？ 步骤：建平方表 → 拆指数 → 挑着乘。

承接上面的例子：算 2⁴⁰ mod 77

第一步：建平方表（一直平方，边平边取模！）

目标	怎么来	mod 77 的结果
2²	4	4
2⁴	4² = 16	16
2⁸	16² = 256	256 - 77×3 = 25
2¹⁶	25² = 625	625 - 77×8 = 9
2³²	9² = 81	81 - 77 = 4

第二步：拆指数（把 40 拆成表里有的数）

40 = 32 + 8

第三步：挑着乘（只乘拆出来的部分）

2⁴⁰ = 2³² × 2⁸ ≡ 4 × 25 = 100 最后再取模：100 - 77 = 23。搞定！

---

七、💥 RSA 里求私钥 d（大轴戏，必考）

期末 RSA 题的绝对核心：给你 p, q, e，求私钥 d。 公式就一句话：d 就是 e 模 φ(n) 的逆元。

e × d ≡ 1 (mod φ(n))

例题：p=19, q=31, e=17，求 d。

第一步：算 φ(n)

φ(n) = (19-1) × (31-1) = 18 × 30 = 540

第二步：列等式

17d ≡ 1 (mod 540)

第三步：召唤第1章的“神奇表格法”秒杀逆元！ 我们要算 540x + 17d = 1，求 d 所在的那个位置（即第四列 y 的值）。 前两行写死（大数 540 在上，小数 17 在下），不断用**“当前行 = 上上行 - 商 × 上一行”**：

行号	商 q	余数 r	x	y（这是d）	考场草稿计算过程（不用写）
-1	无	540	1	0	(写死)
0	无	17	0	1	(写死)
1	31	13	1	-31	q: 540÷17=31余13 y: 0 - 31×1 = -31
2	1	4	-1	32	q: 17÷13=1余4 y: 1 - 1×(-31) = 32
3	3	1	4	-127	q: 13÷4=3余1 y: -31 - 3×32 = -127

算到余数 r=1，直接看最后一行的 y，得到 d = -127！ 是不是比书上的往回代入法爽多了？

🚨 最后一步救命警告：d 算出来是负数怎么办？ 密码学里绝对不许有负数密钥！ 处理方法：加一次模数 φ(n)！

d = -127 + 540 = 413。 这就是最终答案！

---

八、整除判别法速查 & Miller-Rabin

1. 常见整除判断：

• 除以 3 或 9：把所有位上的数字加起来，看能不能被 3/9 整除。
• 除以 11：奇数位之和 减去 偶数位之和，能被 11 整除。

2. Miller-Rabin 素性测试（考概念）： 作用：快速判断一个极大的数“大概率是不是素数”。 特点：它说你是合数，你 100% 是合数；它说你是素数，你只是“大概率”是素数（有极小概率错判）。

---

🚀 本章做题速查表

看到什么	立刻想
判断 a ≡ b (mod m)	直接相减，看 m 能不能整除差值。
求欧拉函数 φ(n)	分解因数 → 只取底数不取指数 → 套连乘公式。
大指数取模 (a^N)	a与m互素吗？互素就用 a^φ(m) ≡ 1 降维打击。
指数降完了还是大	建平方表 + 把指数拆成 2 的幂之和。
RSA 求 d	列出 ed ≡ 1 (mod φ(n))，用表格法求扩展欧几里得。
算出逆元 d 是负数	疯狂警告！必须加上模数 φ(n) 变成正数！

---

☠️ 历年期末最容易连环翻车的地方

1. φ(n) 公式带入指数：算 φ(8) 时，8=2³，公式是 8×(1-1/2)=4。你敢把指数 3 带进去算成 8×(1-1/2)³=1，这题就全零分了。
2. 模重复平方时忘了及时取模：千万别硬算 2⁴⁰ 是多少，你的计算器会按爆的，每次平方后必须立刻 mod。
3. RSA 求 d 算出负数直接交卷：再次强调，d 必须是正数！负数加上 φ(n)！
4. 同余和相等的符号搞混：≡ 不是 =，写解答题时行末别忘了挂上 (mod m) 的尾巴。

---

自测题（满分过关才能看下一章）

1. 判断 47 ≡ 5 (mod 7) 是否成立。
2. 写出模 8 的最小非负完全剩余系。
3. 写出模 12 的一个简化剩余系，并求 φ(12)。
4. 计算 φ(55)。
5. 计算 7¹⁰⁰⁰ mod 47。
6. 已知 p=19, q=31, e=17，求 RSA 私钥指数 d。（必须用表格法自己算一遍！）

---

自测答案

1. 成立（47 - 5 = 42，42 能被 7 整除）。
2. {0, 1, 2, 3, 4, 5, 6, 7}。
3. 把跟 12 不互素的划掉，剩下 {1, 5, 7, 11}，共 4 个，所以 φ(12) = 4。
4. 55 = 5×11，φ(55) = 55 ÷ 5 × 4 ÷ 11 × 10 = 40。
5. 47 是素数，7⁴⁶ ≡ 1。1000 ÷ 46 = 21 余 34，所以 7¹⁰⁰⁰ ≡ 7³⁴。用平方表算得 36。答案：36。
6. φ = 540，求 17d ≡ 1 (mod 540)。表格法算出 -127，加 540 转正，最终 d = 413。