Appearance
第 3 章：一次同余方程
普通方程 ax = b 你会解：两边除以 a 就完事。
同余方程 ax ≡ b (mod m) 你敢直接除吗？不敢——因为在模的世界里，"除以 a"得先问一句：a 在模 m 下有倒数吗？
这一章就是教你：什么时候能除、怎么除、除完有几个答案。
一、乘法逆元：模的世界里的"倒数"
普通数学：5 的倒数是 1/5，因为 5 × 1/5 = 1。
模的世界里不能用分数，但我们想达到同样的效果——找一个整数 b，让 a × b ≡ 1 (mod m)。这个 b 就叫 a 模 m 的乘法逆元，记作 a⁻¹ mod m。
什么时候有逆元？
gcd(a, m) = 1 时才有。不互素就没有。
这跟"整数里 0 没有倒数"是一个道理——在模的世界里，不和 m 互素的数就相当于"0"。
例题：求 40⁻¹ mod 31
40 比 31 大，先把它缩小：
40 ≡ 9 (mod 31)
所以 40⁻¹ 和 9⁻¹ 是同一个东西。问题变成：找 x 使 9x ≡ 1 (mod 31)。
数字不大，直接试乘：
9 × 7 = 63 = 31 × 2 + 1 → 63 ≡ 1 (mod 31)
所以 9⁻¹ ≡ 7，也就是 40⁻¹ ≡ 7 (mod 31)。
数字大了怎么办
直接试乘太慢的话，就用第 1 章的扩展欧几里得求 ax + my = 1，得到的 x 就是 a 的逆元。
二、一次同余方程有没有解？看这个数
方程：ax ≡ b (mod m)
有解的充要条件：
令 d = gcd(a, m)，则 d 必须整除 b。否则无解。
这是本章最核心的判断标准，背下来。做题第一件事就是算 gcd(a, m)。
例题：判断 12x ≡ 3 (mod 15) 有解吗？
gcd(12, 15) = 3。看 3 能不能整除右边 3？能 → 有解。
例题：判断 12x ≡ 1 (mod 15) 有解吗？
gcd(12, 15) = 3。3 能不能整除 1？不能 → 无解。
就这么简单。考试选择题，看到 ax ≡ b (mod m) 第一反应就是算 d = gcd(a, m)，然后看 d | b 成不成立。
三、有解的话怎么解？标准 4 步
方程：ax ≡ b (mod m)，已知 d = gcd(a, m)，且 d | b。
第 1 步：三处（a、b、m）同时除以 d，得到
a'x ≡ b' (mod m')
其中 a' = a/d，b' = b/d，m' = m/d。
第 2 步：在新模数 m' 下求 a' 的逆元 (a')⁻¹。
第 3 步：方程两边同乘这个逆元，直接得到
x ≡ b' × (a')⁻¹ (mod m')
第 4 步：把这个解扩展到原模数 m。因为除以 d 时丢掉了 d-1 个解，所以要补回来：
x ≡ x₀, x₀+m', x₀+2m', ..., x₀+(d-1)m' (mod m)
一共 d 个解。
完整例题：解 91x ≡ 35 (mod 133)
第 1 步：算 d。
辗转相除 133 和 91：
133 = 91×1 + 42 91 = 42×2 + 7 42 = 7×6 + 0
所以 d = gcd(91, 133) = 7。
检查：7 | 35？35 = 7×5，能整除 → 有解，且一共有 7 个解。
第 2 步：三处同除以 7。
91x ≡ 35 (mod 133) → 13x ≡ 5 (mod 19)
为什么模数也除以 7？因为原方程意思是 133 | (91x - 35)，即 91x - 35 = 133k。两边都有公因数 7，约掉：13x - 5 = 19k，所以模 19。
第 3 步：在模 19 下求 13 的逆元。
试乘：13×3 = 39 = 19×2 + 1 → 13⁻¹ ≡ 3 (mod 19)。
两边乘 3：
x ≡ 5×3 = 15 (mod 19)
第 4 步：回到模 133。d = 7，所以要列 7 个解：
x = 15 + 19t，t = 0, 1, 2, 3, 4, 5, 6
| t | x = 15 + 19t |
|---|---|
| 0 | 15 |
| 1 | 34 |
| 2 | 53 |
| 3 | 72 |
| 4 | 91 |
| 5 | 110 |
| 6 | 129 |
答案：
x ≡ 15, 34, 53, 72, 91, 110, 129 (mod 133)
四、系数里带大指数的——先把系数变小
有些题长这样：
12 × 7¹⁶⁸ x ≡ 9 (mod 27)
看着吓人，但本质还是 系数 × x ≡ 右边。所以先把系数在模 m 下化小，就变回上一节的题了。
例题：解 12 × 7¹⁶⁸ x ≡ 9 (mod 27)
第一步：把系数 12 × 7¹⁶⁸ mod 27 化小。
先处理 7¹⁶⁸ mod 27：
gcd(7, 27) = 1，欧拉定理。φ(27) = 27 × (1 - 1/3) = 18。
所以 7¹⁸ ≡ 1 (mod 27)。
168 = 9×18 + 6，所以：
7¹⁶⁸ = (7¹⁸)⁹ × 7⁶ ≡ 1⁹ × 7⁶ ≡ 7⁶ (mod 27)
算 7⁶：
7² = 49 ≡ 22 7³ = 22×7 = 154 ≡ 19 7⁶ = (7³)² = 19² = 361 ≡ 10 (mod 27)
所以 7¹⁶⁸ ≡ 10 (mod 27)。
第二步：代回原方程。
12 × 10 x ≡ 9 → 120x ≡ 9 (mod 27)
120 ≡ 12 (mod 27) → 12x ≡ 9 (mod 27)
第三步：解普通同余方程。
gcd(12, 27) = 3，3 | 9 ✓。三处同除以 3：
4x ≡ 3 (mod 9)
4⁻¹ mod 9：4×7 = 28 ≡ 1，所以 4⁻¹ ≡ 7。
x ≡ 3×7 = 21 ≡ 3 (mod 9)
第四步：回到模 27。d = 3，3 个解：
x = 3, 12, 21 (mod 27)
答案：x ≡ 3, 12, 21 (mod 27)。
五、中国剩余定理（CRT）：把几个方程合并成一个
你遇到这种题：
x ≡ 2 (mod 5) x ≡ 5 (mod 11) x ≡ 3 (mod 17)
三个方程，模数两两互素。CRT 告诉你：一定有唯一解（模 5×11×17 = 935 意义下）。
解法：一次合并两个，逐步吃掉所有方程，像滚雪球一样。
手把手 CRT 例题
题目：
x ≡ 2 (mod 5) x ≡ 5 (mod 11) x ≡ 3 (mod 17)
第一步：从第一个方程写出 x 的通式。
x = 2 + 5t（t 是任意整数）
第二步：把这个通式塞进第二个方程。
2 + 5t ≡ 5 (mod 11) 5t ≡ 3 (mod 11)
求 5⁻¹ mod 11：5×9 = 45 ≡ 1，所以 5⁻¹ ≡ 9。
t ≡ 3×9 = 27 ≡ 5 (mod 11)
所以 t = 5 + 11k。
第三步：代回 x = 2 + 5t。
x = 2 + 5(5 + 11k) = 2 + 25 + 55k = 27 + 55k
这一步合并完成后，前两个方程等价于：
x ≡ 27 (mod 55)
搞定了前两个，现在还剩第三个。
第四步：把 x = 27 + 55k 塞进第三个方程。
27 + 55k ≡ 3 (mod 17)
先化简模 17：
27 ≡ 10 (mod 17) 55 ≡ 4 (mod 17)
所以：
10 + 4k ≡ 3 (mod 17) 4k ≡ 3 - 10 = -7 ≡ 10 (mod 17)
4⁻¹ mod 17：4×13 = 52 ≡ 1，所以 4⁻¹ ≡ 13。
k ≡ 10×13 = 130 ≡ 11 (mod 17)（130 = 17×7 + 11）
第五步：回代到 x = 27 + 55k。
取 k = 11：
x = 27 + 55×11 = 27 + 605 = 632
模 5×11×17 = 935，所以：
x ≡ 632 (mod 935)
验证可以自己验算：632 mod 5 = 2 ✓，632 mod 11 = 5 ✓，632 mod 17 = 3 ✓。
CRT 口诀
写出通式 → 代入下一个方程 → 解出参数 → 写回 x → 继续代入下一个。
就像吃薯片，一片一片来。
六、方程要先"预处理"才能用 CRT
有些题不是直接给 x ≡ 几，而是：
5x ≡ 3 (mod 17) 4x ≡ 6 (mod 11)
做法：先把每个小方程解成 x ≡ 常数的形式，再用 CRT 合并。
例题
第 1 个方程：5x ≡ 3 (mod 17)
5⁻¹ mod 17：5×7 = 35 ≡ 1，所以 5⁻¹ ≡ 7。
x ≡ 3×7 = 21 ≡ 4 (mod 17)
第 2 个方程：4x ≡ 6 (mod 11)
4⁻¹ mod 11：4×3 = 12 ≡ 1，所以 4⁻¹ ≡ 3。
x ≡ 6×3 = 18 ≡ 7 (mod 11)
现在变成标准 CRT：
x ≡ 4 (mod 17)，x ≡ 7 (mod 11)
从第一个：x = 4 + 17t。代入第二个：
4 + 17t ≡ 7 (mod 11) 17 ≡ 6 (mod 11)，所以 4 + 6t ≡ 7 → 6t ≡ 3 (mod 11)
6⁻¹ mod 11：6×2 = 12 ≡ 1，所以 6⁻¹ ≡ 2。
t ≡ 3×2 = 6 (mod 11)
取 t = 6：x = 4 + 17×6 = 4 + 102 = 106。
模 17×11 = 187，所以：
x ≡ 106 (mod 187)
七、二元一次同余方程组
和普通二元一次方程组一模一样的手法，只是每一步都在模 m 下做。消元法最好用。
例题
3x + y ≡ 7 (mod 23) x + 2y ≡ 6 (mod 23)
从第一个方程把 y 表示出来：
y ≡ 7 - 3x (mod 23)
代入第二个：
x + 2(7 - 3x) ≡ 6 x + 14 - 6x ≡ 6 -5x + 14 ≡ 6 -5x ≡ -8 (mod 23)
两边乘 -1：
5x ≡ 8 (mod 23)
5⁻¹ mod 23：5×14 = 70 = 23×3 + 1，所以 5⁻¹ ≡ 14。
x ≡ 8×14 = 112 ≡ 20 (mod 23)（112 = 23×4 + 20）
回代求 y：
y ≡ 7 - 3×20 = 7 - 60 = -53 (mod 23)
-53 往 23 的倍数上靠：-53 + 23 = -30，+23 = -7，+23 = 16。
y ≡ 16 (mod 23)
答案：x ≡ 20，y ≡ 16 (mod 23)。
本章做题速查表
| 看到什么 | 立刻想 |
|---|---|
| 求 a⁻¹ mod m | 先看 gcd(a,m)=1？然后试乘或用扩展欧几里得 |
| 判断 ax ≡ b 有解 | 算 d=gcd(a,m)，看 d|b |
| 解 ax ≡ b | 除以 d → 求 a' 的逆元 → 两边乘 → 扩展回原模数 |
| 系数里有大指数 | 用费马/欧拉先把系数化小 |
| 同余方程组（x ≡ 常数） | CRT：逐个合并 |
| 同余方程组（ax ≡ 常数） | 先解成 x ≡ 常数，再 CRT |
| 二元同余组 | 和普通消元一样，只是每步 mod m |
最容易翻车的地方
- 忘了检查有解条件：上来就解，白算半天才发现无解。第一步一定要算 d = gcd(a, m)。
- 除以 d 时忘了除模数：a 和 b 除了，m 也一定要除。
- 解出 x₀ 后忘了加模数的倍数：一共有 d 个解，不是一个！x₀ + m'×t，t = 0, 1, ..., d-1。
- CRT 代入时忘了对模数取余化简：比如 27 代入 mod 17 时应该先化成 10。
- 逆元算对了但乘错了方向：记住是两边同时乘 a' 的逆元，左边变成 x。
自测题
- 求 7⁻¹ mod 26。
- 判断 12x ≡ 4 (mod 15) 有解吗？
- 解 91x ≡ 35 (mod 161)。
- 解方程组：x ≡ 1 (mod 3)，x ≡ 2 (mod 5)。
- 解方程组：5x ≡ 3 (mod 17)，4x ≡ 6 (mod 11)。
自测答案
- 7×15 = 105 = 26×4 + 1，所以 7⁻¹ ≡ 15 (mod 26)。
- gcd(12, 15) = 3，3 不整除 4 → 无解。
- gcd(91, 161) = 7，7 | 35 ✓。除以 7 得 13x ≡ 5 (mod 23)，13⁻¹ ≡ 16，x ≡ 5×16 = 80 ≡ 11 (mod 23)。d=7，7 个解：x ≡ 11, 34, 57, 80, 103, 126, 149 (mod 161)。
- x = 1 + 3t，代入 mod 5：1 + 3t ≡ 2 → 3t ≡ 1 → t ≡ 2 (mod 5)。x = 1 + 3×2 = 7 (mod 15)。
- x ≡ 106 (mod 187)。