初等数论 · 大衍与互反

本书怎么读：一章一个节奏

全书按「章」前进，一章 50 页。每章的节奏是：第 1 页导引（这个问题在人类文明里是怎么长出来的，本章路线），随后 18 页讲义（定义、定理与方法一条一条立起来，含历史注与现代接口旁注），12 页例题（带完整解答与逐步演算），12 页习题（由浅入深，末页复盘归档），2 页格物札记——一章一思：一页回到《九章算术》的对照传统，一页接通现代数学；末 6 页为综合站（章小结 · 思想卡 · 挑战一 · 挑战二 · 实验 · 章测试与评讲）。

本册三条线索，贯穿每一章：

① 明线——盈不足与逼近。从《九章算术》盈不足术、刘徽割圆注起手，把「以已知的离散，逼近未知的连续」这门古老手艺，一步步提升为极限、连续、导数与积分的语言。凡标〔盈不足〕处，都是这条线索的接续点。

② 现代接口——微积分的现代形态。每章札记与综合站把本章内容与现代数学对齐：实数完备性的等价命题群、可微性的现代表达（方向导数与 Fréchet 导数）、最优化与凸分析、拓扑连续、计算机代数与数值分析。理论在这里长出今天的枝叶。

③ 离散 ⇄ 连续接口——两个世界的握手。盈不足术是线性插值、开方术是不动点迭代、差分是导数的离散影子、梯形法是积分的离散影子。凡标〔离散〕处，都把连续命题翻译成可计算的离散版本，再翻译回来。

写法约定（TEX 标准）：分数写成上下两层的 12；极限的展示型写法是 limn→∞；微分号 d 与常数 π, e 用正体，变量用斜体 x, y, f；积分号 ∫；集合与数系符号 ∈ ⊂ ∪ ∩ ∅，ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ；向量用粗斜体 a；等价 ≅、蕴含 ⟹、当且仅当 ⟺、任意 ∀、存在 ∃。中括号写成 ［　］。凡方法步骤，一律配图，一步一图。

绪论 从物不知数到高斯的宝石0.1 从「物不知数」说起：《孙子算经》的千古一问〔大衍〕

公元四五世纪，一位不知名的算学家在《孙子算经》卷下写下了数学史上最著名的问题之一：

用今天的记号，这道题是求一个数 x，使得 x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7) 同时成立。答案不止 23——233、443、653……都满足；但 23 是最小的一个，通解是 x = 23 + 105t（105 = 3·5·7）。宋人程大位《算法统宗》把解法编成一首口诀：

口诀的账本：2×70 + 3×21 + 2×15 = 233，再减去 105 的两倍，得 23。三个魔法数 70、21、15 各有来历：70 是 5 和 7 的倍数，且除以 3 余 1；21 是 3 和 7 的倍数且除以 5 余 1；15 是 3 和 5 的倍数且除以 7 余 1。把「除以 3 余 2」的那份用 70 去凑，其余两项同法相加——每个条件各出一位代表，互不干扰。

这道题是本册的开篇之题。「余数」在小学里是除法的下脚料，在这里却成了主角：三三数之、五五数之、七七数之——同一个数在不同「模子」下留下不同的影子，数论的全部故事，就是研究这些影子之间的法则。〔大衍〕将作为章内接续点：从《孙子》到秦九韶「大衍求一术」，再到高斯的同余理论，一条暗线贯穿全书。

绪论 从物不知数到高斯的宝石0.2 什么是数论：整数世界的问题清单

数论是研究整数——尤其是正整数——性质的数学分支。它的原料朴素到极致：1, 2, 3, 4, 5, …；但它的定理深刻得惊人。一条判据：一个问题若用整数陈述、却需要非整数的工具才能解决，它多半就是数论问题。

与清单上的未决难题不同，互反律是一个已被完全证明、且证明美到可以被反复重讲的定理。选择它作为目标，正因为它同时展示了数论的两副面孔：具体（每个素数对都能逐字验算）与抽象（定律本身说的是全体素数的对称性）。

绪论 从物不知数到高斯的宝石0.3 现代的入口：群、组合与「TheBook」的证明观

本册处理内容的方式是现代的：凡是能用群论语言说清的，绝不用零散技巧重说一遍。这不是炫技，而是经济——同余的世界天生就是群的温床，用群的眼光看，Wilson 定理、Fermat 小定理、原根存在性会共享同一副骨架。

组合数学是另一件现代武器：把代数恒等式翻译成数东西。下面的例子是 Fermat 小定理的项链证明预告——它将在第二章完整登场。

这样的证明不依赖任何记忆，只依赖「换个方式数同一批东西」——双计数。组合证明与群论证明在本册常常殊途同归：项链的「转动不变性」正是循环群作用的写照。

绪论 从物不知数到高斯的宝石0.4 全书地图：整除→同余→方程→原根→互反的五站旅程

全书五章，是一条环环相扣的行军路线：每一章都为下一章锻造一件兵器。

两全其美的读法：顺着读，兵器一件不缺；带着问题读——每一章开头都会重申主问题「什么时候 x² ≡ a (mod p) 有解」，可以看到答案如何一层层收网。

绪论 从物不知数到高斯的宝石0.5 历史长廊：从《九章》《孙子》到《算术研究》〔大衍〕

本册的数学，是一条东方与西方交替领跑的接力赛道。把八件大事钉在同一根时间轴上，全书的历史坐标便一目了然。

三个细节值得驻足。其一，《九章算术》方田章的约分术（「以少减多，更相减损，求其等也」）正是辗转相减求 gcd——第一章将把它与 Euclid 算法并排讲。其二，秦九韶 1247 年的「大衍求一术」已把物不知数问题推广到任意模数，比 Euler 与 Gauss 的一般理论早了五百多年。其三，高斯的《算术研究》(Disquisitiones Arithmeticae) 完成于他 19 岁到 24 岁之间——「同余」这个核心概念连同记号 ≡，都是这本书的发明。

绪论 从物不知数到高斯的宝石0.6 数论与现代世界：RSA、Diffie–Hellman 与素数

1976 年以前，数论被公认为「最纯粹」的数学——Harder 称「它没有用」甚至是一种荣耀。1976 年 Diffie 与 Hellman 发表《密码学的新方向》，1977 年 Rivest、Shamir、Adleman 提出 RSA：两千年纯数学一夜之间接管了世界的秘密。

本册不回避这些现代应用，但也不喧宾夺主：密码学是数论定理的消费者，不是本书的目的。每一处「现代接口」小节都会指明：是哪一条定理、哪一个群在承担安全。

绪论 从物不知数到高斯的宝石0.7 计算的眼光：用程序「做」数论

数论是最适合「动手算」的数学分支：定理说的就是可数的东西。本册每一章的「实验」综合站都配一个小程序，而正文中所有例题数值均由程序预先对账。先立一个样板——三行代码验算物不知数：

ans = [x for x in range(105) if x%3==2 and x%5==3 and x%7==2]
print(ans)              # [23]  ——《孙子算经》的答案，两千年后一行对账
print(2*70 + 3*21 + 2*15 - 2*105)   # 23  ——「三人同行七十稀」的口诀账

再看本册多处要用的两件「账房工具」：快速幂与欧拉判据。快速幂把 aⁿ mod p 的计算量从 n−1 次乘法压到约 log₂n 次——指数 100 只需 7 步：

def mpow(a, n, p):          # 快速幂：an mod p
    r, a = 1, a % p
    while n:
        if n & 1: r = r*a % p
        a = a*a % p; n >>= 1
    return r
print(mpow(2, 100, 13))     # 3   （第二章例10 逐字对账）
print(mpow(5, 5, 11))       # 1   —— 5 是 mod 11 的平方剩余（第五章欧拉判据）

计算在本书里有三重身份：对账（定理的数字验证）、发现（先算出 QR 表，再猜出 (2/p) 的补律——这正是历史上 Euler 与 Gauss 的路）、反例（一个反例胜过十次苦算）。三重身份在第五章的「互反律对账器」实验里合流。

绪论 从物不知数到高斯的宝石0.8 怎么读本书：记号、约定与节奏

记号先行，全书统一。下列符号将在首次出场处详细定义，此处先立清单备查：

体例节奏：每章 50 页，按「讲义 ×18 → 例题 ×12 → 习题 ×12 → 格物札记 ×2 → 综合站 ×6」行进。讲义一步一图、一图一义；例题全部数值对账；习题课配提示；格物札记一谈中国古典、一谈现代发展；综合站含小结、思想卡、两道挑战（TheBook 式证明）、一个实验与章测试。

两条明线：〔大衍〕标记——从《孙子》物不知数到秦九韶大衍求一术再到 CRT 的算法线；〔少广〕标记——从《九章》少广开方术到模 p 开平方再到互反律的平方线。读到带标记的段落，就是在与古人同行。

最后是姿势建议：数论的定理不读完证明不算读。每个「定理」当作一座必须亲手走过的桥——本册的证明都按 TheBook 标准挑过，走一遍即是享受。

第一章 整除与带余除法1.1 导引：商是配角，余数才是主角

小学的除法算式 385 ÷ 24，我们早在三年级就会写：商 16 余 1。但同一道算式有两种读法：商 16 说的是「装满 16 轮」——这是除法的数量职能；余 1 说的是「轮转之后还剩一格」——这是除法的结构职能。数论关心的，是后者。

看一只钟。17 时过后 9 小时是几时？26 时，但钟面只回答「2 时」：26 与 2 在钟面上无法区分。我们把这件事记作 26 ≡ 2 (mod 24)。钟面把全体整数折叠成 24 个位置，任何数都落到其中一个位置上——折叠的规则，正是带余除法。

下一节先把「整除」这个词说严格——它是「r = 0」的特殊情形，也是全部理论的第一个原子。

第一章 整除与带余除法1.2 整除：定义与基本性质

整除的四条基本性质，每条的证明都只有一行——但这一行行合起来，就是第一章全部 machinery 的雏形。

性质②是四条中最有分量的一条：若 a 同时整除 b 与 c，则 a 整除它们的一切整系数组合。把它倒过来读——对给定的 b、c，问「哪些 a 能整除 mb + nc」——就在追问最大公因数（1.6 节）。整除的结构天然是偏序的：把「整除」当作大小关系，全体因数组成一座格（lattice）。

第一章 整除与带余除法1.3 带余除法：存在性与唯一性

定理貌不惊人，其实是全书的第一台发动机：唯一性保证了「每个整数 mod b 有唯一影子」——没有它，第二章的「折叠」就叠不出良定义的钟面；存在性给出的取整手续，则是第四章「求阶」和第五章「求平方根」时反复使用的降模工具。良序原理（任何非空整数集若有下界则含最小元）是这两步的共同靠山——它是数论的「隐形公理」，1.7 节 Bézout 恒等式将再次调用它。

第一章 整除与带余除法1.4 素数与合数：整数的原子

为什么把 1 开除出素数籍？这不是洁癖，而是保护算术基本定理的唯一性：若 1 算素数，则 6 = 2·3 = 1·2·3 = 1·1·2·3，同一数有「无穷多种分解」——唯一性荡然无存。1 是乘法世界的「单位元」，单位元不参与原子论，这条界线将在 1.13 节讲唯一性时彻底说清。

于是判定素数只需用不超过 √n 的素数试除。例如 223：√223 < 15，只需试 2, 3, 5, 7, 11, 13——全部除不尽，223 是素数（1.12 节前的例 3 完整跑一遍）。

第一章 整除与带余除法1.5 素数有无穷多个：Euclid 的证明与现代变奏

这个证明是「TheBook 式」的典范：不构造新素数，只证明清单永远关不上门。注意证明并没有说 p₁p₂⋯p_k + 1 本身是素数——它只保证这个数带来某个清单外的新素数。例如 2·3·5·7·11·13 = 30030，30031 = 59 × 509，带来两个新素数。

现代变奏（Fermat 数路线）：记 F_n = 2²ⁿ + 1。关键观察：若 m < n，则 F_n − 2 = F_0F_1⋯F_m+1⋯ 的连乘关系使 F_m | F_n − 2。于是 gcd(F_m, F_n) 整除 2 与两奇数之 gcd，只能为 1——Fermat 数两两互素！每个 Fermat 数贡献一批全新素数，而 Fermat 数有无穷多个，故素数无穷。这条变奏的妙处：它把「无穷多」归功于一个显式的两两互素数列——组合结构代替了反证。

第一章 整除与带余除法1.6 最大公因数：定义与直觉

直觉一：交集。gcd(120, 78) 是「120 的因数集合 ∩ 78 的因数集合」的最大元。直觉二（更现代）：因子格的交——1.2 节的格视图下，gcd 是两座塔在整除偏序下的最大公共下界。

交集视图好算却不高——它依赖标准分解，而分解大数很难（这正是现代密码的安全前提）。下一节的 Bézout 恒等式给出一条不需要分解的路：用良序原理直接抓住 gcd，这正是把 gcd 从「搜索问题」变成「结构定理」的关键一步，也是群论登场前最后的铺垫。

第一章 整除与带余除法1.7 Bézout 恒等式：良序原理的杰作

证明的神来之笔是第①步：用带余除法在 S 内部造出「更小的正元」，逼它为零。良序原理 + 带余除法的这套连招，将贯穿全书（1.12 算术基本定理、4.7 原根存在性）。看 120 与 78 的组合世界：

组合世界「恰好是 d 的倍数」不是巧合：d 整除每个组合元（性质②），而 d 自己在 S 中——两头一夹，世界不多不少正是 d 的倍数集。这个「由生成元张成的世界」的图像，第二章将以子群的身份正式登场。

第一章 整除与带余除法1.8 辗转相除法：Euclid 算法及其效率

引理说：gcd 不因降模而变。于是反复降模——辗转相除，gcd(120, 78) 的全程账本：

效率的惊人事实（Lamé, 1844）：Euclid 算法最坏情形恰发生在相邻 Fibonacci 数上——gcd(F_k+1, F_k) 恰需 k − 1 步（如 gcd(34, 21) = 1 用了 7 步）。于是步数 ≤ 5 × 输入的十进制位数：一百位的数也只需约五百步。快，是因为 mod 收缩得快——这个「对数级收缩」的思想，第四章的快速幂与离散对数将再度登场。

第一章 整除与带余除法1.9 互素：群论眼光初瞥——逆元存在的条件

互素不只是「公因数只有 1」的否定性陈述，它有一个响亮的肯定性等价刻画：

面孔②是全书最常用的一条：互素 = 可逆。在 mod n 的世界里，「除以 a」不是除法，而是乘以 a 的逆元——这正是 1.2 节性质②「消去律」在模世界成立与否的分水岭。看 mod 5 的乘法世界（全体非零剩余 1, 2, 3, 4）：

这张图是第四章「原根」的第一眼雏形：乘法世界 (ℤ/5)× 有 4 个元素，从 2 出发幂游 2 → 4 → 3 → 1 走遍全群——2 是生成元。群论的语言将在第二章和第四章分两步把这件事说透；眼下：互素性是「可逆」的同义词，这是 Bézout 恒等式最漂亮的化身。

第一章 整除与带余除法1.10 最小公倍数与 gcd·lcm 恒等式

证明里引理 1.10.2 居功至伟——而它只是 Bézout 的一行推论。现代注脚：把 g 与 L 分别看作因子格 1.2 节中的「最大公共下界」与「最小公共上界」，定理 1.10.3 说的是乘法与格论的调和；到第五章，勒让德符号的乘性将再次扮演「结构随乘法携带」的角色。

第一章 整除与带余除法1.11 线性丢番图方程：ax+by=c 的判据与通解

跑一遍全流程：解 37x + 21y = 63。g = gcd(37, 21) = 1 | 63 ✓。1.7 节账本回代出 37×4 − 21×7 = 1，乘 63：特解 (252, −441)，通解 x = 252 + 21t, y = −441 − 37t。

图中 37x + 21y = 63 一类方程的「非负解计数」是自然的后续问题：通解沿步长 (21, −37) 跳动，正象限只接得住有限几步——这类「计数通解」的题在习题课七展开。丢番图方程是数论的祖业：《九章》盈不足、拜占庭的「百鸡问题」（百钱百鸡）都是它的变奏，第三章将把「求解」升级到模世界。

第一章 整除与带余除法1.12 算术基本定理（一）：存在性——最小反例法

这个证明展示了良序原理的第二种用法：最小反例。1.7 节的用法是「取最小正元直接当答案」，这里是「取最小反例然后撕碎它」——两句台词，同一原理。对具体的数，分解按「从最小的素因子开始剥」逐层进行：

树可以有不同的长法（先剥 11 也行），但叶子集合——重排意义下的素数串——是唯一的。这唯一性正是「基本」二字的分量，它的证明（1.13 节）比存在性微妙得多：需要一个真正深刻的引理，而那个引理的现代解读，是群论的第一声啼鸣。

第一章 整除与带余除法1.13 算术基本定理（二）：唯一性——Euclid 引理的群论解释

群论解释：Euclid 引理里「p 不整除 a ⟹ p 与 a 互素」这一步，说的是素数在 mod a 的世界里是可逆元——「素」的本质是「在所有更小的世界里都不塌缩」。更现代的说法：唯一性是 ℤ 这个环的特惠，而非当然。在高斯整数 ℤ[i] 中，5 不是「素元」：5 = (2+i)(2−i)，分裂了；但 ℤ[i] 仍是唯一分解的——(2+i) 与 (1+2i) 只差单位 i 相乘，本质同一。而在 ℤ[√−5] 中，唯一性真的破产：6 = 2 × 3 = (1+√−5)(1−√−5)，两串分解无可调和——十九世纪的代数学家正是被这类现象逼出了理想论与抽象代数。

第一章 整除与带余除法1.14 素数计数初步：π(x) 与素数定理远望

记 π(x) 为不超过 x 的素数个数。它是数论最重要的函数之一——本册只需它的几个采样点与一条「远景定律」：

从 π(x) 出发的远望，是第五章互反律对账器的底气：程序在几秒内验证上百对素数，靠的正是素数定理保证「素数管够、随手可取」。

第一章 整除与带余除法1.15 素数的间隙：孪生素数猜想与 Bertrand 假设

素数虽密，间隙却会拉长：113 与 127 之间隔着 13 个合数。两个方向的自然问题——间隙能多小与间隙会多大——一个至今未决，一个已有初等答案。

一条阅读分界线：孪生素数猜想「问无穷」，Bertrand 假设「问可达」——前者悬赏两百年未决，后者初等可证。分清这两类问题，是数论基本功：本册的主问题（互反律）属于「可达」一类，而它一旦证毕，立刻给出所有素数对都满足的定律——这正是「定律」与「猜想」的气质之别。

第一章 整除与带余除法1.16 因子个数与因子和：τ、σ 与完全数

算术基本定理一到手，因子结构立刻变成组合小算术。设 n = p₁^a₁ p₂^a₂ ⋯ p_r^a_r，则 n 的每个正因子形如 p₁^b₁⋯p_r^b_r（0 ≤ b_i ≤ a_i）——每个指数独立选值：

组合视角收束：τ 与 σ 的公式把「找因子」从枚举升格为指数独立选值的计数——这正是「因子格 1.2 节」的代数化身：格的每条路径对应一组指数选择。下一节走向本章的出口：当分解大数不可行时，如何不分解而判素。

第一章 整除与带余除法1.17 现代接口：试除与 Miller–Rabin 预告——素性判定的第一块砖〔密码〕

试除法的账单很清楚：判定一个 n 位数需要约 10^n/2/(n ln 10) 次除法——600 位数要试 10²⁹⁷ 量级，宇宙年龄也跑不完。RSA 需要 600 位的素数，故密码学的地基是不分解的判素。第一块砖是 Fermat 小定理（第二章完整证明），先睹其用法：

第一章 整除与带余除法1.18 本章总结与方法表

本章从一句「商是配角」出发，抵达了算术基本定理。装备清单如下：

第一章 整除与带余除法例1 整除证明：n(n+1)(2n+1) 被 6 整除

第一章 整除与带余除法例2 带余除法：求商定余与验证

第一章 整除与带余除法例3 素性判定：试除法判定 221 与 223

第一章 整除与带余除法例4 Bézout：120 与 78 的整系数表达

第一章 整除与带余除法例5 辗转相除：步骤表与复杂度直觉

第一章 整除与带余除法例6 互素三连判：gcd=1 的等价刻画

第一章 整除与带余除法例7 gcd 与 lcm 联算：恒等式的应用

第一章 整除与带余除法例8 线性丢番图：37x+21y=63 的通解

第一章 整除与带余除法例9 标准分解：2024 的素因子账

第一章 整除与带余除法例10 因子函数：τ(2024) 与 σ(2024) 的组合算法

第一章 整除与带余除法例11 完全数：6、28 与 Euclid–Euler 公式初瞥

第一章 整除与带余除法例12 综合：一道整除题的代数与组合双解

第一章 整除与带余除法习题课一 整除与带余除法

第一章 整除与带余除法习题课二 素数与合数

第一章 整除与带余除法习题课三 Bézout 恒等式

第一章 整除与带余除法习题课四 辗转相除法

第一章 整除与带余除法习题课五 互素

第一章 整除与带余除法习题课六 lcm 与联算

第一章 整除与带余除法习题课七 线性丢番图方程

第一章 整除与带余除法习题课八 算术基本定理

第一章 整除与带余除法习题课九 τ 与 σ

第一章 整除与带余除法习题课十 完全数与盈亏数

第一章 整除与带余除法习题课十一 素数分布初探

第一章 整除与带余除法复盘：错题归档与三问自测

复盘的检验标准不是「看懂了」，而是合上书能把证明重写出来。第一章的四个必背证明：带余除法唯一性、Bézout、互素消去律、FTA 唯一性——都是「一行一逻辑」的短证明，值得逐字过关。

第一章 整除与带余除法格物札记① 《九章》约分术与更相减损：gcd 的东方源头〔大衍〕

《九章算术》方田章开篇讲田亩测量，随即遇到一个绕不开的技术问题：分数要约分。约分的全部难点在一个词——「等数」，也就是今天说的 gcd。刘徽注引的术文写道：

拿 49/91 走一遍：「副置」两数 91、49；91 − 49 = 42，49 − 42 = 7，42 − 7 = 35，35 − 7 = 28，…（连减到）7 − 7 = 0——更相减损的账本会连减到底；术文允许求速：42 ÷ 7 恰尽，知等数为 7。约分得 49/91 = 7/13。

两处细节见精神。其一，「可半者半之」是 speed-up：先剥离 2 的因子——这与今天的「二进制 gcd」思想一致。其二，Euclid《原本》第七卷命题 1–2 的原始证法其实也是反复相减，带余除法是后人的打包优化——东西方在同一算法上各自独立地走到了一起，殊途而同归。

第一章 整除与带余除法格物札记② 良序原理：数论证明的隐形引擎

本章出现了三次「取最小」：带余除法里取最大的 q（1.3 节）、Bézout 里取最小的正组合（1.7 节）、FTA 里取最小的反例（1.12 节）。三次的背后是同一条公理：

一个值得咀嚼的哲学观察：良序原理不是自然数的当然属性——整数的负半轴、正有理数集都没有最小元。「自然数良序」与「归纳法可用」是同一枚硬币，皮亚诺公理体系把两者焊在一起。下一章，这套「公理化的自觉」将升级为群论的语言：我们将不再一个个地研究数的性质，而是研究运算本身的结构。

第一章 整除与带余除法章小结：知识图谱与方法表

本章的骨架是一条「良序驱动链」：带余除法立折叠 → Bézout 抓 gcd → 互素开可逆 → Euclid 引理保唯一 → FTA 立宪法 → τ、σ 发红利。六个枢纽，每一步都由上一步供电。

三件兵器交给第二章：良序降模（在同余世界里继续用带余除法）、Bézout 逆元（1.9 节的四面孔将变成单位群的主角）、互素消去（CRT 的相容性论证）。

第一章 整除与带余除法思想卡：余数——把无限的世界折叠成有限

思想卡的另一面值得记录：折叠保留了什么？加法的影子保真（385 + 24 的奇偶性 = 影子 + 影子的奇偶性），乘法也保真——但除法不保真：6 和 2 影子不同（mod 4），可 6 ÷ 2 = 3 的影子没法由影子的除法得出。哪里保真、哪里失真，正是第二章「同余运算规则」（2.8 节）要精确划定的边界。

第一章 整除与带余除法挑战一 算术基本定理的完整证明

把 1.12 与 1.13 的两半合并，独立完成整座桥。允许引用：带余除法（1.3）、Bézout（1.7）、互素消去律（1.10）。分五步走：

验收标准：五个步骤中，不允许出现「显然」——每一步的合法性都要指明引用哪条已证结果。完成本挑战，就拥有了三千年数学史的压舱石。

第一章 整除与带余除法挑战二 Bertrand 假设的初等证明（Erdős 版）

目标：n > 1 时存在素数 p 使 n < p < 2n。Erdős 十七岁的证明是组合数论的杰作——把「存在大素数」化归为「二项式系数足够大」。以下路线图留白关键步：

TheBook 评语：这个证明的口味是纯组合的——不碰微积分、不碰复分析，只数数。完整细节可读 Erdős 1932 年原文的重述（Aigner & Ziegler《Proofs from THE BOOK》第 4 章）。第五章的互反律证明会再次使用「审计素数贡献」的账本手法。

第一章 整除与带余除法实验：辗转相除可视化——最坏情形为何是斐波那契

实验目标：亲手验证 Lamé 定理——相邻 Fibonacci 数把 Euclid 算法拖到最满。程序三件事：数步数、画收缩链、扫全表找最慢。

def esteps(a, b):          # 辗转相除步数
    s = 0
    while b: a, b = b, a % b; s += 1
    return s

# 1) 相邻 Fibonacci 对账（Lamé：gcd(F(k+1), F(k)) 用 k−1 步）
fib = [1, 1]
while len(fib) < 15: fib.append(fib[-1] + fib[-2])
for k in range(2, 14):
    print(k, esteps(fib[k+1], fib[k]))    # 输出恰为 k−1

# 2) 扫描全表：1000 以内哪一对最慢？
best = max(((esteps(a, b), a, b) for a in range(2, 1000)
            for b in range(2, a)), default=(0, 0, 0))
print(best)   # 步数最多的一对，恰是相邻 Fibonacci！

观察任务：①步数序列 1, 2, 3, 4, 5, 6, …（对相邻 Fibonacci）是否严格等差？②全表扫描的最慢对是 (987, 610) = (F₁₆, F₁₅)，步数 14——为什么 Fibonacc 是「收缩最慢」的？直觉：mod 的意义是「砍掉一整段」，而 Fibonacci 数的商 q 全是 1，一砍只砍一小段。商全 1 = 降模最温和 = 步数最多。③挑战：证明 Fibonacci 相邻对在所有 ≤ n 的数对中步数最多（Zeilberger 有一个四页证明）。

第一章 整除与带余除法章测试与评讲

第二章 同余与剩余类2.1 导引：高斯的钟表世界——模运算登场〔大衍〕

1801 年，24 岁的高斯出版《算术研究》，第一句话就发明了一个记号——此后数论的语言再也不一样了：

一千五百年前的物不知数，在高斯的记号下三行写清：求 x 使 x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)。同一个数 23 在三个模子下留下三道影子：

本章路线：先给同余立运算规则（2.2–2.3），再把影子升格为代数对象——加法群 ℤ/nℤ（2.4）、单位群 (ℤ/nℤ)×（2.5）、群论速成（2.6）；随后挥师中国剩余定理与大衍求一术（2.9–2.11），以 Wilson 与 Fermat 的组合证明收束（2.12–2.13）。

第二章 同余与剩余类2.2 同余的定义与基本性质

定义里没有出现「余数」——同余被翻译成整除，这步翻译是高斯记号的力量所在（一切整除工具立刻可用）。由定义立刻读出三条：自反（a ≡ a）、对称（a ≡ b ⟹ b ≡ a）、传递（a ≡ b ≡ c ⟹ a ≡ c）——同余是一个等价关系，这是现代数学对「折叠」的正式称呼。

③的证明是一行线性组合——第一章性质②在折叠世界的第一次领薪。但注意除法不保真：2×3 ≡ 0 (mod 6) 而 2, 3 都 ≢ 0——两个非零影子的乘积可以塌到零（「零因子」现象），这正是 2.5 节单位群必须把「可逆者」单独圈出来的原因。看 mod 5 的抽屉：

第二章 同余与剩余类2.3 剩余类与代表元：把整数折叠成 n 个抽屉

代表元的选取自由而任意：{0, 1, …, n−1}、{1, 2, …, n}、对称系 {−(n−1)/2, …, (n−1)/2}（n 奇）都是合法的完全剩余系。代数运算与代表元的选取无关——定理 2.2.2 的真正含义：剩余类的加法、乘法是良定义的。这一步「与代表元无关」的自觉，是抽象代数的胎动：我们开始操作对象本身，而非它们的化名。

对称系在第五章 Gauss 引理中会大放异彩——「以少减多」的古老直觉，将在那里变成 (p/2, p) 区间的代表元跳跃计数。眼下只需记住：代表元是化名，剩余类才是本人。

第二章 同余与剩余类2.4 ℤ/nℤ 的加法：一个群的诞生

证明中最要紧的一句是「与化名无关」：群论的世界里，[3] 不是「数字 3」，而是整个抽屉——抽屉之间做运算，结果的抽屉不因从抽屉里挑了哪个代表而改变。mod 5 的加法表（Cayley 表）：

现代注脚：ℤ/nℤ 的加法群是循环群——整个群由 [1] 反复自加生成：[1] → [2] → … → [n−1] → [0] → [1]。这枚「生成元」的种子，第四章将长成原根理论：乘法世界里，谁的幂走遍全群？

第二章 同余与剩余类2.5 ℤ/nℤ 的乘法：什么时候能除？——单位群 (ℤ/nℤ)×

乘法同样保真（定理 2.2.2 ③）：[a]·[b] = [ab]。但它造不成群——[0] 没有逆（除 1 = n 的退化情形），复合数还混进「零因子」：[2]·[3] = [0] (mod 6)。把可逆的类单独圈出来，得到一个惊人的干净世界：

Bézout 恒等式在此兑现为「逆元」——1.9 节的四面孔正式上岗。看 mod 10 的单位群（与 10 互素的剩余类恰四个）：

第二章 同余与剩余类2.6 群论速成：群、子群、陪集与 Lagrange 定理

立即兑现的红利：设 G 是交换群、a ∈ G，则 a 的所有幂构成子群 ⟨a⟩，其大小恰是 a 的阶。由 Lagrange：任何元素的阶整除群阶。对 G = (ℤ/pℤ)×（|G| = p − 1，第四章），这句话就是 Fermat 小定理的群论前身——组合的项链证明（2.13）与群的切蛋糕证明将在那里会师。

第二章 同余与剩余类2.7 剩余类环：ℤ/nℤ 的完整代数结构

把加法（2.4）与乘法（2.5）合起来，剩余类集合成了一座完整的代数建筑：

「模 p 是域」是第三章的全部地基：域里能约分、多项式根不超过次数（Lagrange）——这些在环里都会失灵。素数的代数性格在此定型：素数恰好是让折叠世界不产生零因子的模数。

第二章 同余与剩余类2.8 同余式的运算规则：升模、降模与消去律

折叠世界的四则规则中，「除法」最微妙。它的两个精确版本：

规则②是「带着公因数消去」的精确账：消去 a 的同时，模也要降。例：2×3 ≡ 2×0 (mod 6)，消去 2 得 3 ≡ 0 (mod 3)——mod 6 里不能消，降到 mod 3 就能消。这就是降模。「升模」是反方向：mod 3 的信息自动升到 mod 6、mod 12（只要结论形如 n | t，则任何 n 的倍数也整除 t）。

第二章 同余与剩余类2.9 中国剩余定理（一）：物不知数的求解〔大衍〕

把开篇之题正式解一遍——这次用「影子逐条落实」的现代姿势：

第二章 同余与剩余类2.10 中国剩余定理（二）：代数证明——环同构的礼物

证明的骨架是两个「开关元」P 与 Q：P 在 m 世界是 1、在 n 世界是 0——像一只只按一个世界亮灯的开关。任何目标影组 (a, b) 都由开关加权合成。环同构的礼物：映射 x ↦ (x mod m, x mod n) 是环同构 ℤ/mnℤ ≅ ℤ/mℤ × ℤ/nℤ——折叠世界与「影子对」的世界结构全同，加乘都逐影子进行。

第二章 同余与剩余类2.11 中国剩余定理（三）：秦九韶大衍求一术今译〔大衍〕

1247 年，秦九韶在《数书九章》中系统给出 CRT 的通用算法——大衍总数术，其中求「乘率」的核心步骤称大衍求一术。把古术逐词今译：

「求一」二字直白：求出一个数，乘上去余一。求乘率的工具正是辗转相除的回代——秦九韶称「以奇模入之，辗转相减，得奇一而止」。用古术核一笔账：物不知数中 m₃ = 7，衍数 M₃ = 15，奇数 = 15 mod 7 = 1，乘率 = 1，用数 = 15——正是口诀里的「七子团圆正半月」！口诀的三个魔法数 70、21、15，原来就是三个用数：k_i·M_i。

第二章 同余与剩余类2.12 Wilson 定理：项链计数法的组合证明

反向（−1 ⟹ 素数）：若 n 合数，n = ab（1 < a ≤ b < n），则 a 是 (n−1)! 的一个因子（a 出现在阶乘中），且 a 与 (n−1)!/a 互不干扰地同除 n − 1 的阶乘——更直接：ab | (n−1)!（a ≠ b 时两因子分别出现；a = b > 2 时 2a < n 使 a 出现两次），于是 (n−1)! ≡ 0 ≢ −1 (mod n)。∎

历史的趣味：Leibniz 早已知道此定理却未发表；Wilson 是学生时代猜到它；Lagrange 给出第一个证明；Gauss 在《算术研究》里嫌弃试凑式验证、代之以一般理论，并顺手推广到双阶乘（(p−2)!! ≡ 1）。「素数 ⟺ 阶乘 ≡ −1」是素性的等价刻画——但作为判素工具毫无用处：算 (p−1)! 比试除贵得多。定理的价值在结构，不在效率。

第二章 同余与剩余类2.13 Fermat 小定理：多项式视角与组合证明

多项式视角（第三章预演）：a^p ≡ a 对一切 a 成立，等于说多项式 x^p − x 在 mod p 下有 p 个根——次数 p 的方程恰有 p 个根，「根不超过次数」的 Lagrange 定理与「完全分裂」现象都在这里探头。第三章将把这双眼看全。

第二章 同余与剩余类2.14 欧拉定理：φ 函数与一般化

Fermat 小定理依赖素数模——合成模的舞会里有人不可逆。Euler 的推广把主角换成「可逆者的全体」：

这是「重排证明」的原型：交换群作用在自己的集合上保持结构。p 素数时 φ(p) = p − 1，Fermat 小定理是欧拉定理的特例—— generalize by replacing "everything" with "everything invertible"。

第二章 同余与剩余类2.15 Euler φ 函数：公式推导与积性

第二章 同余与剩余类2.16 应用：模幂运算与快速幂算法

欧拉定理的日常用途是给指数「封顶」：算 a^N mod n 时，指数 N 可以对 φ(n) 取余（gcd(a,n)=1 时）——指数瞬间变小。剩余的功耗由快速幂承担：把 N 写成二进制，逐位平方。

第二章 同余与剩余类2.17 现代接口：从 Fermat 到 Miller–Rabin——概率素性测试〔密码〕

1.17 节的预告在此兑现。Fermat 检验：存在 a 使 aⁿ⁻¹ ≢ 1 (mod n) ⟹ n 合数；反之通过者可能合数（伪素数），最顽固的 Carmichael 数 561 = 3 × 11 × 17 对一切互素的 a 都冒充通过。Miller–Rabin 的二次修正撕破伪装：

第二章 同余与剩余类2.18 本章总结与方法表

第二章 同余与剩余类例1 同余判定：大数降模与 2024 mod 7

第二章 同余与剩余类例2 完整剩余系：三种取法与等价性

第二章 同余与剩余类例3 加法群验证：(ℤ/12ℤ,+) 的子群清单

第二章 同余与剩余类例4 单位群枚举：(ℤ/10ℤ)× 的乘法表

第二章 同余与剩余类例5 消去律：何时 ab≡ac 可约去 a

第二章 同余与剩余类例6 物不知数：三人同行七十稀〔大衍〕

第二章 同余与剩余类例7 CRT 联立：x≡2(3), x≡3(5), x≡2(7) 的求解

第二章 同余与剩余类例8 大衍求一术：乘率的计算〔大衍〕

第二章 同余与剩余类例9 Wilson 对账：12! ≡ −1 (mod 13) 的逐项验证

第二章 同余与剩余类例10 快速幂：2¹⁰⁰ mod 13 的折半账

第二章 同余与剩余类例11 φ 函数计算：φ(360) 的标准分解法

第二章 同余与剩余类例12 综合：星期几问题——模 7 算术与历法

第二章 同余与剩余类习题课一 同余基本性质

第二章 同余与剩余类习题课二 剩余类与完整系

第二章 同余与剩余类习题课三 ℤ/nℤ 的加法

第二章 同余与剩余类习题课四 单位群

第二章 同余与剩余类习题课五 消去律

第二章 同余与剩余类习题课六 物不知数〔大衍〕

第二章 同余与剩余类习题课七 CRT 联立方程

第二章 同余与剩余类习题课八 大衍求一术〔大衍〕

第二章 同余与剩余类习题课九 Wilson 定理

第二章 同余与剩余类习题课十 Fermat 与快速幂

第二章 同余与剩余类习题课十一 φ 函数与欧拉定理

第二章 同余与剩余类复盘：错题归档与三问自测

本章必背证明三条：CRT（开关元合成）、Fermat 项链、Wilson 配对。第三章将把「域 F_p」请上台：有域在手，多项式方程的根数将有铁律。

第二章 同余与剩余类格物札记① 从《孙子算经》到《数书九章》：大衍求一术的千年接力〔大衍〕

从「物不知数」到「大衍求一术」，中间隔了近八百年——这条接力赛的每一棒都值得记录：

最令人感慨的是秦九韶的处境：《数书九章》成书于战乱流离之中（序言自述「际时狄患，历岁遥塞」），大衍术却处理着连欧洲要等高斯才严格化的一般情形——数学的火种，最怕的不是难，而是断。

第二章 同余与剩余类格物札记② 群论如何照亮数论：从 Lagrange 定理到 Fermat、Wilson

本章的三颗定理珠子——Fermat、Euler、Wilson——在高斯的折叠世界里各自闪耀了两百年。而现代群论给它们装上了同一盏灯：

历史的次序值得咀嚼：先有定理（1640–1770），后有语言（群论，19 世纪）。Galois 与 Abel 的时代，这些同余事实正是抽象群概念的子宫——数论不是「应用」了群论，而是孕育了它。在第 2.6 节学的每一条群论，都是从这个章节数回去的历史反方向。

第二章 同余与剩余类章小结：知识图谱与方法表

本章把第一章的余数从「下脚料」升格为「代数主角」：折叠合法（等价关系）→ 加法成群 → 可逆者结群 → 模素数成域 → 联立可解（CRT）→ 幂有周期（Fermat/Euler）→ 判素有门（MR）。

两件兵器交给第三章：域 F_p（素性 ⟺ 域，消去律全通）与φ 函数与缩系（多项式求根的计数工具）。

第二章 同余与剩余类思想卡：折叠——无限整数的有限肖像

思想卡的边界同样重要：折叠丢掉了「大小」——5 与 105 在 mod 10 下同影，但 105 是 5 的 21 倍。凡涉及「多少倍」的问题（估值、单调性）不能只靠影子；数论的美妙恰恰在于：多少」的信息常常以出人意料的方式藏在影子的组合里——第五章的 Gauss 引理就是一次精彩的「影子计数还原真身」。

第二章 同余与剩余类挑战一 Wilson 定理项链证明的完整书写

2.12 节给了配对证明的全文。本挑战换一条组合路——反方向跑项链账，把「素数 ⟺ 阶乘 ≡ −1」的等价性两头补齐：

TheBook 评语：步 4 是第五章的伏笔——((p−1)/2)! 的影子由平方剩余决定，而 Gauss 引理将证明它 ≡ ±1，正负由 p mod 4 决定。此题做好，第五章开篇即高屋建瓴。

第二章 同余与剩余类挑战二 非互素模联立的相容条件与 CRT 推广

模不互素时 CRT 失效，但不是全失效——相容的联立仍有解。本挑战把边界走全：

TheBook 评语：现代教科书常略去非互素情形，但「相容条件 = gcd 整除影子差」恰是 CRT 的代数心脏——环同构 ℤ/mn ≅ ℤ/m × ℤ/n 的完整版是：像 = {影子对 : mod g 分量相等}。步 4 则是工程师的实际做法：合并条件、降低系统模数。

第二章 同余与剩余类实验：模幂时钟——快速幂的折半跳舞

实验目标：把快速幂的「折半跳舞」画成时钟轨道——看指数的二进制如何决定轨迹，看 Fermat 周期如何把长舞变短舞。

def mpow_trace(a, n, p):     # 快速幂 + 轨迹记录
    r, a, trail = 1, a % p, [(1, a)]
    while n:
        if n & 1: r = r*a % p
        a = a*a % p; n >>= 1
        trail.append((r, a))
    return trail

for step in mpow_trace(2, 100, 13):
    print(step)   # 观察平方链 2,4,3,9,3,9,3 与累乘链的「跳舞」

观察任务：①平方列 2, 4, 3, 9, 3, 9, 3——从第三格起在 3 与 9 之间跳（2⁴ = 3 → 3² = 9 → 9² = 3）：周期 2 的「平方舞」；②把模换成 11、底换成 5，平方列 5, 3, 9, 4, 5, 3, …——周期 5（ord(5) = 5）：舞曲长度 = 元素的阶；③猜想：平方舞的周期 = ord(a) 的 2-幂部分如何行为？记录观察，第四章 4.2 节将给出精确语言（阶）。

第二章 同余与剩余类章测试与评讲

第三章 同余方程与多项式3.1 导引：在有限世界里解方程

整数世界里，解方程是一件奢侈的事。3x = 2 没有整数解；x² + y² = 13 有没有整数解？要费一番功夫。但在有限世界——固定一个模数 n，把整数折到 {0, 1, …, n−1} 这个小小的圆环上——情况截然不同：候选解只有 n 个。原则上，逐个代入总能验个水落石出。

于是「解方程」这件事在有限世界里获得了新的生命。把等号换成同余号，我们问的是：

答案：x = 3 就命中了，因为 3·3 = 9 ≡ 2 (mod 7)。而在整数世界里，3x = 2 永远无解。同一个方程，两种世界，两种命运——这正是本章要系统研究的对象：同余方程。

第三章 同余方程与多项式3.2 线性同余方程 ax≡b(n)：解的存在性

最简单的非平凡同余方程是线性的：

按定义，x 是解当且仅当 n 整除 ax − b，即存在整数 y 使 ax − b = ny，整理为

左边是 a 与 n 的一个线性组合——第一章的 Bézout 恒等式立刻接管局面：a 与 n 的全部线性组合恰好是 gcd(a, n) 的全部倍数。于是判据一步到位：

证明　（⟹）若 x 是解，则 n | (ax − b)，而 g | n 且 g | a，故 g | ax − b，特别地 g | b。（⟸）设 g | b。由 Bézout，存在 u, v 使 au + nv = g。两边乘 b/g：a·(ub/g) + n·(−vb/g) = b。于是 x₀ = ub/g 满足 ax₀ ≡ b (mod n)。∎

证明顺手送给我们一个构造性的解：x₀ = u·(b/g)，其中 u 是 au ≡ g (mod n) 的系数——这正是第二章「大衍求一术」计算乘率的那一步。求根问题与求逆问题在此会师：特别地，当 g = 1 时方程 ax ≡ b (mod n) 的唯一解就是 x ≡ a⁻¹b，即「乘上 a 的逆元」。

第三章 同余方程与多项式3.3 线性同余方程：解的个数与通解公式

存在性解决了，接下来数一数：有解时究竟有几个解？答案干净利落——恰好 g = gcd(a, n) 个，而且它们排成一条等差数列。

即模 n 意义下恰有 g 个互不相同的解。

证明　先验证这些的确是解：a(x₀ + k·n/g) = ax₀ + k·(a/g)·n ≡ ax₀ ≡ b (mod n)，因为 a/g 是整数，k·(a/g)·n 是 n 的倍数。再证不漏：设 ax ≡ ax₀ (mod n)，即 n | a(x − x₀)。令 d = n/g，则 g | a，写 a = g·a′，于是 d·g | a′·g·(x − x₀)，约去 g 得 d | a′(x − x₀)。由 gcd(a′, d) = 1（已把 a、n 的公因子全部约掉），消去律给出 d | x − x₀，即 x = x₀ + k·d。而模 n 而言 k 只给出 g 个不同余的值（k 与 k + g 相差 n）。∎

第三章 同余方程与多项式3.4 同余方程组：CRT 的一般形式

第二章我们用「大衍求一术」解过《孙子算经》的名题。现在把它写成标准定理，并看清代数骨架。

这个证明是组合式的：k 个「正交探针」张成一个坐标系，x 的各分量 b_i 可以独立调节——好比混音台上 k 个独立的推子。CRT 断言：两两互素时，模 M 的世界与直积 (ℤ/m₁)×(ℤ/m₂)×⋯ 完全等同（环同构，见札记②）。

第三章 同余方程与多项式3.5 多项式同余方程：f(x)≡0(p) 的根

线性只是一次多项式。本章真正的主角是一般的多项式同余方程：

例如 f(x) = x² + 1，模 5 时逐个代入：0²+1=1，1²+1=2，2²+1=5≡0 ✓，3²+1=10≡0 ✓，4²+1=17≡2。根为 x ≡ 2, 3 (mod 5)——注意 3 ≡ −2，两根关于 0 对称，这是「平方方程根成 ±对」的普遍现象。

模素数 p 做多项式，最幸福的一点是：域公理全部成立——加减乘畅通无阻，非零元都可除。这使我们在中学里学的多项式代数（因式定理、根的个数论）几乎原封不动地搬过来。但有一处天壤之别：根可能比次数多吗？中学代数说「n 次方程至多 n 个根」，那是实数世界的法律；在模合数的世界里它会破产（下一页的反例），而模素数时它依然屹立——这正是 Lagrange 定理。

第三章 同余方程与多项式3.6 代数速成：环、域与多项式环——ℤ/pℤ 是域

把代数结构说清楚，定理才站得稳。三层台阶：

证明　n 素时，任一非零类 a（即 gcd(a, n) = 1）由 Bézout 给出逆元（第二章）。反之若 n = ab 为合数（1 < a, b < n），则类 a 非零，却对任何 x 都有 ax ≠ 1：否则 ab·x ≡ b，即 0 ≡ b (mod n)，与 0 < b < n 矛盾。∎

域与环的分水岭是消去律：在域中，a ≠ 0 且 ab = ac 强制 b = c（两边乘 a⁻¹）；在一般环中可以失效——模 8 时 2·3 = 6 与 2·7 = 14 ≡ 6 相等，但 3 ≠ 7。第一章 3.3 证明里的「约分」动作，本质上就是在使用消去律；现在我们知道它的家：消去律住在域里。

第三章 同余方程与多项式3.7 Lagrange 多项式定理：根不超过次数

现在是全章的中心定理。它之优美，在于用一条几乎「显然」的归纳，守住了中学代数最有用的经验法则。

取 F = F_p，立刻得到：模素数 p 时，n 次同余方程至多 n 个根。域是本质——离开域，定理当场破产：

第三章 同余方程与多项式3.8 Lagrange 定理的证明：因式分解路线

证明只需要两块砖：因式定理与数学归纳。

引理（因式定理）　F 是域，f(x) 是多项式，a ∈ F。则 f(a) = 0 ⟺ f(x) = (x − a)·q(x)，其中 q 是低一次的多项式。

证明：用带余除法以 (x − a) 去除 f（在域上合法，因除数首项系数 1 可逆），得 f(x) = (x − a)q(x) + r，r 为常数。代入 x = a：f(a) = r。故 f(a) = 0 ⟺ r = 0。∎

定理的证明　对次数 n 归纳。n = 1 时 f(x) = ax + b（a ≠ 0），恰一根 x = −b/a。设结论对 n − 1 次成立。若 f（n 次）在 F 中没有根，结论显然。若有根 a，由因式定理 f(x) = (x − a)q(x)，q 恰 n − 1 次。对任何根 b ≠ a：0 = f(b) = (b − a)q(b)，而域中 b − a ≠ 0 可逆（且非零因子之积非零），故 q(b) = 0——b 是 q 的根。由归纳假设，q 至多 n − 1 个根，于是 f 至多 1 + (n − 1) = n 个根。∎

三处用到「域」：带余除法（首一除式总可做）、消去律（b − a 可逆）、非零因子之积非零。环里三处都会断裂——反例中 (x−1)(x+1) ≡ 0 (mod 8) 而 x = 3 使两因子 2 与 4 全非零。

第三章 同余方程与多项式3.9 完全分裂：x^p−1−1 在模 p 下的秘密

Fermat 小定理说：p 素数、p ∤ a 时 a^p−1 ≡ 1 (mod p)。翻译成多项式的语言：

而 f 的次数恰是 p − 1——根数顶满了次数！Lagrange 定理允许至多 p−1 个，Fermat 保证至少 p−1 个，于是：

「顶格」在数学里往往是财富的信号：取 x = 0 立得 Wilson 定理（3.10）；比较两边的系数还能榨出更多秘密（3.11 的交错和、第四章原根的存在性）。一个多项式能被自己的根们瓜分殆尽，称其完全分裂（splits completely）——这是域上多项式最理想的形态。

第三章 同余方程与多项式3.10 求和公式：1+2+⋯+(p−1)≡0 与 −1 的藏身处

完全分裂是一座富矿，先采第一桶：比较 x^p−1 − 1 与 (x−1)(x−2)⋯(x−(p−1)) 的中间系数之前，先看看「根之和」。按 Vieta 定理（根之和 = −(x^p−2 的系数)），而左边 x^p−1 − 1 根本没有 x^p−2 项——所以根之和必为 0：

（p 为奇素数时 (p−1)/2 是整数，故整个和是 p 的倍数；对 p = 13 验算：78 = 6·13 ✓。）同理根之平方和、立方和都是 0——左边那些系数位置全空着。这个「空位即零」的现象可以推广成漂亮的一般规律：

证明（群论一瞥）　取一个「生成元」——暂时承认存在 a 使 1, a, a², …, a^p−2 恰是 F_p 的全部非零元（第四章将证明原根存在）。则幂和 = a^k(1 + a^k + a^2k + ⋯ + a^(p−2)k)，等比求和 = a^k·(a^(p−1)k − 1)/(a^k − 1)。由 Fermat，a^(p−1)k ≡ 1；由 k ≤ p−2 知 p−1 ∤ k，故 a^k ≠ 1，分母非零可除。整个式子 ≡ 0。∎

第三章 同余方程与多项式3.11 Wilson 定理的代数再证：交错和路线

第二章我们用「舞会配对」给过 Wilson 定理一个组合证明。完全分裂给出一条惊人的短路——一行代入：

定理与证明（Wilson，代数版）　p 素数 ⟺ (p − 1)! ≡ −1 (mod p)。

（⟸ 即第二章配对证明，此处证 ⟹。）在恒等式 x^p−1 − 1 ≡ (x−1)(x−2)⋯(x−(p−1)) (mod p) 中取 x = 0：左边 = −1；右边 = (−1)(−2)⋯(−(p−1)) = (−1)^p−1(p−1)!。p 为奇素数时 (−1)^p−1 = 1，立得 (p−1)! ≡ −1 (mod p)。∎

同一个定理，两条路：配对路线在乘法群里找各自的舞伴 a·a′ ≡ 1，落单的 1 与 p−1 相乘得 −1；多项式路线把 (p−1)! 认作完全分裂的常数项。一个用「群」，一个用「环」，在 −1 处会师——这正是现代数学的趣味：同一事实在不同结构下的两个化身。

第三章 同余方程与多项式3.12 降次与配方：解多项式同余方程的技巧

有了理论，回到手艺。解高次同余方程的两把常用扳手：

第三章 同余方程与多项式3.13 丢番图方程的门槛：x²+y²=p 的同余侧写

费马晚年给友人的信里写下：奇素数 p 能写成两平方之和 p = a² + b² ⟺ p ≡ 1 (mod 4)。完整定理（含唯一性）在第五章之后才够得着；但它的同余侧影本章就能看清一半。

考虑同余方程 x² + y² ≡ 0 (mod p)。若存在解 (x, y) 且 p ∤ y，则 (xy⁻¹)² ≡ −1 (mod p)：−1 在 F_p 中可开平方。反之，若 −1 有平方根 r，则 (r, 1) 就是解。于是：

而 −1 可开平方当且仅当 p ≡ 1 (mod 4)（配对论证：模 4 意义下平方只能取 0 或 1，故 (p−1)/2 为偶数时……完整两行证明留给习题课）。这解释了 3.5 的那张表：x² + 1 ≡ 0 在模 5、模 13（皆 ≡ 1 (mod 4)）下有两根，在模 3、模 7（皆 ≡ 3 (mod 4)）下无根。数 p = 13 = 2² + 3² 提供了活样本：2² + 3² = 13 ≡ 0 (mod 13)，且 3·2⁻¹ = 3·7 = 21 ≡ 8，而 8² = 64 ≡ −1 (mod 13) ✓。

第三章 同余方程与多项式3.14 组合数论初谈：二项式系数 mod p

多项式世界里最著名的恒等式非二项式定理莫属。模 p 之下它骤然变美：

证明　C(p, k) = p(p−1)⋯(p−k+1) / k!。分子是 p 的倍数；分母 k! 的每个因子都小于 p，故 p ∤ k!。分子里的 p 与分母互素，约分后 p 依然整除整个分数——即 C(p, k) 是 p 的倍数。∎

于是模 p 时中间的 C(p,1), …, C(p,p−1) 全部熄灭，二项式定理坍缩成两行：

这不是 p 的专利，而是一般规律（对任意 k）的特例：C(n, k) mod p 由 n 与 k 的 p 进制数字决定——这就是Lucas 定理（综合站挑战二给出组合证明）。先尝一口：C(10, 3) = 120 ≡ 1 (mod 7)；而 10 = (13)₇、3 = (03)₇，按位组合 C(1,0)·C(3,3) = 1 ✓。数字对数字，逐位算，妙不可言。

第三章 同余方程与多项式3.15 Frobenius 映射：x↦x^p 的代数之美

把 3.14 的坍缩式 (1 + x)^p ≡ 1 + x^p 换一种读法：映射 σ : x ↦ x^p 竟然保加法：

在整数世界这是彻头彻尾的错误（(2+3)⁵ = 3125 ≠ 275 = 2⁵ + 3⁵）；在模 5 的世界里它突然成立：7⁵ ≡ 7·7⁴ ≡ 7·1 = 2？等等，直接算：7⁵ mod 5 = 2⁵ mod 5 = 32 mod 5 = 2；而 3⁵ + 4⁵ mod 5 = 3 + 4 = 7 ≡ 2 ✓。坍缩式让中间系数集体归零，恒等式起死回生。

「保运算的映射」是现代代数的核心词汇：群里叫同态，环/域里叫同态或自同构。σ 在 F_p 内看起来无所作为（恒等），但在更大的域 F_p²、F_pⁿ（第四章后会见到的「扩域」）里，σ 是货真价实的非平凡对称——现代数论（乃至椭圆曲线密码学）的机器上，Frobenius 是转得最勤的那颗齿轮。

第三章 同余方程与多项式3.16 解数统计：同余方程解的个数的组合意义

现在把本章散落的观察收拢成一条定理——它是「根数」问题的完整答案，也是第四章指标法的地基。

对账（p = 13，p − 1 = 12）：x³ ≡ 1 有 gcd(3, 12) = 3 个根 {1, 3, 9} ✓（3.12 的配方亲手算出）。x³ ≡ 2：判据要求 2^12/3 = 2⁴ = 16 ≡ 3 ≢ 1，无解 ✓（枚举确认）。x³ ≡ 8：8⁴ = 4096 = 315·13 + 1 ≡ 1，有解且恰 3 个——枚举给出 {2, 5, 6} ✓。x⁴ ≡ 2 (mod 11)：gcd(4, 10) = 2，判据要 2^10/2 = 2⁵ = 32 ≡ 10 ≢ 1 (mod 11)，无解 ✓；x⁴ ≡ 3 (mod 11)：3⁵ = 243 ≡ 1 (mod 11)，有解恰 2 个 {4, 7} ✓。

第三章 同余方程与多项式3.17 现代接口：线性同余随机数生成器——LCG 的设计〔密码〕

计算机需要「随机数」，但机器只会做确定性的算术。最老牌的方案是线性同余生成器（LCG）：

——一个线性同余方程的迭代！本章的武器立刻能分析它。设计者最关心周期：序列迟早进入循环（抽屉原理，第二章），最好循环遍历全部 m 个状态（满周期）。Hull–Dobell 定理（1958）给出满周期的充要条件：

第三章 同余方程与多项式3.18 本章总结与方法表

本章完成了从「算术」到「代数」的关键一跃：把同余世界升格为域 F_p，让中学多项式代数全面回归，再靠 Lagrange 定理守住「根不超过次数」的底线。

第三章 同余方程与多项式例1 线性同余方程：解 4x≡2(6)

题　解同余方程 4x ≡ 2 (mod 6)。

规范解答　按三步流程走：

第一步（判存在）　g = gcd(4, 6) = 2，且 2 | 2 ✓，方程有解，解数恰为 2。

第二步（求特解）　用 Bézout 显式求 u：解 4u + 6v = 2，即 2u + 3v = 1，取 u = 2, v = −1（4·2 − 6 = 2 ✓）。按公式 x₀ = u·(b/g) = 2·1 = 2。检验：4·2 = 8 ≡ 2 (mod 6) ✓。

第三步（写通解）　x ≡ x₀ + k·(n/g) = 2 + 3k (mod 6)，k = 0, 1。故 x ≡ 2, 5 (mod 6)。

复核　4·5 = 20 = 3·6 + 2 ≡ 2 ✓。剩余四类 0, 1, 3, 4 代入：4·0=0, 4·1=4, 4·3=12≡0, 4·4=16≡4，均不为 2。恰 2 解，与判据「解数 = g = 2」完全一致。

第三章 同余方程与多项式例2 判据三连：无解、一解、多解的辨析

题　判别下列方程解的情况并求解：(a) 4x ≡ 3 (mod 6)；(b) 3x ≡ 2 (mod 7)；(c) 4x ≡ 2 (mod 6)。

解　(a) g = gcd(4, 6) = 2，3 不被 2 整除——无解。理由具象化：4x 恒为偶数，8x−3… 更直接：4x ≡ 3 (6) 要求 6 | 4x − 3，而 4x − 3 是奇数，不可能被偶数 6 整除。左边的「公因子 2」锁死了右边。

(b) g = gcd(3, 7) = 1，g | 2 ✓，恰一解。3 的逆元 mod 7：3·5 = 15 ≡ 1，逆为 5。x ≡ 5·2 = 10 ≡ 3 (mod 7)。检验：3·3 = 9 ≡ 2 ✓。

(c) 即例 1：x ≡ 2, 5 (mod 6)，恰两解。

第三章 同余方程与多项式例3 非互素模联立：含公因子的方程组

题　解方程组 x ≡ 2 (mod 6)，x ≡ 5 (mod 9)。注意两个模不互素——CRT 的「两两互素」前提失效了，怎么办？

相容性检查　g = gcd(6, 9) = 3。判据：两余数必须模 g 相等。2 mod 3 = 2，5 mod 3 = 2 ✓，相容（若第二式是 x ≡ 4 (9)，则 4 mod 3 = 1 ≠ 2，立判无解）。

求解　由第一式写通解 x = 2 + 6t，代入第二式：

这是线性方程，g = gcd(6, 9) = 3 | 3 ✓，恰 3 个解。约去 3：2t ≡ 1 (mod 3)，t ≡ 2 (mod 3)，即 t = 2 + 3s。代回：

复核　14 mod 6 = 2 ✓；14 mod 9 = 5 ✓。解在模 lcm(6, 9) = 18 意义下唯一——不互素时，「模 M 唯一」换成「模 lcm 唯一」，其余照旧。

第三章 同余方程与多项式例4 多项式求根：x²+1≡0(5) 的枚举

题　求 x² + 1 ≡ 0 (mod 5) 的全部解。

解　二次式，模 5 只有五个候选，逐一开列平方表：

根为 x ≡ 2, 3 (mod 5)，恰两个，顶满二次的次数红线（Lagrange 允许至多 2）。

结构注记　3 ≡ −2 (mod 5)：两根成 ± 对——x² + 1 = 0 的根必然如此（若 r² ≡ −1 则 (−r)² ≡ −1，且 r ≢ −r 因 p ∤ 2r）。所以枚举其实只需查一半：找到 r = 2，对称根 −2 ≡ 3 自动奉上。

第三章 同余方程与多项式例5 Lagrange 定理应用：x³−x≡0(7) 的全部解

题　求 x³ − x ≡ 0 (mod 7) 的全部解，并用 Lagrange 定理解读。

解　先因式分解（在域上合法，就是中学代数）：

域中乘积为零必须某个因子为零：x ≡ 0, 1, 6。恰 3 个解。

解读　三次方程、三个根——顶格但不算完全分裂：0 也是根，而完全分裂（3.9）特指 x^p−1 − 1 型、根恰为全部非零元的情形。若把 0 的因式也收入，x³ − x 在 F_7 中同样被自己的根瓜分干净：x(x−1)(x−6)。Lagrange 定理的两重信息都在：根不越 3 条红线；真到 3 条时，分解必然发生。

第三章 同余方程与多项式例6 完全分裂：x^p−1−1 mod 7 的因式分解

题　在 F_7 中把 x⁶ − 1 分解为一次因式之积，并验证。

解　3.9 定理直接给出：

验证一（根）　每个非零元的六次幂都是 1（Fermat）：如 2⁶ = 64 = 63 + 1 ≡ 1 ✓，3⁶ = 729 = 7·104 + 1 ≡ 1 ✓。六个根一个不缺。

验证二（系数）　右边展开的 x⁵ 系数 = −(1+2+⋯+6) = −21 ≡ 0 (mod 7)，与左边（无 x⁵ 项）吻合；常数项 = (−1)⁶·6! = 720 = 7·102 + 6 ≡ 6 ≡ −1，与左边常数 −1 吻合——Wilson 定理 mod 7 顺手复核 ✓。

第三章 同余方程与多项式例7 降次技巧：x³≡1(13) 的全部解

题　求 x³ ≡ 1 (mod 13) 的全部解。

预判　d = 3，g = gcd(3, 12) = 3，方程恰有 3 个根（3.16 定理①）。目标明确：找齐三个。

解　x³ − 1 = (x − 1)(x² + x + 1)。x = 1 是显根。对二次因子配方（两边乘 4）：

查平方表 mod 13：1²=1, 2²=4, 3²=9, 4²=3, 5²=12, 6²=36≡10 ✓。故 2x + 1 ≡ ±6，即 2x ≡ 5 或 2x ≡ −7 ≡ 6。乘 2 的逆（2·7 = 14 ≡ 1，逆为 7）：

全部解 x ≡ 1, 3, 9 (mod 13)。复核：3³ = 27 = 26 + 1 ≡ 1 ✓；9³ = 729 = 13·56 + 1 ≡ 1 ✓。

第三章 同余方程与多项式例8 配方法：x²≡a(p) 的尝试与失败启示

题　在 F_7 中解 (a) x² ≡ 2 (mod 7)；(b) x² ≡ 3 (mod 7)。

解　先建平方值总表（只需算到 3，其余由 ± 对称补齐）：

(a) 2 在表中（来自 x = ±3），故 x ≡ 3, 4 (mod 7)。复核：3² = 9 ≡ 2 ✓，4² = 16 = 14 + 2 ≡ 2 ✓。

(b) 3 不在表中（平方值只能取 {0, 1, 2, 4}），故无解。七个候选逐一排除——枚举即完备证明。

失败启示　同一模数之下，有的 a 开得平方、有的开不得：{1, 2, 4} 是「二次剩余」（QR），{3, 5, 6} 是「非剩余」（QNR）。这不是技巧问题，而是 F_7 的结构性事实。三个问题自然涌出：如何不枚举就判定 a 是否 QR？QR 与 QNR 的分布有什么规律？不同素数之间有何关联？——这三问正是第五章的全部议程，互反律将在第三问处轰然登场。

第三章 同余方程与多项式例9 组合数 mod p：C(10,3) mod 7 的对账

题　求 C(10, 3) mod 7，并用 Lucas 定理的「逐位法」对账。

直算　C(10, 3) = 10·9·8 / 6 = 120，而 120 = 17·7 + 1，故 C(10, 3) ≡ 1 (mod 7)。

Lucas 对账　把 n 与 k 写成 7 进制：10 = 1·7 + 3 → (1, 3)₇；3 = 0·7 + 3 → (0, 3)₇。逐位取组合数再相乘：

再来一例（得 0 的情形）　C(14, 5) = 2002 = 286·7，≡ 0 (mod 7)。逐位：14 = (2, 0)₇，5 = (0, 5)₇ → C(2, 0)·C(0, 5) = 1·0 = 0 ✓。个位上「5 里取 5」超出了 0 的容量——低位借不出东西，组合数当场清零。

第三章 同余方程与多项式例10 Frobenius：(x+y)⁵≡x⁵+y⁵ 的验算

题　在 F_5 中验证 (3 + 4)⁵ ≡ 3⁵ + 4⁵ (mod 5)，并展示中间项的去向。

解　左边：3 + 4 = 7 ≡ 2，2⁵ = 32 ≡ 2 (mod 5)。右边：3⁵ ≡ 3、4⁵ ≡ 4（Fermat），3 + 4 = 7 ≡ 2。两边同为 2 ✓。

中间项去向　按二项式定理完整展开：

五个中间系数 C(5,1) = 5, C(5,2) = 10, C(5,3) = 10, C(5,4) = 5，全是 5 的倍数——每一项都被模 5 吞掉：10·3³·4² = 4320 = 864·5 ✓，10·3²·4³ = 5760 = 1152·5 ✓。中间项不是「约等于零」，是精确地为 5 的倍数。

换一组数再验　(2 + 3)⁵ = 5⁵ ≡ 0 (mod 5)；2⁵ + 3⁵ = 32 + 243 = 275 = 55·5 ≡ 0 ✓——连「和是模的倍数」这一退化情形都严丝合缝。

第三章 同余方程与多项式例11 解数统计：一张「方程—解数」对账表

题　汇总本章出现过的二项方程，用判据统一对账。

读表　七行全部对上：「理论解数」一列由 gcd 与 Euler 型判据一锤定音，「实际解」由枚举或降次配方领出——无一例外。特别留意 x⁴ ≡ 3 (11) 复核：4⁴ = 256 = 23·11 + 3 ✓，7⁴ = 2401 = 218·11 + 3 ✓。

第三章 同余方程与多项式例12 综合：从线性到多项式的完整求解流程

题　解 3x² + 2x − 1 ≡ 0 (mod 11)。

第一步（定策略）　模 11 是素数，F_11 是域：配方合法、消去律成立、Lagrange 红线生效（至多 2 根）。

第二步（配方）　两边乘 3 的对偶数 12（即 4·3 = 12 ≡ 1，先乘 4·3 化首项为平方）：更直接地按通式 (2ax + b)² ≡ b² − 4ac 配方：

第三步（开平方）　查平方表 mod 11：1, 4, 9, 16≡5, 25≡3 → 4² ≡ 5 ✓。故 6x + 2 ≡ ±4。

第四步（解线性方程）　6x ≡ 2 或 6x ≡ −6 ≡ 5。6 的逆：6·2 = 12 ≡ 1，逆为 2。x ≡ 2·2 = 4，或 x ≡ 5·2 = 10。

复核　x = 4：3·16 + 8 − 1 = 55 = 5·11 ✓。x = 10 ≡ −1：3 − 2 − 1 = 0 ✓（对称根藏得深：x = −1 竟是精确根，因 3·1 − 2 − 1 = 0 也整除——多项式恰有整根分解 (3x − 1)(x + 1)）。两根 {4, 10}，恰 2 个，顶格。

第三章 同余方程与多项式习题课一 线性同余方程

练 1.1　解 6x ≡ 3 (mod 9)。提示：g = gcd(6, 9) = 3，3 | 3 ✓，恰 3 解。约去 g：2x ≡ 1 (mod 3)，x₀ ≡ 2 (mod 3)，通解 x = 2 + 3k。答案：x ≡ 2, 5, 8 (mod 9)。检验：6·5 = 30 = 3·9 + 3 ≡ 3 ✓。

练 1.2　解 10x ≡ 6 (mod 14)。提示：g = 2，约成 5x ≡ 3 (mod 7)；5 的逆 mod 7 是 3（5·3 = 15 ≡ 1），x₀ ≡ 3·3 = 9 ≡ 2 (mod 7)，通解 x ≡ 2, 9 (mod 14)。检验：10·9 = 90 = 6·14 + 6 ✓。

练 1.3　判断有无解：7x ≡ 4 (mod 21)。提示：g = gcd(7, 21) = 7，7 ∤ 4 → 无解。换个看法：7x 是 7 的倍数，7x − 4 ≡ −4 (mod 7) 永不为 0，更不可能被 21 整除。

练 1.4　解 8x ≡ 12 (mod 28)，并数一数解的个数与 gcd 的关系。提示：g = 4，12/4 = 3，约成 2x ≡ 3 (mod 7)，x₀ ≡ 3·4 = 12 ≡ 5 (mod 7)（2 的逆是 4），通解 x = 5 + 7k，模 28 得 x ≡ 5, 12, 19, 26，恰 g = 4 个解。

第三章 同余方程与多项式习题课二 解的个数判据

练 2.1　不解方程，只报解数：(a) 15x ≡ 10 (mod 25)；(b) 12x ≡ 9 (mod 28)；(c) 9x ≡ 12 (mod 15)。提示：(a) g = 5 | 10 → 5 解；(b) g = 4 ∤ 9 → 无解；(c) g = 3 | 12 → 3 解。判据先行，一望即答。

练 2.2　a 取何值时，ax ≡ 1 (mod 35) 恰有一解？提示：g = gcd(a, 35) = 1，即 a 与 35 = 5·7 互素：a 不是 5 的倍数也不是 7 的倍数。乘法群 (ℤ/35)× 有 φ(35) = 24 个成员，个个都可作为 a。

练 2.3　判断 2x ≡ 7 (mod 10⁶) 的解的情况并说明理由。提示：g = gcd(2, 10⁶) = 2，而 2 ∤ 7 —— 无解。最快看法：模 2 下左边 2x ≡ 0、右边 7 ≡ 1，当场矛盾。「数字大」不改变判据，gcd 才是一切。

第三章 同余方程与多项式习题课三 非互素模联立

练 3.1　判断相容性并求解：x ≡ 3 (mod 8)，x ≡ 7 (mod 12)。提示：g = gcd(8, 12) = 4；3 mod 4 = 3，7 mod 4 = 3 ✓ 相容。x = 3 + 8t ≡ 7 (12)：8t ≡ 4 (12)，g = 4 | 4，约成 2t ≡ 1 (3)，t ≡ 2 (3)，x = 3 + 8·2 = 19，模 lcm(8,12) = 24 唯一。检验：19 mod 8 = 3 ✓，19 mod 12 = 7 ✓。

练 3.2　判断相容性：x ≡ 5 (mod 9)，x ≡ 6 (mod 12)。提示：g = 3；5 mod 3 = 2，6 mod 3 = 0，不相等 → 无解。不互素联立的第一步永远是这道「模 gcd 比对」的快检。

练 3.3　一个数除以 6 余 4，除以 10 余 8，除以 15 余 13，求最小的它。提示：三对模的 gcd：gcd(6,10) = 2，4 ≡ 8 ≡ 0 (2) ✓；gcd(6,15) = 3，4 ≡ 13 ≡ 1 (3) ✓；gcd(10,15) = 5，8 ≡ 13 ≡ 3 (5) ✓。相容！注意三式都是「余数比模少 2」：x + 2 同时被 6, 10, 15 整除，即 30 | x + 2，最小正解 x = 28。验算：28 = 4·6 + 4 ✓ = 2·10 + 8 ✓ = 15 + 13 ✓。「不整齐的余数」背后是「整齐的 x + 2」——观察结构胜过套公式。

第三章 同余方程与多项式习题课四 多项式的根

练 4.1　求 x² ≡ 1 (mod 8) 的全部解，并解释为什么 Lagrange 定理「管不着」它。提示：奇数平方 ≡ 1 (mod 8)，四解 {1, 3, 5, 7}。二次方程四根——因为 ℤ/8ℤ 不是域，红线只在域内生效。

练 4.2　求 x² + x + 1 ≡ 0 (mod 7) 的全部解。提示：配方 (2x + 1)² ≡ −3 ≡ 4 (7)，±2 → 2x ≡ 1 或 2x ≡ −3 ≡ 4 → x ≡ 4 或 2。两解 {2, 4}。顶格。

练 4.3　求 x³ − 1 ≡ 0 (mod 7) 的全部解。提示：x³ − 1 = (x − 1)(x² + x + 1)；由练 4.2（把 7 换成 7）二次因子在 mod 7 有两根 2, 4。三解 {1, 2, 4}。对账：gcd(3, 6) = 3 ✓ 恰三根。

练 4.4　f(x) = x² + 3x + 2 在 F_5 中有几个根？在 ℤ/6ℤ 中呢？提示：F_5：f = (x + 1)(x + 2)，根 {3, 4}（−1 ≡ 4, −2 ≡ 3），恰两根。ℤ/6ℤ：逐个验 x = 0..5：0→2, 1→6≡0 ✓, 2→12≡0 ✓, 3→20≡2, 4→30≡0 ✓, 5→42≡0 ✓——四根 {1, 2, 4, 5}！非零因子（2·3 ≡ 0）让 (x+1)(x+2) ≡ 0 不再强制单因子为零。

第三章 同余方程与多项式习题课五 Lagrange 定理

练 5.1　F_11 上 x⁴ + 5x² + 4 有几个根？先推理再验证。提示：x⁴ + 5x² + 4 = (x² + 1)(x² + 4)。F_11 中 −1 是 QR 吗？平方表 mod 11：{1, 4, 9, 5, 3}——无 10，−1 非 QR，x² + 1 无根。−4 ≡ 7 是 QR？表中无 7，x² + 4 无根。故 0 个根。四次方程零根，Lagrange 只给上界不给下界。

练 5.2　证明：F_p 上 n 次多项式若有多于 n 个根，则它必是零多项式（所有系数 ≡ 0）。提示：这正是 3.9 完全分裂证明里用过的推理——f − g 至多 n 个根，除非恒为零。反证即得。

练 5.3　F_7 上是否存在二次多项式恰好有 1 个根？举一例。提示：x² ≡ 0 只有根 x = 0（域中 x² = 0 ⟹ x = 0），恰一根——重根只算一个根。另一例：(x − 1)² = x² − 2x + 1，根仅 x = 1。「根计重不记重」时恰一根完全可能。

第三章 同余方程与多项式习题课六 完全分裂

练 6.1　在 F_5 中展开 (x − 1)(x − 2)(x − 3)(x − 4)，验证它 ≡ x⁴ − 1 (mod 5)。提示：逐系数对账：x³ 系数 −(1+2+3+4) = −10 ≡ 0 ✓；x² 系数 = 两两乘积和 = 35 ≡ 0 ✓（35 = 5·7）；x 系数 = 三三乘积和 = 50 ≡ 0 ✓；常数 (−1)⁴·4! = 24 ≡ −1 ✓（Wilson mod 5）。

练 6.2　计算 1·2·3·⋯·6 mod 7 与 1·2·⋯·10 mod 11，用两种方法。提示：法一（Wilson）：6! ≡ −1 ≡ 6 (7)；10! ≡ −1 ≡ 10 (11)。法二（硬乘）：720 ≡ 6 (7) ✓；3628800 = 329891·11 − 1 ≡ 10 (11) ✓。

练 6.3　p = 2 时 Wilson 定理还成立吗？x^p−1 − 1 的完全分裂呢？提示：1! = 1 ≡ −1 ≡ 1 (2) ✓ 成立。x¹ − 1 = x − 1 ≡ x − 1，根集 {1}（F_2 的唯一非零元），完全分裂同样成立——只是「非零元」只剩一个，故事缩短了。

第三章 同余方程与多项式习题课七 降次与配方

练 7.1　解 x³ ≡ 8 (mod 13)。提示：x³ − 8 = (x − 2)(x² + 2x + 4)。试出根 x = 2。配方：(2x + 2)² ≡ 4 − 16 = −12 ≡ 1 (13)，2x + 2 ≡ ±1 → x ≡ −1·7 = −7 ≡ 6 或 x ≡ −3·7 = −21 ≡ 5。三解 {2, 5, 6}，与例 11 对账表一致 ✓（判据 gcd(3,12) = 3）。

练 7.2　解 x² − 4x + 1 ≡ 0 (mod 11)。提示：配方 (2x − 4)² ≡ 16 − 4 = 12 ≡ 1，2x − 4 ≡ ±1 → x ≡ 5·6 = 30 ≡ 8 或 x ≡ 3·6 = 18 ≡ 7（6 是 2 的逆 mod 11）。检验：64 − 32 + 1 = 33 = 3·11 ✓；49 − 28 + 1 = 22 ✓。

练 7.3　解 x² + x ≡ 4 (mod 9)。这里模是合数，配方还灵吗？提示：4(x² + x) ≡ 16，(2x + 1)² ≡ 17 ≡ 8 (9)。逐一检查平方 mod 9：{0, 1, 4, 7}——8 不在其中，无解。配方在合数模下仍可尝试（乘 4 的可逆性没问题：gcd(4, 9) = 1），但「开平方」的枚举账本要按合数模自己的平方表来。谨慎：配方步骤合法 ⟺ 所乘的系数与模互素。

第三章 同余方程与多项式习题课八 组合数 mod p

练 8.1　求 C(7, 2) mod 7 与 C(7, 3) mod 7，并用 3.14 命题解释。提示：C(7,2) = 21 ≡ 0；C(7,3) = 35 ≡ 0。中间系数全部熄灭——素数模的标志。

练 8.2　用 Lucas 逐位法求 C(16, 4) mod 7。提示：16 = (2, 2)₇，4 = (0, 4)₇ → C(2,0)·C(2,4) = 1·0 = 0。直算验证：C(16,4) = 1820 = 260·7 ✓。

练 8.3　用 Lucas 逐位法求 C(21, 7) mod 7，再用直接计算复核。提示：21 = (3, 0)₇，7 = (1, 0)₇ → C(3,1)·C(0,0) = 3。直算：C(21,7) = 116280 = 16611·7 + 3 ✓。

练 8.4　(1 + x)⁶ 在 F_3 中的展开式是什么？提示：先按二项式定理写出系数 1, 6, 15, 20, 15, 6, 1，模 3 得 1, 0, 0, 2, 0, 0, 1 → (1 + x)⁶ ≡ 1 + 2x³ + x⁶ = (1 + x³)² (mod 3)。这正是一般规律 (1+x)^ab ≡ (1+x^a)^b 的特例——Lucas 定理的多项式面孔。

第三章 同余方程与多项式习题课九 Frobenius 映射

练 9.1　在 F_7 中验证 (5 + 4)⁷ ≡ 5⁷ + 4⁷ (mod 7)。提示：两边都 ≡ 5 + 4 = 9 ≡ 2（Fermat：a⁷ ≡ a）。左边硬算亦可：(9)⁷ = 9·(9⁶) ≡ 9·1 = 2 (7) ✓。

练 9.2　证明：σ(x) = x^p 保持「减法」，即 (x − y)^p ≡ x^p − y^p (mod p)。提示：σ(x − y) = σ(x + (−y)) = σ(x) + σ(−y) = σ(x) + (−y)^p = x^p − y^p（p 奇时 (−y)^p = −y^p；p = 2 时 −1 ≡ 1 依然成立）。

练 9.3　F_5 中解方程 x⁵ = x 的全部解。提示：x⁵ − x = x(x⁴ − 1) = x(x − 1)(x + 1)(x² + 1)。F_5 中 x² + 1 的根是 ±2（例 4），故解为全部五个元素 {0, 1, 2, 3, 4}——Frobenius 的不动点恰是整个域，这正是 3.15 的「σ = 恒等」。

第三章 同余方程与多项式习题课十 解数统计

练 10.1　不解方程，报出解数：(a) x⁵ ≡ 1 (mod 11)；(b) x⁵ ≡ 1 (mod 31)；(c) x⁶ ≡ 1 (mod 13)。提示：(a) gcd(5, 10) = 5 → 5 解；(b) gcd(5, 30) = 5 → 5 解；(c) gcd(6, 12) = 6 → 6 解。三个「5 次单位根」「6 次单位根」的群——第四章将给它们正式的名字。

练 10.2　p = 17 时，x⁴ ≡ a (mod 17) 对多少个 a（1 ≤ a ≤ 16）有解？提示：g = gcd(4, 16) = 4。幂映射 x ↦ x⁴ 把 16 个非零元压成 16/4 = 4 个像点，每个像点上方 4 层——恰有 4 个 a 有解，每个恰 4 个根。有解判据：a⁴ ≡ 1 (17)。

练 10.3　x⁴ ≡ 3 (mod 17) 有解吗？再找出 F_17 中所有「四次幂像点」a（即存在 x 使 a = x⁴）。提示：判据 3⁴ = 81 = 4·17 + 13 ≡ 13 ≢ 1 (17)，不过关 → x⁴ ≡ 3 无解。像点：由练 10.2 知共 4 个，逐个验证 a⁴ ≡ 1：1⁴ = 1 ✓，4⁴ = 256 = 15·17 + 1 ✓，13⁴ ≡ (−4)⁴ = 4⁴ ≡ 1 ✓，16⁴ ≡ (−1)⁴ = 1 ✓（其余 a⁴ ≢ 1，可抽查 2⁴ = 16 ≢ 1）。像点集 = {±1, ±4}。

第三章 同余方程与多项式习题课十一 综合训练

练 11.1（线性 + 联立）　解方程组 2x ≡ 4 (mod 6)，5x ≡ 3 (mod 8)。提示：第一式 g = 2 | 4，约成 x ≡ 2 (3)；第二式 g = 1，5 的逆 mod 8 是 5，x ≡ 15 ≡ 7 (8)。联立（互素模）：x ≡ 2 (3) 且 x ≡ 7 (8)。x = 2 + 3t ≡ 7 (8)：3t ≡ 5，t ≡ 5·3 = 15 ≡ 7 (8)（3 的逆是 3），x = 2 + 21 = 23，模 24 唯一。检验：2·23 = 46 = 7·6 + 4 ✓；5·23 = 115 = 14·8 + 3 ✓；23 mod 3 = 2 ✓、23 mod 8 = 7 ✓。

练 11.2（多项式 + 判据）　F_13 中 x⁶ ≡ 1 的六个根恰为 QR 集 {1, 3, 4, 9, 10, 12}——验证并解释。提示：逐个平方：1²=1, 3²=9, 4²=16≡3, 9²=81≡3? —— 81 = 6·13 + 3 ≡ 3？不对，9² = 81 ≡ 3，再平方 3² = 9：9⁴ ≡ 9？慢。x⁶ = (x²)³：QR 的三次方？更直接：逐个算 x⁶：1⁶=1 ✓；3⁶ = 729 = 56·13 + 1 ✓；4⁶ = 4096 = 315·13 + 1 ✓；9⁶ = (9²)³ = 3³ = 27 ≡ 1 ✓；10⁶ = (10²)³ = 9³ = 729 ≡ 1 ✓；12⁶ = (−1)⁶ = 1 ✓。六个 QR 全部通过。解释：p = 13 时 x⁶ = x^(p−1)/2，而第五章的 Euler 判据将证明这个量恒为 ±1，且「取 +1」恰好刻画二次剩余——于是 x⁶ ≡ 1 的解集（六次单位根群）与 QR 集天然重合。这里先把巧合验到手，判据的证明留给第五章。

练 11.3（LCG 逆向）　某 LCG 满足 x_n+1 = a·x_n + c (mod 16)，已知三个连续输出 3, 11, 7，问这样的 (a, c) 存在吗？提示：列方程 3a + c ≡ 11、11a + c ≡ 7 (16)，相减得 8a ≡ −4 ≡ 12 (16)。判据：g = gcd(8, 16) = 8 ∤ 12，无解——三个数不可能出自任何 LCG(16)。这正演示了 LCG 的可验伪性：输出满足刚性线性约束，乱造的数骗不过它。

第三章 同余方程与多项式复盘：错题归档与三问自测

高频错点归档（本章练习中最容易失手的三处）：

三问自测（合上书回答）：

一问：4x ≡ 2 (mod 6) 为什么恰有两个解？说出定理名与证明的关键一步。提示：解数定理（3.3）；关键：两解之差被 n/g 整除——约去 g 后用消去律。

二问：Wilson 定理的组合证明与代数证明各用了什么结构？提示：乘法群 F_p^× 的配对（群）与 x^p−1 − 1 的完全分裂（域上多项式环）。

三问：为什么 x^d ≡ 1 (mod p) 的根数恰好是 gcd(d, p − 1)？提示：完整答案在第四章指标法；本章层面可答「幂映射的分层结构」：d 次幂的像点是 (p−1)/g 个，每个上方 g 层。

第三章 同余方程与多项式格物札记① 秦九韶「正负开方术」与 Horner：多项式求根的东方先声〔少广〕

《数书九章》（1247）少广章中，秦九韶给出高次方程数值解的完整算法——「正负开方术」：反复通过「随乘随加」逐位逼近方程的根。这与西方 1819 年 Horner 发表的方法在算法结构上完全一致，早了近六百年。其核心引擎，就是今天计算机里求多项式值的秦九韶算法（嵌套乘法）：

从最内层括号起步，每一步只做「乘 x、加下一系数」：四次乘法、四次加法搞定四次多项式——比逐项展开经济得多。以 x = 2 为例：3 → 3·2+2 = 8 → 8·2−1 = 15 → 15·2+0 = 30 → 30·2+5 = 65。验算：3·16 + 2·8 − 4 + 5 = 65 ✓。

第三章 同余方程与多项式格物札记② 从 Fermat 小定理到有限域：F_p 的完整画像

三章读罢，是时候把 F_p 的「户口档案」整理成一张画像。它有两副面孔：

两副面孔合起来，Fermat、Euler、Wilson、Lagrange（多项式版）四个定理各归其位：

第三章 同余方程与多项式章小结：知识图谱与方法表

本章是全书的「代数枢纽」：把前两章的群与环升格为域，让多项式代数全面回归，再以 Lagrange 定理为核心收割了一系列定理。知识图谱如下：

第三章 同余方程与多项式思想卡：有限世界的基本定理——根不会太多

三条延伸，各通向一个更大的世界：

其一（唯一性）：次数 ≤ n 的多项式由 n + 1 个点唯一决定——Lagrange 插值公式。这把「多项式」变成了「点值的另一种编码」，密码学里的 Shamir 秘密分享正建于此。

其二（计数）：x^d ≡ 1 至多 gcd(d, p−1) 个根的精确版告诉我们：有限域上的「单位根群」规模有限、结构规整——这是第四章循环群解剖的入口。

其三（不可能性）：次数红线是「不可能证明」的万用模具：想证明某个方程无解？证出根数超线即可（如练 4.1 的 mod 8 四根反例堵死了「域化推广」）。负结果同样有形状。

第三章 同余方程与多项式挑战一 Lagrange 多项式定理的完整证明

任务　不看 3.8，独立完成四步证明。每步附自查点，闯关式推进。

第一步（带余除法）　证明：域 F 上，f(x) 除以 g(x)（g 首项系数 c ≠ 0）可得 f = gq + r，且 r = 0 或次数低于 g。自查：对 f 的次数归纳；除法每步用 c 的逆元——域在哪里出场？答：c 可逆。

第二步（因式定理）　推出 f(a) = 0 ⟺ (x − a) | f(x)。自查：取 g = x − a，余式 r 是常数且 r = f(a)。为什么 g 首项系数是 1？——所以除法永远合法。

第三步（归纳主体）　设 n 次多项式至多 n − 1 个根（归纳假设），证 n 次至多 n 个。自查：找到根 a 后，任何其他根 b 为什么自动是 q(x) = f(x)/(x − a) 的根？关键等式 0 = f(b) = (b − a)q(b) 中，「b − a ≠ 0 可逆」与「非零之积非零」都是域公理——在 ℤ/8ℤ 里指出这两个环节各自断裂的位置。

第四步（反例校准）　用 x² − 1 ≡ 0 (mod 8) 的四根 {1, 3, 5, 7} 逐条对照：哪一步在 ℤ/8ℤ 里失效？自查：b = 3 时 (b − 1) = 2 非零但不可逆；2·4 ≡ 0 是两个非零元之积为零。红线只在域内成立。

第三章 同余方程与多项式挑战二 Lucas 定理：二项式系数 mod p 的组合证明

目标定理　n = ap + r，k = bp + s（0 ≤ r, s ≤ p − 1），则 C(n, k) ≡ C(a, b)·C(r, s) (mod p)。

第一步（坍缩式升级）　由 (1 + x)^p ≡ 1 + x^p (mod p)，反复使用得 ((1 + x)^p)^a ≡ (1 + x^p)^a，故

第二步（比对系数）　右边展开：(1 + x^p)^a 贡献 x^bp 的系数 C(a, b) 乘 (1 + x)^r 中 x^s 的系数 C(r, s)——因为 x^k = x^{bp + s} 只能拆成「p 的倍数部分 + 余数部分」，而 (1+x)^r 的次数不足 p，两部分独立。自查：为什么没有其他组合贡献 x^k？——若 (1+x^p)^a 取 x^(b+1)p 次幂，则 (1+x)^r 需提供负次数，不可能；次数重叠的情形同理排除。

第三步（读出结论）　左边 x^k 的系数是 C(n, k)，右边是 C(a, b)C(r, s)，两边 mod p 相等，Lucas 定理到手。

对账三连：C(10, 3) mod 7 = C(1,0)·C(3,3) = 1（例 9）✓；C(14, 5) mod 7 = C(2,0)·C(0,5) = 0 ✓；C(21, 7) mod 7 = C(3,1)·C(0,0) = 3（练 8.3）✓。

第三章 同余方程与多项式实验：LCG 随机数可视化——点阵里的周期之舞

实验设计　把 LCG 的输出对 (x_n, x_n+1) 画成平面点阵：满周期的 LCG 应在 16×16 网格上盖出整齐的平行线族——「随机」的外表下藏着笔直的骨骼。本章以 m = 16 为例做手工版：

第三章 同余方程与多项式章测试与评讲

T1（存在与个数）　不解方程，判断下列各有几解：(a) 6x ≡ 4 (mod 10)；(b) 5x ≡ 12 (mod 18)。评讲：(a) g = 2 | 4 → 2 解；(b) g = 1 → 1 解。查的是 3.2/3.3 的判据条件反射。

T2（通解公式）　写出 6x ≡ 4 (mod 10) 的全部解。评讲：约成 3x ≡ 2 (5)，x₀ ≡ 2·2 = 4 (5)，通解 x ≡ 4, 9 (10)。错得最多的是漏解或写进模 5。

T3（CRT 对账）　x ≡ 1 (4) 且 x ≡ 3 (9)，求 x mod 36。评讲：x = 1 + 4t ≡ 3 (9) → 4t ≡ 2 → t ≡ 2·7 = 14 ≡ 5 (9)，x = 21。检验：21 mod 4 = 1 ✓，21 mod 9 = 3 ✓。探针法亦可：M₁y₁ = 9·9⁻¹(4)？M₁ = 9，9y ≡ 1 (4) → y ≡ 1，探针 9；M₂ = 4，4y ≡ 1 (9) → y ≡ 7，探针 28；x = 1·9 + 3·28 = 93 ≡ 21 (36) ✓。

T4（Lagrange）　F_11 中 x⁴ − 3x² + 2 有几个根？评讲：因式分解 (x² − 1)(x² − 2)。x² = 1 → x = ±1 = {1, 10}；x² = 2：平方表 mod 11 为 {1, 3, 4, 5, 9}，2 不在 → 无根。共 2 根，未顶格。

T5（完全分裂 + Lucas）　求 C(22, 6) mod 11，并说明用了哪条定理。评讲：22 = (2, 0)₁₁，6 = (0, 6)₁₁ → C(2,0)·C(0,6) = 1·0 = 0（Lucas）。机理追问：为什么低位是 0 就整体清零？——(1+x)^r 部分（r = 0）提供不出 x⁶。

T6（结构题）　举出一个「三次方程五根」的同余方程，并解释它不违反任何已证定理。评讲：x³ ≡ x (mod 6)（例 5 的换模快照）有六根，或 x³ ≡ x (mod 6) 的任一变形。不违反：6 非素数，ℤ/6ℤ 不是域，Lagrange 红线不适用——域假设是定理的岗位说明书。

第四章 原根与指标4.1 导引：乘法群的骨架——谁的幂走遍全群？

第二章末尾我们认识了乘法群 F_p^× = {1, 2, …, p−1}（模 p 乘法）；第三章末尾的幂映射分层图留下了悬念：x ↦ x⁴ 在 F_17 上是「4 层楼」，x ↦ x³ 在 F_13 上是「3 层楼」。楼层多寡不一——那么，谁的幂能走遍整座楼？

十二个不同的值——2 的幂恰好铺满全部非零元！这样的元素叫原根（primitive root）：它是整座乘法群的「一主齿轮」，转一圈把所有齿轮位都带到。本章的两大主角由此登场：证明原根总存在（Gauss 的成名作之一），并利用它建立指标（离散对数）——把乘法翻译成加法的对数表。

第四章 原根与指标4.2 元素的阶：定义与基本性质

阶为什么存在？Fermat 小定理担保 a^p−1 ≡ 1，候选集非空，正整数集中取最小——又是良序原理的手笔。阶的三条基本性质：

证明　① 带余除法 k = qn + r（0 ≤ r < n）：a^k = (aⁿ)^q·a^r ≡ a^r。故 a^k ≡ 1 ⟺ a^r ≡ 1；由 n 的最小性 r = 0，即 n | k。② 若 aⁱ ≡ a^j（0 ≤ i < j < n），则 a^j−i ≡ 1 且 0 < j − i < n，与最小性矛盾。③ 记 m = ord(a^k)。由 (a^k)ⁿ = (aⁿ)^k ≡ 1 知 m | n（用 ①）。又 (a^k)^n/g = a^k·n/g = (aⁿ)^k/g ≡ 1（g = gcd(n, k) 整除 k），故 m ≤ n/g。反过来 a^km ≡ 1 给 n | km，而 gcd(m, n) | m | km 且 gcd(m, n) | n，于是 n | gcd(m,n)·(km/gcd) …简明路线：n | km ⟺ (n/g) | (k/g)m，而 gcd(n/g, k/g) = 1，消去律给 (n/g) | m。两端夹住，m = n/g。∎

第四章 原根与指标4.3 阶的计算：穷举、约化与整除判定

把上一页的「判阶神器」整理成完整流程。给定 F_p 中元素 a（p 素数，p ∤ a）：

三步法的代价约为 O(log n) 次模幂——比逐个穷举 12 个幂快得多。它还揭示一个隐秘的对称：阶的判定全部发生在「n 的因子」层面上。这为 4.6 的群版 Lagrange（阶必整除 p − 1）做了数值铺垫。

第四章 原根与指标4.4 循环群与生成元：群论速成（二）

F_13^× 是循环群：⟨2⟩，因为 2 的幂铺满十二个非零元。循环群是结构最透明的群——整个群由一个元素复制而来，所有的元素都排成一条确定的环游路线。群论里证明「某群循环」是高奖赏动作：一旦成立，计数、子群、方程全都有现成答案。

举例：F_13^× = ⟨2⟩ 的生成元是 2^k（gcd(k, 12) = 1）：k = 1, 5, 7, 11 → 2¹ = 2, 2⁵ = 6, 2⁷ = 11, 2¹¹ = 7。原根 {2, 6, 7, 11}，恰 φ(12) = 4 个——数字完全咬合。

第四章 原根与指标4.5 循环群的子群：每阶恰有一个的独特风景

群论一般理论中，子群可以多到数不清；循环群却出奇地节制：

以 F_13^×（g = 2, n = 12）为例：d = 1, 2, 3, 4, 6, 12 各有一个子群，成员数正比于阶——其中 d = 6 的子群 ⟨2²⟩ = {1, 3, 4, 9, 10, 12} 恰是第二章的二次剩余集！这条暗线将在第五章开花。

第四章 原根与指标4.6 群版 Lagrange 定理：Fermat 小定理的代数再证

证明（陪集分拆）　对 g ∈ G，定义陪集 gH = {gh : h ∈ H}。① 每个陪集与 H 等势（乘 g 是双射）。② 两个陪集要么相等要么不交：g₁H ∩ g₂H ≠ ∅ 时，gh₁ = g₂h₂ → g₂ = g₁(h₁h₂⁻¹) ∈ g₁H → g₂H ⊆ g₁H，对称得相等。③ 每个元素属于某个陪集（g ∈ gH，因 e ∈ H）。于是 G 被切成若干等大的陪集块：|G| = (块数)·|H|。②中「陪集数 · |H|」的块数记 [G : H]，得 |G| = [G : H]·|H|。取 H = ⟨a⟩：|⟨a⟩| = ord(a) 整除 |G|，且 a^|G| = (a^ord(a))^|G|/ord(a) = e。∎

Fermat 小定理的三代证明就此同框：第二章的「项链翻转」（组合），Wilson 舞会配对（双射），本章的「陪集分拆」（结构）。第三个最抽象也最强大——它对任何有限群生效：Euler 定理 a^φ(n) ≡ 1（mod n，gcd(a,n)=1）不过是把群换成 (ℤ/n)× 的免费推论。

第四章 原根与指标4.7 原根的存在性（一）：素数模的构造性证明

本章最高峰。p 素数时，F_p^× 中必然存在阶为 p − 1 的元素。证明是一段漂亮的「计数拼图」：

第一步（定义计数函数）　对 d | p − 1，记 ψ(d) = F_p^× 中阶恰为 d 的元素个数。显然 Σ_{d | p−1} ψ(d) = p − 1（每个元素有唯一的阶）。

第二步（上界 ψ(d) ≤ φ(d)）　阶为 d 的元素都满足 x^d ≡ 1。分两情形：若阶 d 的元素一个也没有，ψ(d) = 0 ≤ φ(d)，完成。若有一个，设为 a：则 1, a, …, a^d−1 是 x^d ≡ 1 的 d 个互不相同的根（4.2 性质②），而第三章 Lagrange 说 x^d ≡ 1 至多 d 个根——所以它们是全部根，任何阶 d 的元素必须落在这个集合里。集合中阶恰为 d 的是哪些？a^k 的阶 = d/gcd(d, k)（4.2 性质③），恰为 d ⟺ gcd(k, d) = 1，共 φ(d) 个。故 ψ(d) ≤ φ(d)。

第三步（欧拉 φ 恒等式）　Σ_{d | n} φ(d) = n。证明：把分数 1/n, 2/n, …, n/n 按约分后的分母分类，分母为 d 的恰有 φ(d) 个，总数为 n。∎

第四步（合拢）　p − 1 = Σ ψ(d) = Σ φ(d) 且逐项 ψ(d) ≤ φ(d)——总和相等的逐项不等式强制处处相等：ψ(d) = φ(d) 对一切 d | p−1。特别地 ψ(p−1) = φ(p−1) ≥ 1：阶为 p − 1 的元素存在，即原根存在！∎

第四章 原根与指标4.8 原根的存在性（二）：全定理与边界

也就是说：除了 1, 2, 4 与「奇素数幂 ×1 或 ×2」这些形状，其余的模都没有原根。边界的两侧行为迥异：

失败的原因各有面目：模 2^k（k ≥ 3）的世界里，「±1 之外还有隐形的平方根」让阶永远上不去；模 15 则因 CRT 分解成两个互素世界的直积，两个循环群的公共节拍凑不满一整圈（群论语言：直积的元素阶是 lcm，15 时 lcm(2, 4) = 4 < 8）。定理的完整证明在本章挑战范围之外（涉及对 2^k 的细致分析），但陈述与检验是本章的必修。

第四章 原根与指标4.9 原根的个数：φ(p−1) 的礼物

4.7 的计数证明顺手送出一份大礼：ψ(d) = φ(d) 对一切 d | p−1 成立。取 d = p − 1：

p = 13：φ(12) = 4 → 原根 4 个 {2, 6, 7, 11}（例 7 逐一验证）。p = 7：φ(6) = 2 → {3, 5}（例 3）。p = 11：φ(10) = 4 → {2, 6, 7, 8}。而且 4.7 的等式 ψ(d) = φ(d) 给出全表：

三行完美咬合：每个阶的「理论名额」φ(d) 与「实测名单」分毫不差。一张表同时验证了 4.7 的计数定理、4.5 的子群唯一性（阶 d 的元素凑成唯一的 d 阶子群）与第三章的解数统计——三个定理在同一条表上握手。

第四章 原根与指标4.10 指标：离散对数的古典名字

原根一到位，整套「以 g 为尺」的坐标系统就可以挂牌营业。设 g 是模 p 的原根，则每个与 p 互素的 a 都有唯一写法 a ≡ g^k (mod p)（1 ≤ k ≤ p − 1）：

指标就是离散对数：普通对数 log₂ 8 = 3 解的是「2 的几次方是 8」，指标 ind(8) 解的是「g 的几次方 ≡ 8 (mod p)」。区别只在幂运算发生在模 p 的折返世界里。Gauss 在《算术研究》中系统地使用指标表（Index-Tafel）做计算——那是 1801 年的「对数表」在有限世界的孪生兄弟。

第四章 原根与指标4.11 指标算术：把乘法变加法

指标的威力来自它把乘法群「同构搬运」到加法世界。设 g 为原根，a ≡ g^u, b ≡ g^v (mod p)，则

注意模数换了：指标运算在模 p − 1 下进行（指数世界以 p − 1 为周期——Fermat 的又一面孔）。同理 ind(a^k) ≡ k·ind(a) (mod p − 1)。乘法、幂、求逆，全部化作模 p−1 的加法、数乘与取负：

最后一行是全场高潮：第三章苦心经营的线性同余方程理论（判据 g | b、解数 = g）在指数世界里精确接管了幂方程——第三章与第四章在此咬合成一台完整的机器。以 p = 13, g = 2 对账三笔：

第四章 原根与指标4.12 指标表：Gauss 的求根工具箱

指标算术的用途，是把「解幂方程」变成「解线性方程」。工具箱的中央就是指标表。p = 7, g = 3 的完整表（例 8 将详细用法）：

使用示范：解 3^x ≡ 4 (mod 7)。查表 ind(4) = 4，方程即 3x ≡ 4 (mod 6)？——不，底数若恰是原根 g 本身，x 就是 ind(4) = 4。验：3⁴ = 81 = 11·7 + 4 ✓。再示范「两数相乘的指标」：ind(2·5) = ind(10) = ind(3) = 1（10 ≡ 3），而 ind 2 + ind 5 = 2 + 5 = 7 ≡ 1 (mod 6) ✓。

指标表的构造是一次原根的幂巡游：算 3¹, 3², …, 3⁶ 逐个登记。表中值序 {0, 2, 1, 4, 5, 3} 杂乱无章——这份杂乱正是安全性的源泉（4.16）与「查账要细心」的原因（4.11）。

第四章 原根与指标4.13 二项同余方程：xⁿ≡a(p) 的指标判据

现在是收割时刻。解二项同余方程 xⁿ ≡ a (mod p)（p ∤ a）：两边取指标，

这是关于未知指标 y = ind(x) 的线性同余方程！第三章定理整装上阵：记 G = gcd(n, p − 1)，方程有解 ⟺ G | ind(a)；有解时恰 G 个，且给出 x 的 G 个互异解。翻译回乘法世界：

这一举解释了第三章「对账表」的全部谜团：x³ ≡ 2 (13) 无解，因为 G = gcd(3, 12) = 3 而 ind(2) = 1，3 ∤ 1；x³ ≡ 8 (13) 恰三解，因为 8 = 2³，ind(8) = 3·ind(2) = 3，3 | 3。当时只能「枚举验证」的现象，如今一行指标账算尽。

第四章 原根与指标4.14 高次同余方程：n 次幂的可解性全景

把 4.13 的判据展开成全景。p 素数，考虑「n 次幂映射」σ_n : x ↦ xⁿ 在 F_p^× 上的行为（以原根为坐标，它就是 y ↦ n·y 的乘法映射，模 p − 1）：

特殊情形一枚：n 整除 p − 1 时，G = n，像点 (p−1)/n 个、每个 n 层——第三章 3.16 那张 p = 13 的柱状图（金色顶格、暗色一根）由此获得完整解释：d | 12 时恰 d 根，d ∤ 12 时「像点」只有 1 个（x = 1）。再一枚：n = 2 时 G = 2，像点 = 平方像点 = 二次剩余，恰 (p−1)/2 个——第五章的主角提前在指标世界领到了身份证。

第四章 原根与指标4.15 有限域的乘法结构：F_p 的完整解剖

三章半的努力，可以给 F_p 出具一份「完整体检报告」了：

这张表的价值在于自足：F_p 的全部乘法行为，都能从「一个原根 + 模 p−1 的算术」推演。第五章将在这个自足体系上再叠一块砖——「平方」这一特殊幂映射（σ₂）的像点分布规律，最终凝成二次互反律。届时可以发现：互反律的 Gauss 计数证明，正是本章陪集分拆与第三章根计数的再度合体。

第四章 原根与指标4.16 离散对数问题：乘起来容易，拆开很难

指标表的最后一行其实写着警告。构造指标表需要逐个计算 g¹, g², g³, …——正向幂运算便宜（快速幂，第二章，O(log k) 步）。但反方向「给 a 求 k」——离散对数问题（DLP）——至今没有已知的高效算法。

难在哪里？实数世界 log 有单调性可用（夹逼、牛顿迭代），模 p 世界 g^k 的值序彻底打乱（4.10 图）——折返毁灭了所有连续性工具。暴力枚举要 O(p) 步；聪明些的「大步小步」算法（BSGS，例 11）要 O(√p) 步与 √p 存储——√(2¹²⁸) 级别的代价，工程上等于不可行。这条「单向性」（易正向、难逆向）正是公钥密码学的引擎。

第四章 原根与指标4.17 现代接口：Diffie–Hellman 密钥交换与 ElGamal〔密码〕

1976 年，Diffie 与 Hellman 发表《密码学的新方向》：两个从未见过面的人，可以在窃听者眼皮底下商定共同密钥。其数论心脏正是本章的幂映射：

第四章 原根与指标4.18 本章总结与方法表

本章从「谁的幂走遍全群」的疑问出发，抵达了「乘法宇宙有一条主轴」的定理，并把轴上的坐标（指标）变成了工具箱。总结如下：