第 2 章：同余

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

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

17 和 5，看起来不是一个数，但除以 6 都余 5。所以在"模 6 的世界"里，17 和 5 就是同一类东西。这就叫同余。

这章学好了，后面 RSA、中国剩余定理、模幂运算全是小菜一碟。

---

一、同余：两个数除以 m 余数一样

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

两个意思完全等价，考试随便用哪个：

• 意思 A：a 和 b 除以 m，余数一样。
• 意思 B：a - b 能被 m 整除（即 m | (a - b)）。

做题建议：判断题直接用意思 B（做差法），最快。

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

做法一（看余数）：

35 ÷ 8 = 4 余 3。11 ÷ 8 = 1 余 3。余数一样 → 成立。

做法二（做差）：

35 - 11 = 24，24 能被 8 整除吗？24 = 8 × 3，能 → 成立。

做差法明显快一截，推荐。

---

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

模 m 的余数只有 m 种可能：0, 1, 2, ..., m-1。

所谓"模 m 的完全剩余系"，就是从每种余数里各挑一个代表，凑够 m 个数、且余数互不相同。

判断方法就两条：

• 数量够不够 m 个？
• 模 m 之后，余数有没有重复/遗漏？

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

模 8 需要 8 个数。题目只给了 6 个 → 直接否。数量不够，后面都不用看。

这就是"先看数量再看内容"的做题顺序。

---

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

完全剩余系是"所有余数都要"。简化剩余系是"只留跟 m 互素的那些"。

什么叫"互素"

两个数的 gcd 是 1，就叫互素。比如 3 和 10，gcd = 1，所以互素；6 和 10，gcd = 2，不互素。

以模 10 为例：

完全剩余系：

逐一检查谁和 10 的 gcd 是 1：

数	gcd(它, 10)	留下？
0	10	扔
1	1	留
2	2	扔
3	1	留
4	2	扔
5	5	扔
6	2	扔
7	1	留
8	2	扔
9	1	留

所以模 10 的简化剩余系是 {1, 3, 7, 9}。

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

φ(10) = 4——表示 1~10 中和 10 互素的数的个数。

---

四、欧拉函数 φ(n)：一条公式搞定

φ(n) = 1 到 n 里，有多少个正整数和 n 互素。

公式（必背）：

如果 n 的标准分解式是 n = p₁ᵃ¹ × p₂ᵃ² × ... × pₖᵃᵏ，那么：

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

关键：只看出现了哪些素数，不管指数是几。

例题：计算 φ(3000)

先把 3000 分解：

3000 = 3 × 1000 = 3 × (10³) = 3 × 2³ × 5³ = 2³ × 3 × 5³

不同素数：2, 3, 5。

套公式：

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

= 3000 × (1/2) × (2/3) × (4/5)

= 3000 × 1/2 = 1500

= 1500 × 2/3 = 1000

= 1000 × 4/5 = 800

心算技巧

不要一口气通分。直接用 n 逐个乘分式：3000 ÷ 2 = 1500，1500 ÷ 3 × 2 = 1000，1000 ÷ 5 × 4 = 800。

---

五、费马小定理：把大指数变小

如果 p 是素数，且 a 不是 p 的倍数（即 gcd(a, p) = 1），那么：

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

有什么用？指数里每出现一个 (p-1)，就可以把那一坨变成 1。这就叫"降指数"。

例题：算 5³⁰ mod 23

23 是素数，gcd(5, 23) = 1 → 费马小定理生效：

5²² ≡ 1 (mod 23)

把指数 30 拆成 22 + 8：

5³⁰ = 5²² × 5⁸ ≡ 1 × 5⁸ ≡ 5⁸ (mod 23)

现在只需要算 5⁸ mod 23。用"平方再平方"的办法（别傻乘 8 次！）：

目标	怎么来	mod 23
5²	25	2
5⁴	(5²)² = 2²	4
5⁸	(5⁴)² = 4²	16

所以 5³⁰ ≡ 16 (mod 23)。

---

六、欧拉定理：费马小定理的升级版

费马小定理要求模数是素数。欧拉定理把这个条件放宽松了：只要 a 和 m 互素就行。

如果 gcd(a, m) = 1，则 a^φ(m) ≡ 1 (mod m)

区别对比：

	费马小定理	欧拉定理
模数要求	必须是素数 p	任意正整数 m
条件	gcd(a, p) = 1	gcd(a, m) = 1
结论	a^(p-1) ≡ 1 (mod p)	a^φ(m) ≡ 1 (mod m)

简单说：模数是素数 → 费马；模数不是素数（或者你不知道是不是素数）→ 欧拉。

例题：算 5²⁸ mod 22

模数 22 不是素数，但 gcd(5, 22) = 1 → 欧拉定理生效。

先算 φ(22)：

22 = 2 × 11

φ(22) = 22 × (1-1/2) × (1-1/11) = 22 × 1/2 × 10/11 = 10

所以：

5¹⁰ ≡ 1 (mod 22)

把 28 重新组织：28 = 2 × 10 + 8：

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

平方法算 5⁸：

目标	怎么来	mod 22
5²	25	3
5⁴	3² = 9	9
5⁸	9² = 81	81 - 22×3 = 15

所以 5²⁸ ≡ 15 (mod 22)。

---

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

遇到 a^N mod m，指数 N 可能很大，流程是：

1. 先用费马/欧拉降指数（把周期部分干掉）
2. 把剩下的指数写成 2 的幂之和（即二进制展开）
3. 算 a², a⁴, a⁸, a¹⁶... 的平方表
4. 需要哪几个就乘哪几个，边乘边取模

例题：算 2²⁰²⁰ mod 77（典型期末题）

第一步：能不能用欧拉？gcd(2, 77) = 1，可以。

77 = 7 × 11，所以：

φ(77) = 77 × 6/7 × 10/11 = 60

所以：

2⁶⁰ ≡ 1 (mod 77)

第二步：把 2020 按 60 来拆。

2020 ÷ 60 = 33 余 40，即 2020 = 33×60 + 40

2²⁰²⁰ = (2⁶⁰)³³ × 2⁴⁰ ≡ 1³³ × 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 = 32 + 8，所以：

2⁴⁰ = 2³² × 2⁸ ≡ 4 × 25 = 100

第五步：100 mod 77：

100 - 77 = 23

所以 2²⁰²⁰ ≡ 23 (mod 77)。

做这类题的命门

每一步算完都要立刻取模，不然中途的数字会爆炸。2⁴⁰ 大概是 1 万亿，不取模根本没法算。

---

八、RSA 里求私钥 d：本质就是求逆元

期末 RSA 题的标准套路：给你 p, q, e，让你求 d。

已知：

n = p × q

φ(n) = (p-1) × (q-1)

d 要满足：e × d ≡ 1 (mod φ(n))

这句话翻译过来就是：d 是 e 模 φ(n) 下的乘法逆元。用扩展欧几里得求。

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

第一步：算 φ(n)。

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

第二步：问题变成——找一个 d，使得：

17d ≡ 1 (mod 540)

也就是用扩展欧几里得，求 17 模 540 的逆元。

第三步：辗转相除（这里直奔目标，过程简写）。

540 = 17×31 + 13 → 13 = 540 - 17×31

17 = 13×1 + 4 → 4 = 17 - 13×1

13 = 4×3 + 1 → 1 = 13 - 4×3 ← 从这开始回代

4 = 1×4 + 0

第四步：回代（用第 1 章的套路）：

1 = 13 - 4×3 = 13 - (17 - 13) × 3 = 13×4 - 17×3 = (540 - 17×31) × 4 - 17×3 = 540×4 - 17×124 - 17×3 = 540×4 - 17×127 = 17 × (-127) ≡ 1 (mod 540)

d = -127 是负的，要变成正数：

d = -127 + 540 = 413

验证：17 × 413 = 7021 = 540×13 + 1 ✓

所以 d = 413。

---

九、整除判别法速查

考试可能会出证明或判断题，记住这几条就行：

被谁整除	怎么看
2	个位是偶数
3	各位数字和能被 3 整除
4	最后两位能被 4 整除
8	最后三位能被 8 整除
9	各位数字和能被 9 整除
11	奇数位和 - 偶数位和，能被 11 整除

例：判断 11 | 1232？

从右往左数位（个位是第 1 位）：

奇数位（1, 3 位）：2 + 2 = 4 偶数位（2, 4 位）：3 + 1 = 4 差 = 4 - 4 = 0，能被 11 整除 → 11 | 1232

---

十、Miller-Rabin 素性测试（了解即可）

这个东西不是让你手算大数的。期末最多考概念：它的作用是快速判断一个大数是不是"大概率为素数"。

核心想法：

1. 把 n-1 写成 2ˢ × d（d 是奇数）
2. 选一个底数 a
3. 算 aᵈ, a²ᵈ, a⁴ᵈ, ... mod n
4. 不符合规律 → 一定是合数；符合 → 大概率是素数

记住这一句话就够了

Miller-Rabin 说"合数"时很肯定；说"可能是素数"时不保证 100%，是概率意义上的。

---

本章做题速查表

看到什么	立刻想
判断 a ≡ b (mod m)	做差 a-b，看 m 是否整除它
完全剩余系	数量=m？余数不重不漏？
简化剩余系	只留和 m gcd=1 的
求 φ(n)	分解 n → 找出不同素数 → 套 φ(n) = n×(1-1/p₁)×...
大指数取模（模数为素数 p）	费马：a^(p-1) ≡ 1
大指数取模（模数不是素数）	欧拉：a^φ(m) ≡ 1
指数降完了还是大	平方表 + 二进制拆分（模重复平方）
RSA 求 d	扩展欧几里得求 e 模 φ(n) 的逆元

---

最容易翻车的地方

1. 费马和欧拉搞混：模数是素数用费马，不是素数用欧拉。但费马其实就是欧拉在素数时的特例，所以实在分不清就用欧拉，反正欧拉什么情况都能用。
2. φ(n) 公式用错：只乘不同的素数，不乘重复的。比如 8=2³，φ(8)=8×(1-1/2)=4，不是 8×(1-1/2)³。
3. 模重复平方时忘了及时取模：中途数字会爆炸，一爆炸就全白算了。
4. RSA 求 d 算出负数忘了加模数：d 必须是正数，负数的情况加上 φ(n) 就行。
5. 同余和相等的符号搞混：≡ 不是 =，后面 (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 = 7×6）。
2. {0, 1, 2, 3, 4, 5, 6, 7}。
3. {1, 5, 7, 11}，φ(12) = 4。
4. 55 = 5×11，φ(55) = 55×4/5×10/11 = 40。
5. 47 是素数，7⁴⁶ ≡ 1。1000 ÷ 46 = 21 余 34，所以 7¹⁰⁰⁰ ≡ 7³⁴。用平方表算得 36。答案：36。
6. φ = 540，17d ≡ 1 (mod 540)，解得 d = 413。