Appearance
第 1 章：整数的可除性
这一章说到底是三件事：
能不能除尽？除不尽的话余多少？两个数的最大公约数怎么凑出来？
考试翻来覆去就考这几个操作，尤其是最后的“凑最大公约数”，是后面学密码学（如 RSA 算法）的地基。练熟就行！
一、整除：谁除谁，别搞反了
先看一个符号：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 的倍数。就跟你用乐高积木拼东西一样——积木本身是红色的，拼出来的还是红的。
二、带余除法：余数绝对不能是负数
就是小学除法写成等式：
a = bq + r
a 是被除数，b 是除数（默认正数），q 是商，r 是余数。 唯一要死记的规矩：0 ≤ r < b。余数必须非负，且必须小于除数。
负数除法——期末连环翻车重灾区
算 -19 除以 5。
错误写法（期末至少一半人会掉这个坑）：
-19 = 5 × (-3) + (-4) ← 余数是 -4，不合格！
正确做法：
考场口诀：商往小了取（数轴向左看），余数自然正
你按计算器算 -19 ÷ 5 = -3.8。 想象一下数轴，-3.8 左边的整数是谁？是 -4！ 所以商就是 -4。 算余数：-19 - 5×(-4) = -19 + 20 = 1。
等式：-19 = 5 × (-4) + 1。检查：0 ≤ 1 < 5 ✓ :::
三、最大公因数 gcd 与“互素”
gcd(a,b) 也写成 (a,b)，就是能同时整除 a 和 b 的最大正整数。 注意：最大公因数永远是正的！如果考你 gcd(-252, 198)，直接把负号扔掉，等于 gcd(252, 198)。
怎么求？辗转相除法：“大 ÷ 小，余数挪下来，继续除”
求 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 ← 最后一个非0余数，就是答案 |
| 4 = 2 × 2 + 0 | 0（停） |
所以 gcd(202, 282) = 2。
整个密码学的核心概念：互素（互质）
如果 gcd(a, b) = 1，我们就说 a 和 b 互素。 只要两个数互素，它们就能通过加减乘除变出“1”。这是后面求“乘法逆元”的绝对前提！
四、扩展欧几里得：把最大公约数“凑出来”
这是第一章最重要的计算题，必考！ 题目不光要你知道最大公约数是几，还要你找到整数 x 和 y，使得：
ax + by = gcd(a, b)
例题：求 47x + 30y = gcd(47, 30) 的 x 和 y。
这里提供两种方法，大家可以根据习惯任选其一：
方法一：传统回代法（像剥洋葱）
分成两段：先往下除（普通辗转相除），再往回代（扩展部分）。
第一段：往下除，并把余数单独写在左边
47 = 30 × 1 + 17 → 17 = 47 - 30×1 ①
30 = 17 × 1 + 13 → 13 = 30 - 17×1 ②
17 = 13 × 1 + 4 → 4 = 17 - 13×1 ③
13 = 4 × 3 + 1 → 1 = 13 - 4×3 ④
4 = 1 × 4 + 0 → 余 0，停
第二段：倒着往回代（每次只替换一个数） 目标是把 1 拼凑成 47 和 30。从最后一个非零余数 ④ 开始：
1 = 13 - 4×3
= 13 - (17 - 13×1) × 3 ← 用 ③ 换掉 4，并合并 13
= 13×4 - 17×3
= (30 - 17×1) × 4 - 17×3 ← 用 ② 换掉 13，并合并 17
= 30×4 - 17×7
= 30×4 - (47 - 30×1) × 7 ← 用 ① 换掉 17，并合并 30
= 30×11 - 47×7
调整成 47x + 30y 的形式：1 = 47 × (-7) + 30 × 11 所以 x = -7，y = 11。
方法二：考场开挂列表法（防手残推荐）
回代法拆括号极其容易算错正负号。强烈建议在考场上用表格法，从上往下算，绝不翻车！
规则：
- 前两行写死：第一行写大数 47，设 x=1, y=0；第二行写小数 30，设 x=0, y=1。
- 从第三行开始：当前行 = 上上行 - 商 × 上一行（商就是普通的辗转相除的商）
| 行号 | 商 q | 余数 r | x | y | 这是怎么算的？（考场不用写这列） |
|---|---|---|---|---|---|
| -1 | 无 | 47 | 1 | 0 | (初始化写死) |
| 0 | 无 | 30 | 0 | 1 | (初始化写死) |
| 1 | 1 | 17 | 1 | -1 | r: 47 - 1×30 = 17 x: 1 - 1×0 = 1 y: 0 - 1×1 = -1 |
| 2 | 1 | 13 | -1 | 2 | r: 30 - 1×17 = 13 x: 0 - 1×1 = -1 y: 1 - 1×(-1) = 2 |
| 3 | 1 | 4 | 2 | -3 | r: 17 - 1×13 = 4 x: 1 - 1×(-1) = 2 y: -1 - 1×2 = -3 |
| 4 | 3 | 1 | -7 | 11 | r: 13 - 3×4 = 1 x: -1 - 3×2 = -7 y: 2 - 3×(-3) = 11 |
当余数 r 算到最大公约数（这里是 1）时，直接看最后一行，答案出来了：
x = -7，y = 11
验证：47×(-7) + 30×11 = -329 + 330 = 1 ✓
五、最小公倍数 lcm：一条公式秒杀
最小公倍数记作 [a, b] 或 lcm(a, b)。 只需要记住这一条公式：
[a, b] = (a × b) / gcd(a, b)
也就是说，先算 gcd，再用乘积除以它。
例题：求 [78, 169] 先求 gcd(78, 169) = 13 套公式：[78, 169] = 78 × 169 / 13 = 6 × 169 = 1014
六、判断素数：试到 √n 就够了
判断一个数 n 是不是素数，试到 √n 就行。 因为如果 n = a × b，a 和 b 不可能两个都比 √n 大。
例题：101 是不是素数？ √101 ≈ 10.05，所以只要试到 10 以内的素数（2, 3, 5, 7）。 全不整除 → 101 是素数。
七、标准分解式：从小素数开始一直除
做法：从 2 开始，能除就除，除不动了换下一个素数。
例题：分解 1176 1176 ÷ 2 = 588 → ÷ 2 = 294 → ÷ 2 = 147 → ÷ 3 = 49 = 7 × 7 所以 1176 = 2³ × 3 × 7²
🚀 本章做题速查表（考前 5 分钟必看）
| 看到题目里有什么 | 立刻想 |
|---|---|
a | b | b 能写成 a × 整数吗？（左小右大） |
| 被除数是负数 | 计算器算完商往左看，余数必须正！ |
| 求 gcd | 辗转相除，除到余 0。如果是负数直接扔掉负号。 |
求 ax + by = gcd(a,b) | 扩展欧几里得，推荐画表格从上往下算。 |
| 题目说“两者互素” | 它们的 gcd 是 1，存在 ax + by = 1。 |
| 求 lcm | a×b / gcd |
| 判断素数 | 试除到 √n 就行 |
☠️ 历年期末最容易翻车的地方
- 负数带余除法：算出个负的余数，整道题直接 0 分。记住商往数轴左边取。
gcd(-a, b)：最大公约数不可能有负数！自带的负号直接当没看见。- 扩展欧几里得符号算错：用传统回代法拆括号时，减号后面特别容易算错，算完务必验算一遍。
- lcm 公式：别忘了先算 gcd，直接把两个数乘起来会偏大。
自测题（满分过关才能看下一章）
- 判断 7 | 91 是否成立。
- 求 -27 被 5 除的商和余数。（避坑测试）
- 求 gcd(-55, 85)。（避坑测试）
- 求 gcd(368, 299, 552)。（提示：先算两个，再和第三个算）
- 求整数 x, y，使得 66x + 75y = gcd(66, 75)。
- 求 lcm(49, 77)。
自测答案
- 成立，91 = 7 × 13。
- 计算器 -27/5 = -5.4，数轴向左取商为 -6。余数 = -27 - 5×(-6) = 3。
- 负号扔掉，求 gcd(55, 85) = 5。
- gcd(368, 299) = 23，gcd(23, 552) = 23，答案是 23。
- gcd(66, 75) = 3。可得 x = 8，y = -7。（验证：66×8 + 75×(-7) = 528 - 525 = 3）。
- gcd(49, 77) = 7，lcm = 49×77/7 = 49×11 = 539。