Appearance
第 4 章：二次同余
先从一道题开始：
判断
x² ≡ 111 (mod 373)有没有解。
你第一反应肯定是：那我试试 x = 0, 1, 2, ..., 372 呗，总能试出来。 但如果是模 2011 呢？如果是模一个极大的数呢？试到天亮也试不完。
这一章所有的花里胡哨（勒让德符号、二次互反律、雅可比符号），终极目标只有一个：
不用解出 x 是几，就能一眼看穿
x² ≡ a (mod m)到底有没有解！
一、平方剩余：谁有资格在模 m 下当个“平方数”
如果在模 m 的世界里，存在一个数 x 让 x² ≡ a (mod m)，我们就说 a 是模 m 的平方剩余（即 a 有资格当平方数）。不存在，就叫平方非剩余。
小模数怎么看？直接暴力算！ 例题：4 是模 7 的平方剩余吗？ 把 0 到 6 全平方一遍：1²=1, 2²=4, 3²=2, 4²=2, 5²=4, 6²=1。 结果里出现了 4（x=2 和 x=5 都能搞出 4），所以 4 是模 7 的平方剩余。
考试常识
在奇素数 p 的模下，非零的平方剩余恰好占一半（(p-1)/2 个），平方非剩余也占一半。 如果是大模数，绝不能暴力试，必须用下面的“检测仪器”。
二、勒让德符号 (a/p)：有解无解的“扫描仪”
当 p 是奇素数、且 a 不是 p 的倍数时，我们引入一个符号 (a/p)，它就是个扫描仪，只输出两个结果：
(a/p) = 1 → a 是平方剩余 → 有解！(a/p) = -1 → a 是平方非剩余 → 无解！
怎么算出这个 1 或 -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 ≡ 3 (mod 4) → 结果是 -1(口诀：余 1 就是 1，余 3 就是负 1)
公式 3：( 2 / p ) 的判定 —— 看 p 除以 8
p ≡ 1 或 7 (mod 8) → 结果是 1 p ≡ 3 或 5 (mod 8) → 结果是 -1(口诀：一七得正，三五成负)
三、二次互反律：把大数翻到下面去
如果上下两个都是大素数，比如 (151/373)，公式判定不了怎么办？ 二次互反律允许你把它们上下颠倒变成 (373/151)，然后让上面的大数对下面的小数取余数，数字就变小了！
颠倒时的符号规则只有一条，请默念口诀：
🚨 “双双三，要翻脸！”
什么意思？
- 看看 p 和 q 除以 4 余几。
- 如果两个数除以 4 都余 3，那么交换上下位置时，前面必须加个负号！
- 其他所有情况（只要有一个余 1），交换时不加负号，直接翻。
四、勒让德计算标准操作：无脑三板斧
遇到求 (a/p)，反复循环以下“三板斧”，直到变成 ±1。
- 第一斧【上大化小】：如果上面的数比下面大，直接求余数。(如 373/151 变成 71/151)
- 第二斧【合数拆开】：如果上面的数是合数，分解成质数乘积，用公式1拆开。(如 40 拆成 8×5)
- 第三斧【素数翻转】：如果上面也是素数，直接用“互反律”颠倒，大数换到上面继续砍第一斧！(注意双双三要变号)
完整实战：计算 (151 / 373) （期末必考题）
Round 1（素数翻转）：两个都是素数，用互反律颠倒。 151 和 373 除以 4 都不是余 3（373余1，151余3），不满足“双双三”，不变号：
(151/373) = (373/151)
Round 2（上大化小）：上面的 373 大了，对 151 取余数（373 = 151×2 + 71）：
(373/151) = (71/151)
Round 3（素数翻转）：两个又是素数。 71÷4余3，151÷4也余3。双双三，翻脸！加负号！
(71/151) = - (151/71)
Round 4（上大化小）：151 对 71 取余数（151 = 71×2 + 9）：
- (151/71) = - (9/71)
Round 5（合数拆开/找平方）：9 是 3²，是一个完全平方数。 完全平方数在勒让德符号里永远是 1！
- (9/71) = - 1
结论：算出来是 -1，说明 151 是模 373 的平方非剩余，方程 x² ≡ 151 (mod 373) 无解。
五、判断 x² ≡ a (mod p) 有没有解的综合例题
题目：判断 x² ≡ 111 (mod 71) 有解吗？（71是素数） 问题等价于算 (111 / 71)。
- 上大化小：111 模 71 余 40 →
(40/71) - 合数拆开：40 = 8 × 5 = 2³ × 5 →
(2/71)³ × (5/71) - 公式判定：算
(2/71)。71÷8余7，用公式3，(2/71) = 1。所以1³ = 1。 - 素数翻转：算
(5/71)。5÷4余1，非双双三，直接翻转 →(71/5)。 - 上大化小：71 模 5 余 1 →
(1/5)。1 是平方数，结果为 1。 - 合并：
1³ × 1 = 1。
结论：算出来是 1，所以有解！
六、如果模数 m 是合数怎么办？（期末第一大坑）
前面所有的公式和定理，前提都是模数（也就是下面的数）必须是奇素数！ 如果考题出了个合数，比如 x² ≡ 99 (mod 323)，怎么判定？
☠️ 史诗级翻车警告：雅可比符号的谎言
书上教了一个“雅可比符号”，允许下面的数是合数。 但是！雅可比符号算出来 = 1，不代表方程一定有解！ 雅可比 = -1，绝对无解；但雅可比 = 1，可能是无解的！(期末判断题一定会考这句话！)
正确的满分解题套路： 遇到合数模，先把它打碎成素数，各自算勒让德符号！只要有一个无解，原方程就死刑无解！
满分例题演示：判断 x² ≡ 99 (mod 323) 有解吗？
第一步：分解模数 323 = 17 × 19。 第二步：把原方程拆成两个素数模的子方程。
子方程A：
x² ≡ 99 (mod 17)子方程B：x² ≡ 99 (mod 19)
第三步：挨个判定。先看子方程 A。 上大化小：99 模 17 余 14。判断 (14/17)。 合数拆开：14 = 2 × 7，所以 (14/17) = (2/17) × (7/17)
(2/17)：17÷8余1，公式得 1。(7/17)：7÷4余3，17÷4余1，非双双三，直接翻转得(17/7)。17模7余3，即(3/7)。由于 7 模 8 不是啥特殊值，接着翻：3和7都是除4余3，**双双三翻脸！**得-(7/3)，即-(1/3)= -1。 所以(14/17) = 1 × (-1) = -1。
第四步：下结论。 子方程 A 算出 -1，模 17 下无解！ 一票否决，原方程 x² ≡ 99 (mod 323) 绝对无解！不用再看 19 了。
七、带系数的二次方程怎么做？
有些题不长 x² 的样子，比如：
11 x² ≡ -3 (mod 91)
做法：跟第 3 章一样，先用逆元把系数 11 杀掉，变成纯净版！
实战演示：
- 算 11 在模 91 下的逆元（用神奇表格法算出是 58）。
- 两边同乘 58：
x² ≡ -3 × 58 = -174 (mod 91)。 - 把负数化正：
-174 ≡ 8 (mod 91)。 - 方程变成了标准的：
x² ≡ 8 (mod 91)。 - 因为 91 = 7 × 13（合数模），按照上一节的套路拆成 mod 7 和 mod 13 分别判定勒让德即可。
🚀 本章做题速查表（考前 5 分钟必看）
| 遇到什么情况 | 你该怎么做 |
|---|---|
| 求 (-1 / p) | 看 p 模 4。余 1 为 1，余 3 为 -1。 |
| 求 (2 / p) | 看 p 模 8。余 1,7 为 1，余 3,5 为 -1。 |
| 求 (大素数 / 小素数) | 先上大化小，求余数。 |
| 求 (小素数 / 大素数) | 二次互反律翻过去！注意双双三翻脸（加负号）。 |
| 判断合数模有没有解 | 必须把模数分解成素数，对每个素因子算勒让德。全为1才有解。 |
| 雅可比符号算出为 1 | 不一定有解！ 这可能是个假象，只能说明判定失败，仍需拆分素数模。 |
☠️ 历年期末最惨烈翻车现场
- 二次互反律忘了看负号：两个都是 3 mod 4 一定要加负号！这是考卷上扣分最多的地方，没有之一。
- 雅可比符号直接下结论：再说一遍，雅可比符号算出 1 不代表有解。选择题看到“雅可比符号为 1 则是平方剩余”直接打叉。
- 上大化小忘了动作：算
(111/71)直接当素数去想互反律了。上面的 111 已经比底座大了，第一步永远是对它求余数化小！ - 遇到带系数的强行算：
3x² ≡ 5 (mod 11)，直接去算(5/11)？错！先算 3 的逆元（4），两边乘 4 变成x² ≡ 20 ≡ 9 (mod 11)再去判定。
自测题（没做对别进考场）
- 判断 4 是模 7 的平方剩余吗？
- 判断方程
x² ≡ 111 (mod 71)有没有解。（练勒让德三板斧） - 判断方程
x² ≡ 360 (mod 2011)有没有解。（连环拆解挑战） - 判断方程
x² ≡ 99 (mod 323)有没有解。（防合数坑测试） - 计算勒让德符号
(151 / 373)。（双双三变号测试）
自测答案
- 是（因为 2² = 4 mod 7）。
(111/71) = (40/71) = (2/71)³ × (5/71)。71÷8余7，(2/71)=1。5÷4余1，直接翻得(71/5) = (1/5) = 1。全都是 1，所以有解。- 360 = 36 × 10。所以化简为
(10/2011) = (2/2011) × (5/2011)。2011÷8余3，(2/2011) = -1。5÷4余1，直接翻(2011/5) = (1/5) = 1。乘积为 -1，所以无解。 - 323 = 17 × 19。在模 17 下，方程化为
x² ≡ 14 (mod 17)。(14/17) = (2/17) × (7/17) = 1 × (-1) = -1。有一个不满足，所以无解。 (151/373) = (373/151) = (71/151) = -(151/71) = -(9/71) = -1。