L02a 取模与同余:把整条数轴绕成一个表盘
从带余除法讲起,一步步看清 mod 怎么算、负数怎么取模、同余是什么意思,以及为什么加减乘可以先取模再算。
一句话版
a mod n 就是 a 除以 n 剩下的余数,这个余数永远落在 0 到 n−1 之间。两个数余数相同,就说它们模 n 同余。做加、减、乘的时候,可以先把每个数换成余数再算,结果的余数不变。
这一页是第 2 讲数论的第一块砖。后面的最大公因数、模逆、欧拉定理、中国剩余定理,全都建立在这里的余数记法上。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| b | a | 读「b 整除 a」 | a 能被 b 除尽,没有余数 |
| 商 q、余数 r | quotient、remainder | a 里装得下几个 n,装完还剩多少 |
| ⌊x⌋ | 向下取整,floor | 不超过 x 的最大整数,⌊−1.5⌋ = −2 |
| a mod n | 读「a 模 n」 | a 除以 n 的余数,落在 0 到 n−1 |
| 模数 n | modulus | 表盘上一共有几格 |
| a ≡ b (mod n) | 读「a 与 b 模 n 同余」 | a 和 b 落在表盘的同一格 |
一个类比:钟表上的小时
墙上的钟只有 12 个刻度。现在 9 点,再过 5 小时是几点?不会是 14 点,指针转过 12 又从头来,停在 2 点。
模运算就是这个钟。整数轴本来是一条无限长的直线,把它按长度 n 一圈一圈绕起来,就成了一个只有 n 格的表盘。a mod n 是 a 落在第几格。两个数落在同一格,就叫同余。
钟上算「再过几小时」,你从来不需要先算出总小时数。直接拿现在的格子往前拨就行。这正是模运算最有用的地方:先取模再算,结果一样。
类比在哪里失效:
- 钟面写的是 1 到 12。模 12 的表盘写的是 0 到 11,12 点在模运算里记作 0。
- 钟只能往前拨。整数可以是负数,负数在表盘上是倒着拨,第 2 个概念专门讲它。
- 钟上没有乘法。模运算里乘法也能先取模,除法却不能,第 4 个概念会讲为什么。
从零讲起
1. 整除和带余除法
它解决什么问题
小学就会的除法,到了密码学里要用符号精确写下来。后面每一个算法都要反复拿「a 等于几个 n 再加一个余数」这条式子做变形。先把它写成一条不会有歧义的等式。
直觉
一根长 a 的绳子,拿长 n 的尺子去量。量了 q 整段,最后剩下一截不够一整段,这一截就是余数 r。剩下的那截一定比尺子短,也可能刚好是 0。
如果最后一截正好是 0,说明尺子能把绳子量尽,这时候就说 n 整除 a。
一步一步看
目标:在数轴上找 70 落在 15 的哪两个刻度之间,看出商和余数怎么读出来、余数为何必小于 15。
拿 70 除以 15 来看。
-
在数轴上每隔 15 打一个刻度:0、15、30、45、60、75。
-
找到 70 落在哪两个刻度之间:在 60 和 75 之间。
-
下面那个刻度是 60 = 4 × 15,所以商 q = 4。
-
70 比 60 多出 10,所以余数 r = 10。写成一条式子:70 = 4 × 15 + 10。
-
余数为什么一定小于 15?因为 70 一旦比 60 多出 15,就到了下一个刻度 75,商要变成 5。
怎么算
整除的定义:
b | a ⟺ 存在整数 m,使 a = m × b (要求 b ≠ 0)
意思是:a 能写成 b 的整数倍,就说 b 整除 a。m 可以是负数,也可以是 0。
带余除法(课件叫 Division Algorithm):
a = q × n + r, 0 ≤ r < n, q = ⌊a / n⌋
意思是:任何整数 a 除以正整数 n,都能拆成「q 个 n」加「一个比 n 小的非负余数 r」。商 q 就是 a/n 向下取整。
记号方向要看清。b | a 是竖线,竖线左边是除数。分数 a/b 的除数写在右边,两者顺序相反。
常见误解
以为整除只对正整数讲
定义里唯一的限制是除数 b 不能为 0。被除数可以是 0,也可以是负数。所以 17 | 0 成立,因为 0 = 0 × 17;−5 | 30 也成立,因为 30 = (−6) × (−5)。反过来 0 | 17 没有定义。
把 b | a 和 b / a 当成一回事
b | a 是一句话,结论只有成立或不成立。b / a 是一个数,是除法的结果。3 | 12 成立;3 / 12 是一个小于 1 的分数,是另一件事。
试一下
把 100 除以 7 写成 a = q × n + r 的形式。q 和 r 各是多少?
7 × 14 = 98,7 × 15 = 105 超过了 100。所以 q = 14,r = 2,写成 100 = 14 × 7 + 2。
判断:6 | 0 成立吗?0 | 6 成立吗?
6 | 0 成立,0 = 0 × 6。0 | 6 没有定义,除数不能是 0。
2. mod:把余数单独拿出来
它解决什么问题
带余除法一次给出两个数,q 和 r。很多时候只关心余数,比如钟上是几点只看余数,不看转了几圈。mod 运算就是把余数单独拿出来起个名字。
直觉
a mod n 回答一个问题:a 在 n 格的表盘上落在第几格。
正数好办,除一下看余数。负数要小心。负数在数轴上是往左走的,往左走也要找「下面那个刻度」,而负数的「下面」是更负的那一边。
一步一步看
目标:在数轴上给 −11 找 7 的倍数刻度,看出负数取模为什么商取 −2、余数是 3 而不是 −4。
拿 −11 mod 7 来看。
-
在数轴上标出 7 的倍数:−21、−14、−7、0、7。
-
找 −11 落在哪两个刻度之间:在 −14 和 −7 之间。
-
下面那个刻度是 −14 = (−2) × 7,所以商取 −2。
-
从 −14 往右量到 −11,距离是 3,所以余数是 3:−11 = (−2) × 7 + 3。
-
如果商取 −1,会得到 −11 = (−1) × 7 + (−4)。余数 −4 不在 0 到 6 之间,不符合定义。
怎么算
a mod n = a − ⌊a / n⌋ × n
意思是:先算 a 里向下数能装几个 n,再从 a 里减掉这么多个 n,剩下的就是余数。
负数取模的实用办法:先按正数算出余数,再用 n 减掉它。−11 mod 7:先算 11 mod 7 = 4,再算 7 − 4 = 3。如果正数余数是 0,负数余数也是 0。
写程序时要注意。C、Java、JavaScript 的 % 对负数返回负的余数,-11 % 7 得 −4。Python 的 % 和数学定义一致,得 3。其他语言里要得到数学上的余数,写成 ((x % n) + n) % n。
常见误解
以为负数取模就是在正数结果前面加个负号
−11 mod 7 = 3,11 mod 7 = 4,两个结果没有简单的正负关系。余数必须落在 0 到 n−1 之间,−4 不在这个范围里,所以还要再加 7 折回来。
以为商总是向 0 取整
数学定义里商是向下取整。−11/7 在 −2 和 −1 之间,向下取整是 −2。向 0 取整会得到 −1,那是 C、Java 的做法,余数会变成负的。
试一下
算 −20 mod 6 和 −18 mod 6。
20 mod 6 = 2,所以 −20 mod 6 = 6 − 2 = 4。验证:−20 = (−4) × 6 + 4。
18 mod 6 = 0,所以 −18 mod 6 = 0。验证:−18 = (−3) × 6 + 0。
JavaScript 里 -20 % 6 返回多少?怎么改成数学上的余数?
返回 −2。改成 ((-20 % 6) + 6) % 6,先得 −2,加 6 得 4,再模 6 还是 4。
3. 同余:落在表盘同一格
它解决什么问题
我们经常想说「这两个数在模 n 下没区别」,不关心它们具体是多少。比如 21 和 1,在模 10 的表盘上落在同一格。同余就是这句话的正式写法。
直觉
把模 10 的表盘画出来,0 到 9 十格。1、11、21、31 除以 10 都余 1,全部落在 1 那一格。它们彼此之间相差 10 的倍数,绕了几整圈又回到原处。
所以同余有两种等价的说法:余数相同;或者差是 n 的倍数。
一步一步看
目标:把 1、11、21、31 放上模 10 的表盘,看出落在同一格的数两两之差都是 10 的倍数。
-
画一个模 10 的表盘,格子是 0 到 9。
-
1 = 0 × 10 + 1,落在 1 格。
-
11 = 1 × 10 + 1,绕一圈后也落在 1 格。
-
21 = 2 × 10 + 1,31 = 3 × 10 + 1,同样落在 1 格。
-
任挑两个,比如 31 和 11,差是 20 = 2 × 10,正好是 10 的倍数。
怎么判断
a ≡ b (mod n) ⟺ a mod n = b mod n ⟺ n | (a − b)
意思是:判断两个数是否模 n 同余,可以比余数,也可以看两数之差能不能被 n 整除,两种方法结论一样。
课件从定义里推出两条结论:
- 若 a ≡ 0 (mod n),则 n | a。余数为 0,就是能被整除,整除和同余从这里开始可以互相翻译。
- 消去律:若 gcd(u, z) = 1 且 u·x ≡ u·y (mod z),则 x ≡ y (mod z)。两边约掉 u 之前,必须先确认 u 和模数 z 互素。gcd 的意思下一页讲。
注意 ≡ 后面的 (mod n) 是整句话的一部分。光写 21 ≡ 1 没有意义,要说清是在模几下。
常见误解
以为两边都乘了同一个数,就能随便约掉
反例:4 × 2 = 8 ≡ 2,4 × 5 = 20 ≡ 2,所以 4 × 2 ≡ 4 × 5 (mod 6)。可是 2 和 5 模 6 并不同余。原因是 4 和 6 有公因数 2,不满足消去律的前提。
以为 a ≡ b (mod n) 要求 b 小于 n
不要求。21 ≡ 11 (mod 10) 完全正确。只是做题时习惯把右边化成 0 到 n−1 里的那个代表,比如写 21 ≡ 1 (mod 10)。
试一下
判断 38 ≡ 14 (mod 6) 是否成立,用两种方法各验一次。
比余数:38 = 6 × 6 + 2,14 = 2 × 6 + 2,余数都是 2,成立。
看差:38 − 14 = 24 = 4 × 6,是 6 的倍数,成立。
−3 和 4 模 7 同余吗?
同余。−3 mod 7 = 4,4 mod 7 = 4。或者看差:4 − (−3) = 7,正好是 7 的倍数。
4. 模运算的三条性质
它解决什么问题
密码学里要算的数非常大,比如一个数的几十次方再取模。先把大数完整算出来再取模,中间结果会长到几十位。三条性质保证:加、减、乘每一步都可以先取模,数字永远停在 0 到 n−1 之间。
直觉
回到钟表。现在 9 点,过 5 小时是几点?你会直接拿 9 加 5 再减 12,不会去算从开天辟地到现在过了多少小时。
加法如此,减法、乘法也是一样:只看格子,不看圈数。每个数换成它所在的格子,再做运算,最后落在同一格。
一步一步看
目标:把 (211 × 125) mod 8 分先乘后模、先模后乘两条路算,看出两条路都得 7,后一条只碰小数。
用课件的数来走一遍:算 (211 × 125) mod 8。
-
上路:先乘。211 × 125 = 26375,是个五位数。
-
再对 8 取模:26375 = 3296 × 8 + 7,余 7。
-
下路:先各自取模。211 = 26 × 8 + 3,余 3;125 = 15 × 8 + 5,余 5。
-
再乘:3 × 5 = 15,15 mod 8 = 7。
-
两条路都得 7。下路从头到尾没碰过超过 15 的数。
怎么算
[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) − (b mod n)] mod n = (a − b) mod n
[(a mod n) × (b mod n)] mod n = (a × b) mod n
意思是:做加、减、乘时,可以先把每个数换成它的余数,算完再取一次模,结果和直接算大数再取模完全一样。
为什么成立,拿加法看一眼就够。设 a = q₁n + r₁,b = q₂n + r₂。两式相加得 a + b = (q₁ + q₂)n + (r₁ + r₂)。前面那一项是 n 的倍数,取模时整个消失,只剩 r₁ + r₂ 决定余数。乘法展开后,除了 r₁r₂ 以外每一项都带因子 n,道理相同。
减法有一个细节:先取模再相减,结果可能是负数。(3 − 5) = −2,还要再折回 0 到 7,得 6。
三条里没有除法。模意义下的「除以 b」要改写成「乘以 b 的模逆」,而模逆不一定存在,L02c 专门讲。
常见误解
以为除法也可以先取模
反例:(12 / 4) mod 8 = 3。先取模的话,12 mod 8 = 4,4 mod 8 = 4,4 / 4 = 1,结果对不上。模运算里没有直接的除法。
减法算出负数就直接交卷
(211 − 125) mod 8 的答案是 6。先取模得 3 − 5 = −2,这一步还没完,余数必须在 0 到 7 之间,−2 + 8 = 6。
试一下
不算出乘积,求 (98 × 97) mod 10。
98 mod 10 = 8,97 mod 10 = 7,8 × 7 = 56,56 mod 10 = 6。直接算 98 × 97 = 9506,末位也是 6。
求 (17 − 40) mod 9。
17 mod 9 = 8,40 mod 9 = 4,8 − 4 = 4。直接算 17 − 40 = −23,−23 = (−3) × 9 + 4,也是 4。
把它们串起来
四个概念是一条链。带余除法给出 a = qn + r;mod 把其中的 r 单独拿出来;同余说的是两个数的 r 相同;三条性质说的是加减乘可以只拿 r 来算。
这条链有两处会在后面反复出现。
第一处是「负数要折回去」。扩展欧几里得算法求模逆时,经常先算出一个负数,最后一步必须折回 0 到 n−1。
第二处是「没有除法」。想在模运算里做除法,就得找一个数,乘上去的效果等于除。这个数叫模逆。模逆存不存在,取决于两个数有没有公因数,所以下一页先讲最大公因数和欧几里得算法。
课件里的坑
- [口径差异] 课件 p.4 把除法算法的条件写成「n 为正整数、a 为非负整数」→ a 取负数时结论照样成立,只要坚持 0 ≤ r < n;p.15 的 −11 mod 7 马上就要用到这一点(p.4)
- [课件有误] 课件 p.15 的 ⌊a/n⌋ 在导出时乱码成了别的字形 → 就是向下取整(p.15)
- [适用条件] p.16 的消去律带着 gcd(u, z) = 1 的前提,丢了前提就会出错:4 × 2 ≡ 4 × 5 (mod 6),但 2 与 5 模 6 不同余(p.16)
- [容易漏看] p.17 的三条性质只有加、减、乘,没有除法。这是故意的,模意义下的除法要等 p.22 的模逆(p.17)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写带余除法的三个条件和模运算三条性质;再把课件例题自己算一遍;最后做变式题,回查最容易错的地方,负数有没有折回去。
必背
- 除法算法 a = qn + r,0 ≤ r < n,q = ⌊a/n⌋ 是全讲地基;负数取模要折回 [0, n):−11 mod 7 = 3 而不是 −4。
- b | a 只要求除数 b 非零:−5 | 30、17 | 0 都成立,0 | 17 没有定义。
- a ≡ b (mod n) 的定义是 a mod n 与 b mod n 相等;a ≡ 0 (mod n) 就是 n | a。
- 模运算三性质里只有加、减、乘能先取模,没有除法;模意义下的除法必须改写成乘以模逆。
- 减法先取模后可能落到负数,(3 − 5) mod 8 还要再折回 [0, 8) 得 6。
课件例题
例 1(课件 p.3):整除的三处填空
题面:(a) 写出 24 的全部正因子。(b) −5 | 30 成立吗?(c) 17 | 0 成立吗?
提示
整除的定义里,只有除数不能为 0。商 m 可以取负数,也可以取 0。
解答
(a) 1, 2, 3, 4, 6, 8, 12, 24,共 8 个。
(b) 成立。30 = (−6) × (−5),定义里 m 和 b 都允许取负数。
(c) 成立。0 = 0 × 17,任何非零整数都整除 0。反过来 0 | 17 没有定义,因为除数不能是 0。
例 2(课件 p.15):正数和负数取模
题面:求 11 mod 7 和 −11 mod 7。
提示
余数必须落在 0 到 6 之间。负数的商要向下取整。
解答
11 = 1 × 7 + 4,所以 11 mod 7 = 4。
−11 要满足 0 ≤ r < 7,商只能取 ⌊−11/7⌋ = −2,于是 −11 = (−2) × 7 + 3,−11 mod 7 = 3。取商 −1 会得到余数 −4,不在 [0, 7) 里。C、Java、JavaScript 的 % 返回的正是 −4,和数学定义不一致。
例 3(课件 p.16):同余填空
题面:73 ≡ ? (mod 23),21 ≡ ? (mod 10),填 0 到模数减 1 之间的数。
提示
就是求 73 mod 23 和 21 mod 10。
解答
73 = 3 × 23 + 4,所以 73 ≡ 4 (mod 23)。21 = 2 × 10 + 1,所以 21 ≡ 1 (mod 10)。
例 4(课件 p.17):先取模再运算
题面:求 211 mod 8、125 mod 8,再用模运算三条性质求 (211 + 125)、(211 − 125)、(211 × 125) 各自 mod 8。
提示
先把 211 和 125 换成余数,再做加减乘。减法的结果记得检查是不是负数。
解答
211 = 26 × 8 + 3,得 3;125 = 15 × 8 + 5,得 5。
加:(3 + 5) mod 8 = 0,直接算 336 = 42 × 8 也是 0。
减:(3 − 5) mod 8 = (−2) mod 8 = 6,直接算 86 = 10 × 8 + 6。−2 一定要再折回 [0, 8)。
乘:(3 × 5) mod 8 = 15 mod 8 = 7,直接算 26375 = 3296 × 8 + 7。
完整例题
考试里这一块的考法是「给一个算式,要求用模运算性质化简」,而且常常故意放一个减法让结果变负。
题面:不用计算器,求 (321 − 987 × 654) mod 9。
解法:
- 三个数分别取模:987 = 109 × 9 + 6,得 6;654 = 72 × 9 + 6,得 6;321 = 35 × 9 + 6,得 6。
- 先算乘法:6 × 6 = 36,36 mod 9 = 0。
- 再算减法:6 − 0 = 6,已经在 0 到 8 之间,不用折。
- 答案:(321 − 987 × 654) mod 9 = 6。
- 验算:987 × 654 = 645498,321 − 645498 = −645177。645177 = 71686 × 9 + 3,所以 −645177 ≡ −3 ≡ 6 (mod 9),一致。
答题格式:写出每个数取模的那一行带余除法;写明用的是乘法性质和减法性质;最后一行确认结果落在 0 到 n−1 之间。
变式题(先自己做)
改编自课件 p.17:不算出完整乘积,求 (−47 + 125 × 211) mod 8。
提示
−47 单独取模时,商要向下取整,余数要在 0 到 7 之间。
判分点与答案(非官方评分标准)
判分点:① 三个数各自取模正确;② −47 折回非负余数;③ 最后一步再取一次模。
125 mod 8 = 5,211 mod 8 = 3,乘积 5 × 3 = 15 ≡ 7。
−47:⌊−47/8⌋ = −6,−47 = (−6) × 8 + 1,所以 −47 mod 8 = 1。
相加:1 + 7 = 8 ≡ 0 (mod 8)。验算:125 × 211 = 26375,26375 − 47 = 26328 = 3291 × 8,确实整除。
闪卡自测
1. b | a 的定义里对 a 和 b 各有什么限制?
只要求除数 b 非零。被除数 a 可以是 0,也可以是负数,所以 −5 | 30、17 | 0 都成立(p.3)。
2. −11 mod 7 等于多少?为什么商取 −2?
等于 3。要满足 0 ≤ r < 7 只能取 q = ⌊−11/7⌋ = −2,于是 −11 = (−2) × 7 + 3。C/Java/JavaScript 的 % 对负数返回 −4,与数学定义不一致,Python 的才一致(p.15)。
3. 判断 a ≡ b (mod n) 有哪两种等价方法?
比余数,a mod n 是否等于 b mod n;或者看差,n 能否整除 a − b(p.16)。
4. 消去律 u·x ≡ u·y ⇒ x ≡ y (mod z) 的前提是什么?举一个反例。
前提是 gcd(u, z) = 1。反例:4 × 2 ≡ 4 × 5 (mod 6),但 2 与 5 模 6 不同余,因为 gcd(4, 6) = 2(p.16)。
5. 模运算的三条性质是什么?为什么其中没有除法?
加、减、乘三种运算都满足「先取模再算 = 先算再取模」。除法不在其中,因为模意义下的除法要改写成乘模逆,而模逆未必存在(p.17、p.22)。
6. (211 − 125) mod 8 先取模得到 −2,答案写几?
写 6。−2 不在 0 到 7 之间,要加 8 折回来(p.17)。
下一讲
下一页 L02b:最大公因数与欧几里得算法 讲怎么快速求两个数的最大公因数。它要反复用这一页的带余除法,每一步都是「被除数 = 商 × 除数 + 余数」。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。