Appearance
第 4 章：二次同余
先从一道题开始：
判断 x² ≡ 111 (mod 373) 有没有解。
你第一反应肯定是：那我试试 x = 0, 1, 2, ..., 372 呗，不就三百多次——
但如果是模 2011 呢？模一个大素数呢？试到天亮也试不完。
这一章的所有工具——勒让德符号、二次互反律、雅可比符号——终极目标只有一个：
不用解方程，就能快速判断 x² ≡ a (mod m) 有没有解。
一、平方剩余：一个"平方数能余出谁"的清单
如果存在 x 使得 x² ≡ a (mod m)，就说 a 是模 m 的平方剩余。不存在，就是平方非剩余。
小模数直接暴力列出所有平方数，一看便知。
例题：4 是模 7 的平方剩余吗？
把 0 到 6 全平方一遍，模 7：
| x | x² | mod 7 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 4 | 4 ← 出现了！ |
| 3 | 9 | 2 |
| 4 | 16 | 2 |
| 5 | 25 | 4 |
| 6 | 36 | 1 |
结果里有 4（x=2 和 x=5 都能搞出 4），所以 4 是平方剩余，而且方程 x² ≡ 4 (mod 7) 的解是 x ≡ 2 或 5。
TIP
模 p 下，非零的平方剩余恰好占一半（(p-1)/2 个），平方非剩余也占一半。所以随便猜也有 50% 正确率——但你做题不能靠猜。
二、勒让德符号 (a/p)：一个"有解/无解"判断器
当 p 是奇素数、且 a 不是 p 的倍数时，用符号 (a/p) 表示：
(a/p) = 1 → a 是平方剩余 → 有解 (a/p) = -1 → a 是平方非剩余 → 无解
它就是一个人造的"开关"，只输出 1 或 -1。
欧拉判别法：怎么算出这个符号？
(a/p) ≡ a^((p-1)/2) (mod p)
算出来是 1 就是 1，算出来是 p-1 就是 -1（因为在模 p 下，-1 ≡ p-1）。
但别急着去算大幂——下面这些公式能帮你绕开大部分计算。
三、三条"直接出答案"的公式
这几条是做题的最高频工具，背下来：
公式 1：符号能拆
(ab/p) = (a/p) × (b/p)
上面是乘积就能拆开。比如 (6/p) = (2/p) × (3/p)，拆开分别判断。
公式 2：( -1/p ) 只和 p 模 4 有关
p ≡ 1 (mod 4) → (-1/p) = 1 p ≡ 3 (mod 4) → (-1/p) = -1
一句话：p 除 4 余 1 就是 1，余 3 就是 -1。
公式 3：( 2/p ) 只和 p 模 8 有关
p ≡ 1 或 7 (mod 8) → (2/p) = 1 p ≡ 3 或 5 (mod 8) → (2/p) = -1
一句话：p 除 8 余 1 或 7 → 1；余 3 或 5 → -1。
这两条出现频率极高。因为很多数分解后都会冒出 -1 和 2。
四、二次互反律：把大数翻到下面去
核心作用：把 (大素数/小素数) 翻成 (小素数/大素数)，然后大数对小素数取余变小，反复迭代到能直接判断。
规则就一条（用"双双三"口诀）：
"双双三，要翻脸"——两个素数都是 3 mod 4 时，交换上下位置要变号；其他情况不变号。
| p 和 q 的情况 | (p/q) 和 (q/p) 的关系 |
|---|---|
| 至少一个 ≡ 1 (mod 4) | (p/q) = (q/p)，不变号 |
| 两个都 ≡ 3 (mod 4) | (p/q) = -(q/p)，变号 |
五、完整实战：计算 (151/373)
这是期末必考题。跟一遍就懂了。
题目：计算勒让德符号 (151/373)。
两个都是奇素数，可以用互反律。
Round 1：看模 4。
- 151 ÷ 4 余 3
- 373 ÷ 4 余 1
至少一个 1 mod 4 → 不变号。
(151/373) = (373/151) ← 交换，不翻脸
Round 2：把上面的大数模下面变小。
373 ÷ 151 = 2 余 71，所以：
(373/151) = (71/151)
Round 3：继续互反律交换。
- 71 ÷ 4 余 3
- 151 ÷ 4 余 3
两个都 3 mod 4 → "双双三，要翻脸"，变号！
(71/151) = - (151/71)
Round 4：把 151 模 71 变小。
151 ÷ 71 = 2 余 9，所以：
(151/71) = (9/71)
现在：- (151/71) = - (9/71)。
Round 5：9 是完全平方数！
9 = 3²。一个平方数在奇素数模下，只要和模数互素，勒让德符号就是 1。
(9/71) = 1
往回收：
(151/373) = (373/151) （Round 1） = (71/151) （Round 2） = - (151/71) （Round 3，翻脸！） = - (9/71) （Round 4） = -1 （Round 5）
答案：(151/373) = -1。151 是模 373 的平方非剩余。
做题时的思路总结
整个过程就是循环做两件事：
① 上面大了 → 对下面取余变小② 上下换位 → 看要不要变号（双双三才变）
一直循环到上面的数变成 -1、2、或完全平方数，就能直接出结果。
六、判断 x² ≡ a (mod p) 有没有解——一条龙例题
题目：判断 x² ≡ 111 (mod 71) 有解吗？
模数 71 是素数，问题等价于算 (111/71)。
第一步：把 111 模 71 变小。
111 - 71 = 40，所以 (111/71) = (40/71)
第二步：拆 40。
40 = 8 × 5 = 2³ × 5
(40/71) = (2/71)³ × (5/71)
第三步：(2/71) 用公式 3。
71 ÷ 8 余 7 → (2/71) = 1
所以 (2/71)³ = 1³ = 1。
第四步：(5/71) 用互反律。
5 ≡ 1 (mod 4)，所以和 71 交换不变号。
(5/71) = (71/5) ← 71 mod 5 = 1，所以 (71/5) = (1/5)
任何数的 (1/p) 都等于 1（因为 1 是完全平方数 1²）。
所以 (5/71) = 1。
第五步：合并。
(40/71) = 1³ × 1 = 1
答案：有解（具体 x 是几不用求，题目只问有没有）。
七、雅可比符号：下面不是素数怎么办
勒让德符号要求下面必须是奇素数。如果下面是合数，比如 (38/385)，就要用雅可比符号。
做法：把下面分解成素数，拆开各自算勒让德符号，再乘起来。
如果 n = p₁ᵃ¹ × p₂ᵃ² × ...，那么：
(a/n) = (a/p₁)ᵃ¹ × (a/p₂)ᵃ² × ...
⚠️ 雅可比符号最大的坑
| 雅可比符号的值 | 含义 |
|---|---|
| (a/n) = -1 | 方程 x² ≡ a (mod n) 一定无解 |
| (a/n) = 1 | 不一定有解！还要继续检查！ |
这跟勒让德符号不一样。勒让德符号为 1 就肯定有解，雅可比符号为 1 只是"有可能有解"。期末判断题百分之百会考这个区别。
八、合数模下怎么判定：拆开来分别看
判断 x² ≡ a (mod m)，m 是合数：
把 m 分解成素数幂 → 每个素数模下分别判断 → 全都有解原方程才有解。
只要拆出来的方程有一个无解，就全部无解。
例题：判断 x² ≡ 99 (mod 323) 有解吗？
第一步：分解模数。
323 = 17 × 19
第二步：拆成两个方程。
x² ≡ 99 (mod 17) x² ≡ 99 (mod 19)
第三步：先看模 17。
99 ÷ 17 = 5 余 14，所以是 x² ≡ 14 (mod 17)
要判断 (14/17)。
14 = 2 × 7 (14/17) = (2/17) × (7/17)
(2/17)：17 ÷ 8 余 1 → (2/17) = 1。
(7/17)：7 ≡ 3 (mod 4)，17 ≡ 1 (mod 4) → 交换不变号：
(7/17) = (17/7) = (3/7)
模 7 的平方剩余是 {1, 2, 4}，3 不在里面 → (3/7) = -1。
所以 (14/17) = 1 × (-1) = -1 → 模 17 下无解。
第四步：下结论。
有一个子方程无解，原方程直接判死刑——x² ≡ 99 (mod 323) 无解。不用再看模 19 了。
九、前面带系数的二次同余
有些题不是标准的 x² ≡ a，而是：
11x² ≡ -3 (mod 91)
做法：把系数消掉——两边同乘系数的逆元，变回标准形式。
例题：判断 11x² ≡ -3 (mod 91) 有解吗？
第一步：消掉 11。
求 11⁻¹ mod 91：
91 = 11×8 + 3 11 = 3×3 + 2 3 = 2×1 + 1
回代得 1 = 91×4 - 11×33，所以 11×(-33) ≡ 1 (mod 91)。
-33 ≡ 58 (mod 91)，所以 11⁻¹ ≡ 58。
第二步：两边乘 58。
x² ≡ -3 × 58 = -174 (mod 91)
取模：-174 + 91 = -83，+91 = 8。
所以变成：x² ≡ 8 (mod 91)
第三步：分解模数。
91 = 7 × 13
需要同时有解：
x² ≡ 8 (mod 7)：8 ≡ 1，x² ≡ 1 肯定有解 ✓
x² ≡ 8 (mod 13)：判断 (8/13)
(8/13) = (2/13)³。13 ÷ 8 余 5 → (2/13) = -1。(-1)³ = -1 → 模 13 下无解 ✗
结论：原方程无解。
本章做题速查表
| 看到什么 | 立刻想 |
|---|---|
| 小模数判断平方剩余 | 直接列出所有平方数 |
| p 是奇素数，判断 (a/p) | 勒让德符号；a 先对 p 取余变小 |
| 上面是乘积 | (ab/p) = (a/p)(b/p)，拆开 |
| 上面出现 -1 或 2 | 专用公式（看 p mod 4 或 p mod 8） |
| 上下都是大素数 | 二次互反律：交换 + "双双三翻脸" |
| 下面是非素数 | 雅可比符号：分解下面再拆开 |
| 雅可比符号 = 1 | 不能直接说有解！（和勒让德不一样） |
| 模数是合数 | 分解模数 → 每个素因子分别判断 |
| 前面有系数 | 两边乘系数的逆元，变成标准形式 |
最容易翻车的地方
- 雅可比符号 = 1 不等于有解。这是期末判断/选择题的头号考点。雅可比符号 = -1 才能拍板说无解；= 1 只能说"还不确定"。
- 二次互反律忘了看符号。两个都是 3 mod 4 一定要变号，漏一次整个结果反了。
- 拆合数模时只看了勒让德符号。比如 n = pq，雅可比 (a/n) = 1 不代表两个子方程都有解，要分开算勒让德。
- 上面的大数忘了先取余。比如 (111/71)，111 先 mod 71 变成 40，别直接用 111。
- 连乘时忘了某一步变号或漏了 (2/p) 的处理。建议每一步写清楚，别跳。
自测题
- 4 是模 7 的平方剩余吗？
- 判断 x² ≡ 111 (mod 71) 有解吗？
- 判断 x² ≡ 360 (mod 2011) 有解吗？
- 判断 x² ≡ 99 (mod 323) 有解吗？
- 计算 (151/373)。
自测答案
- 是（2² = 4 mod 7）。
- 有解（(111/71) = 1）。
- 无解（(360/2011) = -1）。
- 无解（模 17 下 (14/17) = -1）。
- (151/373) = -1。