← COMP5521 全部讲次
L02a · 第 2 周

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 来看。

  1. 在数轴上每隔 15 打一个刻度:0、15、30、45、60、75。

  2. 找到 70 落在哪两个刻度之间:在 60 和 75 之间。

  3. 下面那个刻度是 60 = 4 × 15,所以商 q = 4。

  4. 70 比 60 多出 10,所以余数 r = 10。写成一条式子:70 = 4 × 15 + 10。

    数轴上每隔 15 打一个刻度,依次标 0、1 × 15 到 5 × 15,下面写着 0、15、30、45、60、75。黑点 a = 70 落在 60 和 75 之间,从 60 到 70 这一段用青绿括号标成 r = 10

  5. 余数为什么一定小于 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 来看。

  1. 在数轴上标出 7 的倍数:−21、−14、−7、0、7。

  2. 找 −11 落在哪两个刻度之间:在 −14 和 −7 之间。

  3. 下面那个刻度是 −14 = (−2) × 7,所以商取 −2。

  4. 从 −14 往右量到 −11,距离是 3,所以余数是 3:−11 = (−2) × 7 + 3。

    数轴上标出 −21、−14、−11、−7、0、7。从下面那个刻度 −14 到 −11 用青绿括号标出加 3;从 −11 往右到 −7 的虚线标着 −4,注明不在 0 到 6 里,不算。底部写着 ⌊−11/7⌋ = −2,余数是 3

  5. 如果商取 −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 的倍数。

  1. 画一个模 10 的表盘,格子是 0 到 9。

  2. 1 = 0 × 10 + 1,落在 1 格。

  3. 11 = 1 × 10 + 1,绕一圈后也落在 1 格。

  4. 21 = 2 × 10 + 1,31 = 3 × 10 + 1,同样落在 1 格。

    一个刻 0 到 9 的表盘,1 那一格用青绿圈出。右边四行算式:1 = 0 × 10 + 1,11 = 1 × 10 + 1,21 = 2 × 10 + 1,31 = 3 × 10 + 1,余数都是 1,所以 21 ≡ 1 ≡ 11 (mod 10);同一格里任挑两个数,差都是 10 的倍数

  5. 任挑两个,比如 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。

  1. 上路:先乘。211 × 125 = 26375,是个五位数。

  2. 再对 8 取模:26375 = 3296 × 8 + 7,余 7。

  3. 下路:先各自取模。211 = 26 × 8 + 3,余 3;125 = 15 × 8 + 5,余 5。

  4. 再乘:3 × 5 = 15,15 mod 8 = 7。

    上下两条路算 (211 × 125) mod 8。上路先乘得到五位数 26375,再模 8;下路先把 211 变成 3、125 变成 5,相乘得 15 再模 8。两条路都落到青绿方框里的 7,下路每一步都是小数

  5. 两条路都得 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 分钟怎么用:合上页面,先默写带余除法的三个条件和模运算三条性质;再把课件例题自己算一遍;最后做变式题,回查最容易错的地方,负数有没有折回去。

必背

  1. 除法算法 a = qn + r,0 ≤ r < n,q = ⌊a/n⌋ 是全讲地基;负数取模要折回 [0, n):−11 mod 7 = 3 而不是 −4。
  2. b | a 只要求除数 b 非零:−5 | 30、17 | 0 都成立,0 | 17 没有定义。
  3. a ≡ b (mod n) 的定义是 a mod n 与 b mod n 相等;a ≡ 0 (mod n) 就是 n | a。
  4. 模运算三性质里只有加、减、乘能先取模,没有除法;模意义下的除法必须改写成乘以模逆。
  5. 减法先取模后可能落到负数,(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。

解法:

  1. 三个数分别取模:987 = 109 × 9 + 6,得 6;654 = 72 × 9 + 6,得 6;321 = 35 × 9 + 6,得 6。
  2. 先算乘法:6 × 6 = 36,36 mod 9 = 0。
  3. 再算减法:6 − 0 = 6,已经在 0 到 8 之间,不用折。
  4. 答案:(321 − 987 × 654) mod 9 = 6。
  5. 验算: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:最大公因数与欧几里得算法 讲怎么快速求两个数的最大公因数。它要反复用这一页的带余除法,每一步都是「被除数 = 商 × 除数 + 余数」。

下一讲 →
L02b L02b 最大公因数与欧几里得算法:拿短的去量长的

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。