Appearance
第 1 章：整数的可除性
这一章说到底是三件事：
能不能除尽？除不尽的话余多少？两个数的最大公约数怎么凑出来？
考试翻来覆去就考这几个操作，练熟就行。
一、整除：谁除谁，别搞反了
先看一个符号：a | b
这玩意儿中间是一根竖线，读作"a 整除 b"。
什么意思？就是 b 可以写成 a 乘以某个整数。
2 | 6→ 对，因为 6 = 2 × 36 | 2→ 错，2 写不成 6 乘整数3 | 0→ 对，0 = 3 × 0（任何数都能整除 0）
记忆法
竖线左边是"除数"，右边是"被除数"。左边小、右边大才可能成立（除非是 0）。
这一条性质最常用
如果 c | a 且 c | b，那么 c 也能整除 a 和 b 的任意"拼凑"：
c | (sa + tb)，不管你 s、t 取什么整数。
什么意思？a 和 b 都是 c 的倍数，那它们随便乘个整数再加加减减，结果还是 c 的倍数。就跟你用乐高积木拼东西一样——积木本身是红色的，拼出来的还是红的。
例题：已知 3 | 12，3 | 21，问 3 | (5×12 - 2×21) 成不成立？
12 和 21 都是 3 的倍数。上面那条性质直接告诉你，不管前面乘什么整数，组合出来的一定还是 3 的倍数。直接验证也行：5×12 - 2×21 = 60 - 42 = 18 = 3×6，成立。
二、带余除法：余数绝对不能是负数
就是小学除法写成等式：
a = bq + r
a 是被除数，b 是除数（默认正数），q 是商，r 是余数。
唯一要死记的规矩：0 ≤ r < b。余数必须非负，且必须小于除数。
正数除法——没啥好说的
23 ÷ 5 → 23 = 5×4 + 3，商 4，余 3。检查：0 ≤ 3 < 5，合格。
负数除法——最容易翻车的地方
算 -19 除以 5。
错误写法（期末至少一半人会掉这个坑）：
-19 = 5 × (-3) + (-4) ← 余数是 -4，不合格！
正确做法：
想一个问题：比 -19 更小的、5 的倍数，最大是哪个？
5 的倍数：... -25, -20, -15, -10 ...
比 -19 小的最大 5 的倍数是 -20（= 5 × (-4)）。
-20 到 -19 差多少？差 1。所以：
-19 = 5 × (-4) + 1，商 -4，余 1。检查：0 ≤ 1 < 5 ✓
翻车重灾区
负数的带余除法，商要"往左取"（取更小的那个倍数），不是往右取。你按计算器算 -19/5 = -3.8，直觉想取 -3 就错了——必须取 -4，让余数变成正数。
三、最大公因数 gcd：辗转相除，除到余 0
gcd(a,b) 也写成 (a,b)，就是能同时整除 a 和 b 的最大正整数。
比如 gcd(60, 24) = 12，因为 12 是同时能整除 60 和 24 的最大数。
怎么求？"大 ÷ 小，余数挪下来，继续除"
这就是辗转相除法。一个例子就懂了。
求 gcd(202, 282)：
把 282 ÷ 202：
282 = 202 × 1 + 80 → 余 80
然后把上一行的除数当新的被除数，余数当新的除数：
202 = 80 × 2 + 42 → 余 42
80 = 42 × 1 + 38 → 余 38
42 = 38 × 1 + 4 → 余 4
38 = 4 × 9 + 2 → 余 2
4 = 2 × 2 + 0 → 余 0，停！
最后一个不是 0 的余数是 2，答案出来了：
gcd(202, 282) = 2
建议做题时列成表，不容易乱：
| 算式 | 余数 |
|---|---|
| 282 = 202 × 1 + 80 | 80 |
| 202 = 80 × 2 + 42 | 42 |
| 80 = 42 × 1 + 38 | 38 |
| 42 = 38 × 1 + 4 | 4 |
| 38 = 4 × 9 + 2 | 2 ← 答案 |
| 4 = 2 × 2 + 0 | 0（停） |
四、扩展欧几里得：把最大公因数"凑出来"
这是第一章最重要的计算题，也是后面 RSA 求 d、求逆元的基础。必须会。
辗转相除只能告诉你 gcd 是几。扩展欧几里得还要你找到整数 x 和 y，使得：
ax + by = gcd(a, b)
用人话说：不光知道最大公约数是几，还要用 a 和 b 把它拼出来。
例题：求 47x + 30y = gcd(47, 30) 的 x 和 y
这道题分成两段：先往下除（普通辗转相除），再往回代（扩展部分）。
第一段：往下除（跟前面一模一样）
47 = 30 × 1 + 17，把余数 17 写成 → 17 = 47 - 30×1 ①
30 = 17 × 1 + 13，把余数 13 写成 → 13 = 30 - 17×1 ②
17 = 13 × 1 + 4，把余数 4 写成 → 4 = 17 - 13×1 ③
13 = 4 × 3 + 1，把余数 1 写成 → 1 = 13 - 4×3 ④
4 = 1 × 4 + 0 → 余 0，停
最后一个非 0 余数是 1，所以 gcd(47, 30) = 1。
注意这五步里，每步我都把余数单独写成 余数 = ... 的形式——因为往回代的时候全靠它们。
第二段：往回代（倒着往上替换）
目标：把 1 表示成 47 × ? + 30 × ?。
从 ④ 开始，它最靠近 1：
1 = 13 - 4×3
式子里有 13 和 4，但我要的是 47 和 30。所以要把 4 和 13 一个个踢掉。
踢掉 4：从 ③ 知道 4 = 17 - 13×1，代入：
1 = 13 - (17 - 13×1) × 3
= 13 - 17×3 + 13×3
= 13×4 - 17×3 ← 合并 13
现在式子里是 13 和 17，继续踢。
踢掉 13：从 ② 知道 13 = 30 - 17×1，代入：
1 = (30 - 17×1) × 4 - 17×3
= 30×4 - 17×4 - 17×3
= 30×4 - 17×7 ← 合并 17
现在式子里是 17 和 30，还差一步。
踢掉 17：从 ① 知道 17 = 47 - 30×1，代入：
1 = 30×4 - (47 - 30×1) × 7
= 30×4 - 47×7 + 30×7
= 30×11 - 47×7
调整成 47x + 30y 的形式：
1 = 47 × (-7) + 30 × 11
所以 x = -7，y = 11。
验证：47×(-7) + 30×11 = -329 + 330 = 1 ✓
回代速记口诀
从最后一个有用式子出发，从后往前踢掉"中间变量"，每次只换一个。
画成图就是：
式④: 1 = 13 - 4×3
↓ 用式③换掉4
1 = 13×4 - 17×3
↓ 用式②换掉13
1 = 30×4 - 17×7
↓ 用式①换掉17
1 = 47×(-7) + 30×11 ← 搞定这跟剥洋葱一样——从最里面一层一层往外剥，剥到最后只剩下原数 47 和 30。
最容易出错的三个地方
- 忘了把每步余数写成
余数 = ...的形式——回代全靠这些等式 - 拆括号时符号搞错——尤其是减号后面有括号的情况
- 合并同类项时数错个数——建议用荧光笔把同一个变量的系数圈起来
五、最小公倍数 lcm：一条公式秒杀
最小公倍数记作 [a, b] 或 lcm(a, b)。
只需要记住这一条公式：
[a, b] = a × b / gcd(a, b)
也就是说，先算 gcd，再用乘积除以它。
例题：求 [78, 169]
先求 gcd(78, 169)：
169 = 78×2 + 13
78 = 13×6 + 0 → gcd = 13
套公式：
[78, 169] = 78 × 169 / 13 = 78/13 × 169 = 6 × 169 = 1014
六、判断素数：试到 √n 就够了
判断一个数 n 是不是素数，不需要从 2 试到 n-1，试到 √n 就行。
为什么？如果 n = a × b，a 和 b 不可能两个都比 √n 大，否则乘起来超过 n。所以只要 n 有因数，一定有一个 ≤ √n。
例题：101 是不是素数？
√101 ≈ 10.05，所以只要试到 10。
试除 2、3、5、7（10 以内的素数）：
- 2：101 奇数，不整除
- 3：1+0+1=2，不整除
- 5：个位不是 0 或 5，不整除
- 7：7×14=98，7×15=105，不整除
全不整除 → 101 是素数。
七、标准分解式：从小素数开始一直除
就是把一个数写成素数幂的乘积。做法很简单：从 2 开始，能除就除，除不动了换下一个素数。
例题：分解 1176
1176 ÷ 2 = 588 588 ÷ 2 = 294 294 ÷ 2 = 147 147 ÷ 3 = 49 49 = 7 × 7
所以 1176 = 2³ × 3 × 7²
本章做题速查表
| 看到题目里有什么 | 立刻想 |
|---|---|
a | b | b 能写成 a × 整数吗？ |
| 带余除法，被除数是负数 | 商往左取，余数要非负 |
| 求 gcd | 辗转相除，除到余 0 |
求 ax + by = gcd(a,b) | 先往下除，再往回代（扩展欧几里得） |
| 求 lcm | a×b/gcd |
| 判断素数 | 试到 √n 就行 |
| 标准分解式 | 2, 3, 5, 7...一路往下除 |
最容易翻车的地方
a | b的左右顺序：左边除右边，不是右边除左边。- 负数带余除法：商要取小（往左），让余数回到正数。
- 扩展欧几里得的符号：回代时括号前面是减号最容易算错。
- lcm 公式：别忘了先算 gcd，直接用乘积会偏大。
- 判断素数的范围：只试到 √n，不用试到 n-1。
自测题
做不出来说明前面没看懂，回去重看对应部分。
- 判断 7 | 91 是否成立。
- 求 -27 被 5 除的商和余数。
- 求 gcd(55, 85)。
- 求 gcd(368, 299, 552)。（提示：先算两个，再和第三个算）
- 求整数 x, y，使得 66x + 75y = gcd(66, 75)。
- 写出 600 的标准分解式。
- 求 lcm(49, 77)。
自测答案
- 成立，91 = 7 × 13。
- -27 = 5 × (-6) + 3，商 -6，余 3。
- gcd(55, 85) = 5。
- gcd(368, 299) = 23，gcd(23, 552) = 23，答案是 23。
- x = 8，y = -7（66×8 + 75×(-7) = 528 - 525 = 3）。
- 600 = 2³ × 3 × 5²。
- gcd(49, 77) = 7，lcm = 49×77/7 = 49×11 = 539。