← COMP5521 全部讲次
L02c · 第 2 周

L02c 模逆与扩展欧几里得:模运算里的除法

从「模运算里怎么做除法」讲起,看清模逆是什么、什么时候存在,再用 Bézout 恒等式和扩展欧几里得算法一行一行把它算出来。

一句话版

普通算术里「除以 5」等于「乘以 1/5」。模运算里没有分数,于是找一个整数 x,让 5 × x 模 n 等于 1,这个 x 就当作 1/5 来用,叫 5 的模逆。模逆只在两个数互素时存在;要把它算出来,就把上一页的欧几里得算法倒着走一遍。

这一页用到 L02a 的取模和 L02b 的欧几里得算法。RSA 的私钥就是用这一页的方法算出来的。

先认识这几个词

词 全称 / 读法 一句人话
a⁻¹ mod b 读「a 模 b 的逆」,modular inverse 和 a 相乘后模 b 得 1 的那个数
可逆 invertible 有模逆
Zₙ 读「Z n」 0 到 n−1 这 n 个数,加上模 n 的运算
Bézout 恒等式 Bézout’s identity,也译裴蜀恒等式 gcd 一定能写成两个数的整数倍相加
扩展欧几里得算法 Extended Euclidean Algorithm 求出 Bézout 等式里那两个系数的方法
回代 tracing backward 从最后一行往上,一行一行代入

一个类比:表盘上按固定步长跳

拿一个 8 格的表盘,从 0 出发,每次往前跳 3 格:0、3、6、1、4、7、2、5,再回到 0。八格全踩到了,其中踩到 1 的那一下是第 3 跳。3 跳 3 次到 1,所以 3 × 3 ≡ 1,3 的模逆就是 3。

换成每次跳 2 格:0、2、4、6、0、2……只在偶数格里打转,永远踩不到 1。2 在模 8 下没有模逆。

能不能踩到 1,看的是步长和表盘格数有没有公因数。3 和 8 没有,能踩遍;2 和 8 有公因数 2,只能踩到一半。

类比在哪里失效:

  • 跳格子只能告诉你逆元存不存在,表盘一大,一格一格跳就太慢了。真正求逆元要用第 4 个概念的扩展欧几里得算法。
  • 跳格子看起来只能往前走。模逆有时会先算出一个负数,要再折回 0 到 n−1 之间。

从零讲起

1. 模逆是什么

它解决什么问题

上一页讲过,模运算三条性质里没有除法。可是很多问题非要除不可,比如解 5t ≡ 1 (mod 7) 这样的方程。模逆让除法变成乘法:要除以 a,就乘 a 的模逆。

直觉

普通算术里,5 × (1/5) = 1。模运算里只有整数,那就问:哪个整数和 5 相乘,模 7 以后等于 1?试一下,5 × 3 = 15,15 mod 7 = 1。所以在模 7 的世界里,3 扮演了 1/5 的角色。

一步一步看

目标:在模 8 表盘上分别用步长 3 和 2 去跳,看出能踩到 1 的才有模逆。

在模 8 的表盘上,从 0 出发,按固定步长跳。

  1. 步长 3:依次落在 0、3、6、1、4、7、2、5,八格全部踩到。

  2. 踩到 1 是在第 3 跳,说明 3 × 3 = 9 ≡ 1 (mod 8)。3 的模逆是 3。

  3. 步长 2:依次落在 0、2、4、6,然后又回到 0。

  4. 只在偶数格里打转,永远踩不到 1,所以 2 没有模逆。

    两个刻了 0 到 7 的表盘。左边按步长 3 跳,依次落在 0、3、6、1、4、7、2、5 再回到 0,八格全部踩到并踩到过 1,所以 3 可逆且 3 × 3 = 9 ≡ 1;右边按步长 2 跳,只落在 0、2、4、6 四格,永远踩不到 1,所以 2 没有乘法逆元

怎么算

若 a · x mod b = 1,则称 x 是 a 模 b 的乘法逆元,记作 a⁻¹ mod b

意思是:a 乘上 x 以后,除以 b 余 1,那么 x 就是 a 在模 b 下的「倒数」。

验证一个数是不是模逆很容易,乘一下看余数:

  • 5 × 3 = 15 = 2 × 7 + 1,所以 5⁻¹ mod 7 = 3。
  • 7 × 7 = 49 = 3 × 16 + 1,所以 7⁻¹ mod 16 = 7,7 是自己的逆元。

按惯例,模逆取 0 到 b−1 之间的那个数。

常见误解

把 a⁻¹ mod b 当成 1/a 再取模

1/5 是分数,没法取模。a⁻¹ mod b 是一个整数,要按「乘起来余 1」去找。5⁻¹ mod 7 = 3,和 0.2 没有关系。

以为模逆和模数无关

同一个数在不同模数下逆元不同。5⁻¹ mod 7 = 3,但 5⁻¹ mod 8 = 5,因为 5 × 5 = 25 ≡ 1 (mod 8)。

试一下

求 3⁻¹ mod 7。

3 × 5 = 15 = 2 × 7 + 1,所以 3⁻¹ mod 7 = 5。

4 是 2 模 7 的逆元吗?

是。2 × 4 = 8 = 1 × 7 + 1。

2. 什么时候有模逆

它解决什么问题

上一节看到 2 在模 8 下没有逆元。在动手求逆元之前,要先能判断它存不存在,否则可能白算一场。

直觉

如果 a 和 b 有公因数 d > 1,那么 a 的任何倍数 a·x,减去 b 的任何倍数,结果都是 d 的倍数。1 不是 d 的倍数,所以 a·x 永远不可能模 b 余 1。

反过来,如果 a 和 b 互素,第 3 个概念会证明一定能凑出 1。

一步一步看

目标:逐行看模 8 乘法表里有没有 1,看出有模逆的恰好是与 8 互素的那几个数。

把模 8 的乘法表整张画出来,看每一行有没有 1。

  1. 第 0 行全是 0,没有 1。

  2. 第 1、3、5、7 行各有一个 1,而且都落在对角线上。

  3. 第 2、4、6 行整行没有 1。

    模 8 乘法表,行和列都是 0 到 7。第 1、3、5、7 行各有一个青绿方框圈出的 1,都在对角线上,旁边注明有 1 可逆;第 0、2、4、6 行灰底,注明整行没有 1。底部写着 1 只出现在与 8 互素的四行,各自是自己的逆元

  4. 有 1 的四行,正好是与 8 互素的 1、3、5、7;没有 1 的,正好是与 8 有公因数的 0、2、4、6。

怎么判断

a 模 b 的逆元存在  ⟺  gcd(a, b) = 1

意思是:a 和 b 互素时逆元一定存在,不互素时一定不存在。判断方法就是用上一页的欧几里得算法算 gcd。

这条判据两个方向都会考。给两个数问逆元存不存在,就算 gcd。题目告诉你「逆元存在」,你就立刻知道两个数互素。

比如 gcd(8, 14) = 2,所以 8 模 14 没有逆元。

模 8 的表里还有一个现象:2 × 4 = 8 ≡ 0。两个都不是 0 的数,乘起来得 0,这种数叫零因子。模数换成素数,零因子就消失了,除 0 以外每个数都可逆。这是密码学喜欢拿素数做模数的原因。

常见误解

以为只要 a 小于 b,模逆就存在

和大小无关,只看 gcd。6 小于 9,但 gcd(6, 9) = 3,6 模 9 没有逆元。

以为模数是合数就没有任何逆元

8 是合数,可模 8 下 1、3、5、7 都可逆。合数模数下,与模数互素的那些数照样有逆元。

试一下

模 10 下,哪些数有逆元?

与 10 互素的数:1、3、7、9。逆元分别是 1、7、3、9,比如 3 × 7 = 21 ≡ 1,9 × 9 = 81 ≡ 1。

15 模 25 有逆元吗?

没有。gcd(15, 25) = 5 ≠ 1。

3. Bézout 恒等式

它解决什么问题

知道逆元存在还不够,还要把它算出来。Bézout 恒等式把「求模逆」这个模运算问题,翻译成「解 ax + by = 1」这个整数方程。整数方程有现成的机械算法。

从哪来(补充)

这条恒等式以法国数学家 Étienne Bézout(1730–1783)命名。他在 1779 年证明的是多项式的版本。整数的版本更早,已经出现在 Bachet de Méziriac 的趣味数学书《Problèmes plaisants》1624 年的第 2 版里。

出处:Wikipedia: Bézout’s identity

直觉

拿 a 和 b 两种砝码,可以放在天平左边,也可以放在右边,相当于可以加也可以减。能称出哪些重量?

能称出来的,一定是 gcd(a, b) 的倍数,因为两种砝码都是它的倍数。Bézout 说的是另一半:gcd(a, b) 本身一定能称出来。

一步一步看

目标:对比 4 和 6、3 和 5 的整数组合能凑出哪些数,看出只有 gcd 为 1 时才凑得出 1。

  1. 用 4 和 6 加加减减:4x + 6y 能凑出 −2、0、2、4、6、8……

  2. 凑出来的全是偶数,因为 4 和 6 都是 2 的倍数。gcd(4, 6) = 2,凑不出 1。

  3. 换成 3 和 5:3x + 5y 能凑出 −3 到 8 之间的每一个整数。

  4. 其中 1 = 2 × 3 + (−1) × 5,说明 gcd(3, 5) = 1 能凑出来。

    两排数字格。上排 4x + 6y 只能凑出 −2、0、2、4、6、8 这些偶数,奇数格灰掉,注明 gcd(4, 6) = 2,凑不出 1。下排 3x + 5y 从 −3 到 8 每一格都能凑出,青绿框出的 1 = 2 × 3 + (−1) × 5

  5. 两两对照:gcd 为 2 时只能凑出偶数,gcd 为 1 时每个整数都能凑出。

怎么算

对任意整数 a、b,存在整数 x、y,使  a·x + b·y = gcd(a, b)

意思是:两个数的最大公因数,总能写成「a 的若干倍」加「b 的若干倍」,倍数可以是负数。

它和模逆的关系只差一步。gcd(a, b) = 1 时,等式是 a·x + b·y = 1。两边同时模 b,b·y 是 b 的倍数,整项变成 0,剩下 a·x ≡ 1 (mod b)。这个 x 就是 a 的模逆。

反方向也成立。如果 a·x ≡ 1 (mod b),就有 a·x − 1 = k·b。任何同时整除 a 和 b 的数都整除 1,所以 gcd = 1。这就证明了上一节的判据。

常见误解

以为 Bézout 系数 x、y 都是正数

几乎总有一个是负数。1 = 2 × 3 + (−1) × 5,里面就有 −1。两个都是正数的话,结果至少是 a + b,比 gcd 大。

以为求逆元时两个系数都要用

只用 a 前面的那个系数 x。b 的系数 y 乘的是 b 自己,模 b 以后整项消失。

试一下

找整数 x、y,使 5x + 7y = 1,然后读出 5⁻¹ mod 7。

5 × 3 + 7 × (−2) = 15 − 14 = 1,所以 x = 3,y = −2。两边模 7 得 5 × 3 ≡ 1,5⁻¹ mod 7 = 3。

6x + 9y 能凑出 1 吗?

不能。gcd(6, 9) = 3,能凑出来的都是 3 的倍数。

4. 扩展欧几里得算法

它解决什么问题

Bézout 只说 x、y 一定存在,没说怎么找。小数字可以凑,大数字凑不出来。扩展欧几里得算法给出一条固定的路线,再大的数也能一步步算出 x、y。

直觉

欧几里得算法的每一行都是「被除数 = 商 × 除数 + 余数」。把它移项,就得到「余数 = 被除数 − 商 × 除数」,每个余数都能用上面两个数表示出来。

最后一个非零余数是 gcd。从它出发,一行一行往上代,把式子里的余数逐个换成更上面的数,最后只剩下最初的 a 和 b。

一步一步看

目标:以 16⁻¹ mod 93 为例先正向辗转相除,再一行行回代,看出模逆怎样从等式里读出来。

求 16⁻¹ mod 93。

  1. 正向跑欧几里得算法:93 = 5 × 16 + 13;16 = 1 × 13 + 3;13 = 4 × 3 + 1。余数到 1,gcd = 1,逆元存在。

  2. 从最后一行开始,把 1 写成余数的形式:1 = 13 − 4 × 3。

  3. 式子里最晚出现的余数是 3。用第二行把它换掉:3 = 16 − 1 × 13,代入整理得 1 = 5 × 13 − 4 × 16。

  4. 现在最晚出现的余数是 13。用第一行把它换掉:13 = 93 − 5 × 16,代入整理得 1 = 5 × 93 − 29 × 16。

    左栏三行正向除法:93 = 5 × 16 + 13,16 = 1 × 13 + 3,13 = 4 × 3 + 1,箭头向下,注明余数到 1,gcd = 1,逆元存在。右栏三行回代自下而上:1 = 13 − 4 × 3,= 5 × 13 − 4 × 16,= 5 × 93 − 29 × 16,箭头向上。下方:两边模 93 得 1 ≡ (−29) × 16,−29 折回得 64,验算 16 × 64 = 1024 = 11 × 93 + 1

  5. 两边模 93,5 × 93 那一项消失:1 ≡ (−29) × 16 (mod 93)。

  6. −29 不在 0 到 92 之间,折回:93 − 29 = 64。所以 16⁻¹ mod 93 = 64。验算 16 × 64 = 1024 = 11 × 93 + 1。

课件的大例子 911⁻¹ mod 999 也是同一条路线,只是正向多了两行:

左半是去程五行除法:999 = 1 × 911 + 88,911 = 10 × 88 + 31,88 = 2 × 31 + 26,31 = 1 × 26 + 5,26 = 5 × 5 + 1,得 gcd 为 1。右半是回程五行回代,自下而上把最老的余数逐行换掉,最终 1 = (−193) × 911 + 176 × 999,两边模 999 后负系数折回正数得 911 的逆元 806

怎么算

三步路线:

① 正向:跑欧几里得算法,直到余数为 1(gcd ≠ 1 就停下,逆元不存在)
② 回代:1 = (最后一行移项),然后每次把式子里最老的余数用上一行换掉
③ 折正:得到 1 = x·a + y·b 后,a⁻¹ mod b = x mod b

意思是:先确认逆元存在,再从底往上把 1 改写成 a 和 b 的组合,最后把 a 前面的系数折回 0 到 b−1 之间。

「最老的余数」指的是式子里出现得最晚、在正向过程中排得最靠下的那个余数。每一步只换一个,换完合并同类项。

回代时最常见的错是丢掉减号。一个简单的自查办法:每合并完一行,把数字代进去算一下,结果必须仍然等于 1。哪一行不等于 1,错就出在哪一行。

常见误解

算出 x = −29 就直接写答案

模逆按惯例取 0 到 b−1 之间的数。−29 要加 93 折回 64。这一步最容易漏,考试会扣分。

回代时一次换掉两个余数

一次换两个,很容易把系数合错。每一步只换「最老的」那一个,换完合并,再换下一个。

试一下

用扩展欧几里得求 7⁻¹ mod 26。

正向:26 = 3 × 7 + 5;7 = 1 × 5 + 2;5 = 2 × 2 + 1。gcd = 1。

回代:1 = 5 − 2 × 2 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7 = 3 × (26 − 3 × 7) − 2 × 7 = 3 × 26 − 11 × 7。

所以 7⁻¹ ≡ −11 ≡ 15 (mod 26)。验算:7 × 15 = 105 = 4 × 26 + 1。

用扩展欧几里得求 11⁻¹ mod 30。

正向:30 = 2 × 11 + 8;11 = 1 × 8 + 3;8 = 2 × 3 + 2;3 = 1 × 2 + 1。

回代:1 = 3 − 2 = 3 − (8 − 2 × 3) = 3 × 3 − 8 = 3 × (11 − 8) − 8 = 3 × 11 − 4 × 8 = 3 × 11 − 4 × (30 − 2 × 11) = 11 × 11 − 4 × 30。

所以 11⁻¹ mod 30 = 11。验算:11 × 11 = 121 = 4 × 30 + 1。

把它们串起来

模逆是模运算里的除法;它存在当且仅当 gcd = 1;Bézout 恒等式说 gcd 总能写成 a·x + b·y,于是 gcd = 1 时 x 就是逆元;扩展欧几里得算法把上一页的除法倒着代回去,把 x 真正算出来。

一道求逆元的题,完整答案总是三段:先算 gcd 判存在,再回代求系数,最后折正并验算。

到这里,本讲的前两块零件齐了:欧几里得算法判互素,扩展欧几里得算法求逆元。下一页 L02d 讲第三块:素数、费马小定理和欧拉定理,它们负责把很大的指数降下来。

课件里的坑

  • [容易漏看] 课件 p.22 的存在性判据是双向的:给两个数问逆元存不存在,算 gcd;给出「逆元存在」,立刻得到两数互素(p.22)
  • [课件留白] 课件 p.23 只陈述了 Bézout 恒等式,没有证明,也没写它为什么能推出模逆判据。推导见本页第 3 个概念(p.23)
  • [容易漏看] 课件 p.25 最后一步把 −193 折回 806,这一步最容易漏,答题时要写 −193 ≡ 806 (mod 999) 并验算(p.25)
  • [容易漏看] 课件 p.19 乘法表里 2 × 4 = 0 这样的零因子,是 Z₈ 不能对每个非零数做除法的原因;模数是素数时零因子消失(p.19)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写模逆存在的充要条件和扩展欧几里得的三步路线;再把课件例题 p.24 和 p.26 各自独立算一遍;最后做变式题,回查最容易错的地方,算出负系数就交卷。

必背

  1. a⁻¹ mod b 是满足 a·x mod b = 1 的 x;5⁻¹ mod 7 = 3,7⁻¹ mod 16 = 7。
  2. 模逆存在 ⟺ gcd(a, b) = 1;Z₈ 里只有 1、3、5、7 可逆,且各自是自己的逆元。
  3. Bézout 恒等式 ax + by = gcd(a, b),整数 x、y 一定存在;gcd = 1 时两边模 b,x 就是 a 的逆元。
  4. 扩展欧几里得手算三步:正向跑除法 → 逐行回代 → 负系数折回正数。
  5. 回代时每次把最老的余数用上一行换掉,每合并一行都应仍等于 1;911⁻¹ mod 999 = 806。

课件例题

例 1(课件 p.22):三个模逆的判断

题面:求 5⁻¹ mod 7、7⁻¹ mod 16;判断 8 模 14 有没有逆元。

提示

小数字可以直接试乘。判断有没有逆元,先算 gcd。

解答

5 × 3 = 15 = 2 × 7 + 1,所以 5⁻¹ mod 7 = 3。

7 × 7 = 49 = 3 × 16 + 1,所以 7⁻¹ mod 16 = 7,7 是自己的逆元。

gcd(8, 14) = 2 ≠ 1,所以 8 模 14 没有逆元。

例 2(课件 p.24–25):用扩展欧几里得求 911⁻¹ mod 999

题面:先跑欧几里得算法确认 gcd(911, 999) = 1,再逐行回代写出 1 = x × 911 + y × 999,最后取出 911 模 999 的逆元。

提示

正向一共五行,第一行是 999 除以 911。回代从 1 = 26 − 5 × 5 开始。

解答

正向五行:999 = 1 × 911 + 88;911 = 10 × 88 + 31;88 = 2 × 31 + 26;31 = 1 × 26 + 5;26 = 5 × 5 + 1,gcd = 1,逆元存在。

回代,每次把最老的余数用上一行换掉:

1 = 26 − 5 × 5 = −5 × 31 + 6 × 26 = 6 × 88 − 17 × 31 = −17 × 911 + 176 × 88 = 176 × 999 − 193 × 911

两边模 999,176 × 999 那一项被模掉,得 1 ≡ −193 × 911 (mod 999)。负系数折回正数:−193 + 999 = 806。

验算:806 × 911 = 734266 = 735 × 999 + 1。

例 3(课件 p.26,Exercise-2):求 16⁻¹ mod 93

题面:用扩展欧几里得求 16 模 93 的逆元。上一页例 5 已算出两者互素。

提示

正向三行,回代三行,最后折正一次。

解答

正向:93 = 5 × 16 + 13;16 = 1 × 13 + 3;13 = 4 × 3 + 1。

回代:1 = 13 − 4 × 3 = 5 × 13 − 4 × 16 = 5 × 93 − 29 × 16。

所以 16⁻¹ ≡ −29 ≡ 93 − 29 = 64 (mod 93)。验算:16 × 64 = 1024 = 11 × 93 + 1。

例 4(课件 p.48,Exercise-8):27 模 392 的逆元存在吗,存在就求出来

题面:判断 27 模 392 的逆元是否存在;存在就求出来,不存在就说明理由。

提示

先跑欧几里得算法,第一行是 392 = 14 × 27 + 14。

解答

逆元存在,27⁻¹ mod 392 = 363。完整过程见下方完整例题。

完整例题

期末闭卷,这一块的考法是「给你两个数,当场跑一遍算法」。课件 Exercise-8 把判存在、求系数、折正三段都考到了。

题面:27 模 392 的逆元存在吗?存在就求出来,不存在就说明理由。

解法:

  1. 先按充要判据算 GCD,同时也是在为回代备料:392 = 14 × 27 + 14,27 = 1 × 14 + 13,14 = 1 × 13 + 1,13 = 13 × 1 + 0,得 gcd(27, 392) = 1,逆元存在。
  2. 逐行回代,每次把式子里最老的余数用上一行换掉:1 = 14 − 13 = 14 − (27 − 14) = 2 × 14 − 27 = 2 × (392 − 14 × 27) − 27 = 2 × 392 − 29 × 27。
  3. 于是 1 = (−29) × 27 + 2 × 392,取 27 那一侧的系数 −29。
  4. 负系数折回正数:−29 ≡ 392 − 29 = 363 (mod 392)。
  5. 验算:27 × 363 = 9801 = 25 × 392 + 1 ✓。

答题格式:判存在(算 GCD)→ 求系数(回代)→ 折正并验算,三段都写。题面故意问「或说明为什么不能」,考的就是那条充要判据;如果 gcd ≠ 1,正确答案是「不存在,因为两数不互素」,不用硬算。

变式题(先自己做)

改编自课件 p.48:求 17 模 120 的逆元,或说明为什么不存在。

提示

这道题的 GCD 一步就除完了,别因为除得太快而跳过「判存在」那句话。

判分点与答案(非官方评分标准)

判分点:判存在、回代求系数、折正并验算,三段缺一不可。

120 = 7 × 17 + 1,17 = 17 × 1 + 0,故 gcd(17, 120) = 1,逆元存在。回代只有一行:1 = 120 − 7 × 17,取 17 那一侧的系数 −7,折正得 120 − 7 = 113。验算 17 × 113 = 1921 = 16 × 120 + 1 ✓。

闪卡自测

1. 模逆存在的充要条件是什么?这条判据怎么用?

充要条件是 gcd(a, b) = 1。两个方向都会考:给两个数问逆元存不存在,就算 GCD;给出「逆元存在」,就立刻得到两数互素(p.22)。

2. 在 Z₈ 的乘法表里哪些元素有乘法逆元?为什么是这几个?

只有 1、3、5、7,而且各自是自己的逆元(3 × 3 = 9 ≡ 1,5 × 5 = 25 ≡ 1,7 × 7 = 49 ≡ 1)。它们恰好是与 8 互素的那些。2、4、6 所在的行整行没有 1,还出现 2 × 4 = 0 这样的零因子(p.19、p.20)。

3. 写出 Bézout 恒等式,并说明它和求模逆的关系。

ax + by = gcd(a, b),整数 x、y 一定存在。gcd = 1 时两边模 b 得 ax ≡ 1 (mod b),x 就是 a 的逆元。它把「求模逆」换成了「解整数方程」,工具是扩展欧几里得(p.23)。

4. 扩展欧几里得的回代规则是什么?

每次只把式子里最老的那个余数用它上一行的等式换掉,然后合并同类项,从下往上直到只剩最初的两个数(p.24)。

5. 911⁻¹ mod 999 等于多少?为什么最后要加 999?

等于 806。回代得到的系数是 −193,模逆要落在 0 到 998 之间,所以 −193 + 999 = 806(p.25)。

6. Bézout 等式里 b 的系数 y 在求逆元时有什么用?

没有用。y 乘的是 b,两边模 b 以后整项为 0,只留下 a 的系数 x(p.25)。

下一讲

下一页 L02d:素数、费马小定理与欧拉定理 讲怎么把 7 的 134 次方这种大指数降下来。去之前把例 2 的回代在纸上独立重做一遍。

下一讲 →
L02d L02d 费马小定理与欧拉定理:乘够圈数就回到 1

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