第2卷 第7章 以发型为模

学习目标

• 能用带余除法和差可被模数整除的条件定义同余，并判断时钟标签与数学余数的区别
• 能安全执行同余式的加减乘幂运算，识别消去因子与模数互质及模数缩小的条件
• 能通过乘法表判断模逆元，区分既约剩余类群、剩余类环、零因子和有限域
• 能用实验与反例解释为什么素数模升级为域，而合数模仍只是含幺交换环

从时钟与余数开始

第2卷第7章从三次发型变化旁的一只时钟切入：尤里的马尾辫换了丝带，泰朵拉修短了头发，米尔嘉拄着拐杖回到教室。日常外观会改变，而时针只保留“除以12之后落在哪一格”。这正是本章的数学动作：有意识地忽略整圈差异，只保留余数。

先预测：15点为何和3点落在同一格；12点的余数到底是12还是0；等式中能同时除以2，为何同余式中有时不能；乘法表的一行出现重复意味着什么；同一个剩余类集合何时只是环，何时会升级成域？三组实验会把这些问题串成一条链。

对自然数a,b，带余除法不是用含糊的“除完剩下多少”定义，而是要求存在商q和余数r：

$$a=bq+r,\qquad 0\le r\lt b.$$

其中a是被除数，b是除数，q是商，r是余数。范围0\le r\lt b不可省略。若允许r任意大，7=3\cdot2+1也可写成7=3\cdot1+4，余数便不唯一；“余数小于除数”正是把还可以继续分出的整份全部拿走。

把范围扩到整数时，除数不能为0，并用绝对值处理负除数：

$$a=bq+r,\qquad b\ne0,\qquad 0\le r\lt |b|.$$

这叫带余除法。例如：

$$-7=3(-3)+2,$$

所以按本章采用的非负余数约定，-7除以3的余数是2。余数范围固定后，商和余数都是唯一的；若有两组表示，相减可得b(q-q')=r'-r，而右边绝对值小于|b|，只能两边都为0。

时针指示的是模12的余数类

求余运算记为mod：

$$a\bmod b=r.$$

例如：

$$7\bmod3=1,\qquad 15\bmod12=3,\qquad23\bmod12=11.$$

时针不记录已经绕过多少整圈，只记录当前位置。15点和3点相差12小时，因此显示相同；23点显示11。尤里抓住了一个关键条件：12除以12的余数不可能是12，因为余数必须小于12：

$$12=12\cdot1+0,\qquad12\bmod12=0.$$

钟面没有写0，而是把余数类0的位置标成12。也就是说，“显示标签”和“数学余数”不是同一件事。这个小小的不一致正好迫使我们从具体数字12走向“12与0在钟面世界里同等看待”。

同余是不拘小节地同等看待

给定正整数m，若整数a,b除以m得到相同余数，就说它们同余，写作：

$$a\equiv b\pmod m.$$

以下三个条件完全等价：

$$a\equiv b\pmod m \iff a\bmod m=b\bmod m \iff m\mid(a-b).$$

例如：

$$15\equiv3\pmod{12},\qquad 12\equiv0\pmod{12},\qquad -3\equiv2\pmod5.$$

“模m”中的m叫模数。同余不是普通等号：15当然不等于3，但若只关心相差多少个12，它们就属于同一类。原章所谓“不拘小节地同等看待”，就是忽略所有m的整数倍差异。

同余满足自反、对称与传递：

$$a\equiv a,\qquad a\equiv b\Rightarrow b\equiv a,\qquad a\equiv b,\ b\equiv c\Rightarrow a\equiv c \pmod m.$$

因此它是等价关系。与a同余的全部整数形成剩余类：

$$[a]_m=\{a+km\mid k\in\mathbb Z\}.$$

模5只有五个剩余类[0]_5,[1]_5,[2]_5,[3]_5,[4]_5。例如：

$$[2]_5=\{\ldots,-8,-3,2,7,12,\ldots\}.$$

无限多个整数并没有消失，而是按“相差5的整数倍”折叠进五个抽屉。这就是“同余把无限折叠成有限”。

等式与同余式的合法变形

若a=b，当然对任意正整数m都有a\equiv b\pmod m；反过来不成立，因为同余允许两边相差m的整数倍。必须始终带着模数阅读同余式。

若：

$$a\equiv b\pmod m,\qquad c\equiv d\pmod m,$$

则可以做加法、减法和乘法：

$$a+c\equiv b+d\pmod m,$$ $$a-c\equiv b-d\pmod m,$$ $$ac\equiv bd\pmod m.$$

证明只需把a-b=km、c-d=\ell m代入。例如：

$$ac-bd=c(a-b)+b(c-d)=m(ck+b\ell).$$

差仍是m的倍数，所以乘法保持同余。重复乘法还能得到：

$$a\equiv b\pmod m\Longrightarrow a^n\equiv b^n\pmod m.$$

这些规则允许先把大数换成较小代表元再计算。例如2026\equiv1\pmod5，所以2026^4\equiv1\pmod5，无需展开四次方。

两边同时做除法的条件

真正危险的是除法。下面的式子成立：

$$2\cdot1\equiv2\cdot4\pmod6,$$

因为2和8相差6。但若擅自消去2，就会得到错误结论：

$$1\not\equiv4\pmod6.$$

问题不在“同余不能除”，而在2在模6世界中没有乘法逆元。合法的消去定理是：

$$ac\equiv bc\pmod m,\qquad\gcd(c,m)=1 \Longrightarrow a\equiv b\pmod m.$$

由m\mid c(a-b)且\gcd(c,m)=1，欧几里得引理推出m\mid(a-b)。也可以先找c的模逆元 c^{-1}，在两边同乘它，从而消掉c。因此，除法的本质是寻找逆元。

若c与m不互质，也并非什么都不能推出。令g=\gcd(c,m)，一般消去律给出：

$$ac\equiv bc\pmod m \Longrightarrow a\equiv b\pmod{m/g}.$$

刚才的例子中g=\gcd(2,6)=2，因此正确结论是1\equiv4\pmod3，而不是模6同余。消去公因子时，模数也要一起缩小。

原章把数学工具比作拐杖。拐杖能帮助前进，却不能代替检查条件；同余式可以像等式一样做许多变形，但每一次“除”都必须确认被除数与模数互质，或明确模数将怎样变化。

除法的本质是寻找逆元

普通算术中“除以a”等于“乘以a^{-1}”。在模m世界里，解：

$$ax\equiv b\pmod m$$

也应先问是否存在u使：

$$au\equiv1\pmod m.$$

若存在，就有x\equiv ub\pmod m。贝祖定理给出完整判据：

$$a\text{ 在模 }m\text{ 下可逆} \iff \gcd(a,m)=1.$$

因为\gcd(a,m)=1等价于存在整数u,v使au+mv=1，取模m便得到au\equiv1。反过来，若au\equiv1，则au-1是m的倍数，a与m不可能有大于1的公因数。

用运算表研究可逆性

原章从“喝着可可”转入运算表研究，因为有限世界可以逐格检查。模5乘法表是：

\times	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

除0行外，每一行都是0,1,2,3,4的一个排列，因而每行恰好出现一次1：2^{-1}=3，3^{-1}=2，4^{-1}=4。

模6则不同：

\times	0	1	2	3	4	5
2	0	2	4	0	2	4
3	0	3	0	3	0	3

2行和3行反复碰到同样结果，且没有1。重复不是排版偶然，而是乘法映射x\mapsto ax发生碰撞。若\gcd(a,m)=1，ax\equiv ay可合法消去a，所以不同输入不会碰撞；有限集合上的单射必为满射，于是该行是全部剩余类的排列，也必出现1。反过来，行中出现1就已经给出逆元。

既约剩余类群

模m下可逆的剩余类叫既约剩余类；它们组成既约剩余类群：

$$U(m)=(\mathbb Z/m\mathbb Z)^\times =\{[a]_m\mid\gcd(a,m)=1\}.$$

关于模m乘法，U(m)闭合，结合律继承自整数乘法，单位元是[1]_m，每个元素按定义都有逆元，乘法可交换。因此确实是阿贝尔群。

例如：

$$U(8)=\{[1],[3],[5],[7]\}.$$

其中：

$$3^2\equiv5^2\equiv7^2\equiv1\pmod8,$$

所以每个非单位元都是自己的逆元。注意U(8)只保留可逆类；完整剩余类集合\mathbb Z/8\mathbb Z还包含0、2、4、6，它们不属于这个乘法群。

从群到环

群只有一种运算。若在同一集合上同时保留加法和乘法，并要求它们由分配律连接，就得到剩余类环。

本章采用的约定更具体：乘法还要求交换并有单位元1，也就是严格说的“含幺交换环”。公理可以整理为：

1. 关于加法构成阿贝尔群，单位元记作0。
2. 乘法闭合、结合、交换，并有单位元1。
3. 乘法对加法满足左右分配律。

不同教材对“环”是否必须含1、乘法是否必须交换有不同约定；本章的定义应连同约定一起读，不能只背名字。

整数\mathbb Z关于通常加法和乘法是环，却不是域，因为除\pm1外的大多数整数没有整数乘法逆元。完整剩余类集合：

$$\mathbb Z/m\mathbb Z=\{[0],[1],\ldots,[m-1]\}$$

关于模m加法与乘法也构成剩余类环。运算良定义正是依靠同余对加法和乘法的相容性：换掉代表元不会改变结果所在的剩余类。

从环到域

若一个含幺交换环中，除0外每个元素都有乘法逆元，就得到有限域。也就是说：

$$F\text{ 关于加法是阿贝尔群},\qquad F\setminus\{0\}\text{ 关于乘法是阿贝尔群}.$$

有理数\mathbb Q、实数\mathbb R、复数\mathbb C都是域，整数\mathbb Z不是域。

剩余类环何时成为域？答案恰好由素数决定：

$$\mathbb Z/m\mathbb Z\text{ 是域} \iff m\text{ 是素数}.$$

若p是素数，1,2,\ldots,p-1全与p互质，所以每个非零类都有逆元，得到：

$$\mathbb F_p=\mathbb Z/p\mathbb Z.$$

若m是合数，写成m=ab且1\lt a,b\lt m，则[a]和[b]都非零，却有：

$$[a][b]=[m]=[0].$$

这种非零元素乘积为0的元素叫零因子。零因子不可能有逆元；例如模6中[2][3]=[0]。因此\mathbb Z/6\mathbb Z是环而不是域。

以发型为模：选择保留什么

“以m为模”不是把整数说成真的相等，而是先声明当前问题只关心哪一种差异。以12为模，3点与15点相同；以5为模，2、7、12相同。换一个模数，分类也会改变。

标题中的发型把这种选择放回人物故事：丝带、长短、马尾、短发都是醒目的外观差异，数学中的模则明确规定哪些差异暂时忽略。这里不应把“忽略”误解为随意；同余类由精确条件m\mid(a-b)划定，既能不拘小节，又不会含混。

更重要的是，折叠并没有破坏加法与乘法。正因为同余关系与两种运算相容，无限整数才能安全地压缩成有限剩余类环；正因为素数模下非零类全可逆，环才能进一步成为有限域。后面讨论椭圆曲线在\mathbb F_p上的点时，本章的有限域正是必要语言。

官方概念回收：从钟面走到有限域

标题ヘアスタイルを法として与“以发型为模”都在提醒同一个选择：先声明哪些差异要忽略，再保留可以计算的结构。余数的定义是带余除法，并且要写清余数范围；只有这样才有商和余数的唯一性。把除数允许为负数就是整数的mod定义，仍以绝对值限制余数。

时钟提供时钟模12与模12的位置的可视模型；钟面12代表余数0，不是把余数写成12。一般地，同余既同余等价于余数相同，也同余等价于差可被模数整除；这里的模数决定抽屉数量。因为自反、对称、传递成立，同余是等价关系，每个抽屉就是一个剩余类，最终实现同余把无限折叠成有限。

做变形时要区分等式与同余式。同余式支持同余式的加减法、同余式的乘法和同余式的幂运算；但两边同时做除法的条件需要先验。消去因子与模数互质时可以保留模数，若不互质则一般消去律需要缩小模数。所以除法的本质是逆元，模逆元存在当且仅当模m可逆等价于与m互质。

运算表的研究把“可逆”变成可见的行：乘法行是排列等价于可逆。所有可逆类构成既约剩余类与既约剩余类群；群只有一种运算。把加法也保留，就得到环有加法和乘法两种运算。本章采用本章采用含幺交换环约定，整数环是整数环的例子，而 Z/mZ 是剩余类环。

最后一层是域：域的非零元素都有乘法逆元，所以可以安全做除法；有限域 Fₚ 满足模素数的剩余类环是域。相反，模合数出现零因子，模6中 [2][3]=[0] 就说明合数模只能停留在环，而不能升级为域。

本章回顾：把无限折叠成有限

1. 带余除法用a=bq+r和0\le r\lt|b|同时规定商、余数及其唯一代表。
2. 时针显示当前时刻模12的位置；钟面12代表余数类0，并不是余数12。
3. a\equiv b\pmod m等价于两数余数相同，也等价于m整除a-b。
4. 同余是等价关系，把无限整数分成m个剩余类；这就是把无限折叠成有限。
5. 同余式可以相加、相减、相乘和取非负整数次幂，因为这些运算保持“差是m的倍数”。
6. 同余式不能随意约分；只有消去因子与模数互质时，才能保持原模数。
7. 除法的本质是乘以模逆元；整数a模m可逆当且仅当\gcd(a,m)=1。
8. 乘法表的一行是全部剩余类的排列，当且仅当该行元素可逆。
9. 全部可逆类关于乘法构成既约剩余类群；完整剩余类集合关于加法和乘法构成剩余类环。
10. 当且仅当模数是素数时，剩余类环成为有限域\mathbb F_p；合数模会产生零因子。

Modular Inverse Lab

切换模数，观察同一个因子何时可逆、何时产生碰撞。

重置实验

模 5模 6

gcd(2,5) = 1

2⁻¹ = 3

2×3 ≡ 1 (mod 5)；乘法行是排列。

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 折叠：用时钟认识余数类

先写带余除法，再把 15 点与 3 点放到同一钟面，特别标出钟面 12 对应数学余数 0。

上一步播放下一步

练习与答案

练习

1. 问题 1：唯一余数。 说明为什么 7=3·2+1 是除以3的标准表示，而 7=3·1+4 不是合法的带余除法表示。

查看答案

带余除法要求 0≤r<|b|。在第一式中余数 1 满足 0≤1<3；第二式的余数 4 不小于3，还能继续分出一个3，所以不符合标准范围，也破坏唯一性。

2. 问题 2：合法约分。 判断从 2·1≡2·4 (mod 6) 得到 1≡4 (mod 6) 是否正确；若不正确，能得到什么模数下的结论？

查看答案

不正确，因为 gcd(2,6)=2，2 没有模6逆元。一般消去律只能把模数缩小为 6/2=3，所以正确结论是 1≡4 (mod 3)。

3. 问题 3：乘法表。 为什么模5中2有逆元，而模6中2没有？请用乘法行说明。

查看答案

模5的2行是 0,2,4,1,3，包含每个剩余类且出现1，因此 2⁻¹=3。模6的2行是 0,2,4,0,2,4，发生碰撞且没有1；这对应 gcd(2,6)=2，所以2不可逆。

4. 问题 4：环还是域。 解释为什么 Z/5Z 是有限域，而 Z/6Z 只是剩余类环。

查看答案

5是素数，1、2、3、4都与5互质，所有非零剩余类都有逆元，所以 Z/5Z 是域。6是合数，[2][3]=[0] 产生非零零因子，非零元素不全可逆，因此 Z/6Z 不是域。

名词解释

本章出现的专业名词，用大白话再讲一遍。

带余除法

把整数写成除数乘商加余数，并要求余数位于标准范围内的唯一表示。

同余

两个整数之差是模数倍数的关系；它把无限整数分成有限剩余类。

模逆元

与给定数相乘后模 m 等于1的剩余类，模意义下的除法靠它完成。

既约剩余类群

模 m 下全部与 m 互质的剩余类，关于乘法形成的群。

剩余类环

完整剩余类集合同时带有模加法和模乘法，并由分配律连接。

有限域

元素有限且每个非零元素都有乘法逆元的域；Fₚ 是素数模的典型例子。