← COMP5521 全部讲次
L02b · 第 2 周

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

从列因子找最大公因数讲起,到互素的意思,再一行一行跑欧几里得算法,最后看它为什么十位数也只要十步。

一句话版

两个数的最大公因数(gcd),是能同时整除它们的最大的那个数。欧几里得算法求它的办法很简单:拿小数去除大数,留下余数,再拿余数去除刚才的小数,一直除到余数为 0,最后一个不为 0 的余数就是答案。

这一页要用到上一页 L02a 的带余除法。求出 gcd 以后,下一页会用它判断模逆存不存在。

先认识这几个词

词 全称 / 读法 一句人话
因子 / 因数 divisor, factor 能把一个数除尽的数
公因数 common divisor 同时能除尽两个数的数
gcd(a, b) Greatest Common Divisor,最大公因数 公因数里最大的那个
互素 relatively prime, coprime 两个数的 gcd 是 1,除了 1 没有公因数
欧几里得算法 Euclidean algorithm,辗转相除法 反复做带余除法求 gcd 的方法
O(log n) 读「大 O log n」 步数大约跟数字的位数成正比

一个类比:用地砖铺满长方形

一间房长 710、宽 310,想用同样大小的正方形地砖把地面刚好铺满,不能切砖。地砖边长最大能取多少?答案就是 gcd(710, 310)。

欧几里得的做法是这样的:先在长边上尽量铺宽 310 的大正方形,铺下两块,剩一条宽 90 的长条。再在这条长条里铺边长 90 的正方形,又剩一条。一直铺下去,直到某一次正好铺满,没有剩余。最后那块正方形的边长,就能把前面每一块都量尽,它就是答案。

类比在哪里失效:

  • 地砖要求边长是正数。gcd 的定义允许负数和 0,比如 gcd(a, 0) = |a|,这在铺地砖时说不通。
  • 铺地砖是几何画面。真正手算时不用画图,只要一行一行写带余除法。

从零讲起

1. 最大公因数

它解决什么问题

两个数之间有没有共同的「零件」,零件最大有多大,是数论里最常问的问题之一。后面判断模逆存不存在、分数能不能约分,问的都是它。

直觉

把两个数各自的因子列出来,找两张清单里都有的数,挑最大的。

这个办法对小数字很好用。数字一大,列因子就很慢,于是有了第 3 个概念的欧几里得算法。

一步一步看

目标:列出 6 和 18 的因子清单取交集,看出较小数整除较大数时,gcd 就是那个较小数。

  1. 求 gcd(6, 18)。先列 6 的因子:1、2、3、6。

  2. 再列 18 的因子:1、2、3、6、9、18。

  3. 两张清单都有的是 1、2、3、6,最大的是 6。

    两组因子格子。上面一组是 6 和 18:6 的因子 1、2、3、6,18 的因子 1、2、3、6、9、18,公共的 6 用青绿框出,gcd = 6。下面一组是 8 和 15:8 的因子 1、2、4、8,15 的因子 1、3、5、15,公共的只有 1,所以互素

  4. 所以 gcd(6, 18) = 6。6 本身就整除 18,这时 gcd 就是较小的那个数。

怎么算

gcd(a, b) = max{ k : k | a 且 k | b }

意思是:在所有同时整除 a 和 b 的整数 k 里,取最大的那个。

几条边界情况要记住,它们全是按定义推出来的:

  • gcd(a, b) = gcd(|a|, |b|)。gcd 不管正负号,所以一般只讨论正整数。
  • gcd(a, 0) = |a|。任何整数都整除 0,所以 0 的因子清单是「所有整数」,和 a 的清单取交集就是 a 自己的因子,最大的是 |a|。
  • gcd(0, 0) 按惯例规定为 0。两边都是 0 时,所有整数都是公因数,找不出最大的。
  • gcd(a·n, a) = |a|。a 同时整除这两个数,而且公因数不可能比 |a| 更大。

gcd(a, 0) = |a| 这一条,在第 3 个概念里是算法停下来的出口。

常见误解

以为 gcd(a, 0) 等于 0

0 能被任何非零整数整除,所以 a 的每一个因子都是 a 和 0 的公因数,最大的是 |a|。gcd(7, 0) = 7。

以为 gcd 一定比两个数都小

可以等于较小的那个。gcd(6, 18) = 6,6 本身就整除 18。

试一下

列因子求 gcd(12, 30)。

12 的因子 1、2、3、4、6、12;30 的因子 1、2、3、5、6、10、15、30。公共的是 1、2、3、6,最大的是 6。

gcd(−9, 0) 等于多少?

等于 9。gcd 不管符号,gcd(−9, 0) = gcd(9, 0) = 9。

2. 互素

它解决什么问题

有时只想知道两个数之间有没有大于 1 的公因数,不在乎最大公因数具体是几。互素就是「没有」的意思。本讲后面的模逆、欧拉定理、中国剩余定理,前提里都写着互素。

直觉

两个数互素,是说它们没有共同的零件。这跟它们自己是不是素数没有关系。8 是合数,15 也是合数,但 8 只由 2 组成,15 由 3 和 5 组成,没有交集。

一步一步看

目标:把 8 和 15 的因子并排对照,看出两数公共因子只剩 1 时就叫互素。

  1. 写出 8 的因子:1、2、4、8。

  2. 写出 15 的因子:1、3、5、15。

  3. 把两张清单放在一张表里对比:

    数 因子
    8 1、2、4、8
    15 1、3、5、15
    公共 只有 1
  4. 公共因子只有 1,gcd(8, 15) = 1,所以 8 和 15 互素。

怎么判断

a 与 b 互素  ⟺  gcd(a, b) = 1

意思是:算出 gcd,等于 1 就互素,大于 1 就不互素。

两个快速判断:相邻的两个整数一定互素,比如 15 和 16;两个不同的素数一定互素,比如 5 和 7。如果两个数都是偶数,它们至少有公因数 2,一定不互素。

常见误解

以为互素要求两个数都是素数

8 和 15 都是合数,照样互素。互素说的是两个数之间的关系,素数说的是一个数自己的性质。

以为一个素数和任何数都互素

素数 p 和它自己的倍数不互素。7 和 14 的 gcd 是 7。素数 p 只和不含因子 p 的数互素。

试一下

9 和 28 互素吗?

互素。9 的因子 1、3、9;28 的因子 1、2、4、7、14、28。公共只有 1。

21 和 35 互素吗?

不互素。两个数都含因子 7,gcd(21, 35) = 7。

3. 欧几里得算法

它解决什么问题

列因子的方法只适合小数字。两个几百位的大数根本列不出因子,因为分解大数非常慢。欧几里得算法不用分解,只靠反复做除法就能求出 gcd。

从哪来(补充)

这个算法写在欧几里得的《几何原本》里,大约是公元前 300 年。整数版本在第 VII 卷开头两个命题,第 X 卷还有一个讲长度的版本。它很可能在欧几里得之前就有人知道,是至今仍在使用的最古老的算法之一。

出处:Wikipedia: Euclidean algorithm

直觉

关键是一个观察:拿 a 除以 b,得到 a = q × b + r。凡是同时整除 b 和 r 的数,也一定整除 a;凡是同时整除 a 和 b 的数,也一定整除 r = a − q × b。

所以 (a, b) 这一对和 (b, r) 这一对,公因数完全相同,最大公因数也一样。换成 (b, r) 以后数字变小了,一直换下去,余数总会变成 0。

一步一步看

目标:用 gcd(710, 310) 一轮轮做带余除法,看出问题怎样不断缩小,最后一个非零余数就是答案。

求 gcd(710, 310)。

  1. 710 除以 310:710 = 2 × 310 + 90。问题换成 gcd(310, 90)。

  2. 310 除以 90:310 = 3 × 90 + 40。问题换成 gcd(90, 40)。

  3. 90 除以 40:90 = 2 × 40 + 10。问题换成 gcd(40, 10)。

  4. 40 除以 10:40 = 4 × 10 + 0。余数为 0,停。

    四行条形图求 gcd(710, 310)。第一行 710 切出两段 310,剩零头 90;第二行 310 切出三段 90,剩 40;第三行 90 切出两段 40,剩 10;第四行 40 正好切成四段 10,没有零头,青绿标出的 10 就是 gcd

  5. 最后一个非零余数是 10,所以 gcd(710, 310) = 10。

再看一个结果为 1 的例子,gcd(93, 16),写成竖式:

欧几里得算法求 gcd(93, 16) 的四行竖式:93 = 5 × 16 + 13,16 = 1 × 13 + 3,13 = 4 × 3 + 1,3 = 3 × 1 + 0。每一行的除数滑成下一行的被除数、余数滑成下一行的除数,最后一个非零余数 1 就是答案,递归出口是 gcd(a, 0) = |a|

怎么算

课件给的递归写法:

GCD(p, q) = p                  如果 q = 0
          = GCD(q, p mod q)    否则

意思是:如果第二个数是 0,答案就是第一个数;否则把这对数换成「第二个数」和「第一个数除以第二个数的余数」,再求一次。

第一行用的就是 gcd(a, 0) = |a|。第二行用的就是直觉里那个观察:gcd(p, q) = gcd(q, p mod q)。

手算时写成一列带余除法,每一行的除数和余数,下移一行变成新的被除数和除数。余数出现 0 时停,答案是上一行的余数,也就是最后一行的除数。

课件第 10 页的流程图写成循环:开头如果 a < b 就交换;每轮用 b 替换 a、用余数替换 b;余数为 0 时输出 b。换成 while b ≠ 0: (a, b) ← (b, a mod b) 这种写法时,退出循环后输出的是 a。两种写法输出的都是最后一个非零余数。

常见误解

以为答案是最后一行的余数

最后一行的余数是 0。答案是最后一个不为 0 的余数,也就是倒数第二行的余数。

以为一开始必须把大数放在前面

放反了也没关系。gcd(310, 710) 第一步算 310 mod 710 = 310,问题变成 gcd(710, 310),自动摆正了,只是多了一步。

试一下

用欧几里得算法求 gcd(84, 36)。

84 = 2 × 36 + 12;36 = 3 × 12 + 0。最后一个非零余数是 12,gcd = 12。

用欧几里得算法求 gcd(55, 34)。

55 = 1 × 34 + 21;34 = 1 × 21 + 13;21 = 1 × 13 + 8;13 = 1 × 8 + 5;8 = 1 × 5 + 3;5 = 1 × 3 + 2;3 = 1 × 2 + 1;2 = 2 × 1 + 0。gcd = 1,55 和 34 互素。

4. 为什么欧几里得算法这么快

它解决什么问题

密码学里的数有几百位。一个算法如果步数跟数字本身一样大,根本跑不完。这一节说明欧几里得算法的步数只跟数字的位数有关。

直觉

每做两次除法,余数至少缩小一半。缩小一半这件事很厉害:一个十位数反复减半,几十次就到 0 了。所以步数大约跟位数成正比,课件写作 O(log min(p, q))。

分解质因数就没有这样的捷径。这个快慢差别,后面会成为 RSA 安全性的来源之一:求 gcd 很快,分解大数很慢。

一步一步看

目标:跟踪一对十位数的余数逐轮缩小,看出欧几里得算法十轮就能算完。

课件给了一对十位数 a = 1160718174、b = 316258250。

  1. 第 1 轮:1160718174 = 3 × 316258250 + 211943424。

  2. 第 2 到第 4 轮:余数依次变成 104314826、3313772、1587894。

  3. 第 5 到第 8 轮:余数依次变成 137984、70070、67914、2156。

  4. 第 9 轮:67914 = 31 × 2156 + 1078。第 10 轮:2156 = 2 × 1078 + 0。

    十根柱子表示十轮的余数,高度按位数画,即对数刻度:从 211943424 一路降到 1078,第 10 轮是 0。青绿标出的第 9 轮余数 1078 是最后一个非零余数,也就是答案

  5. 十轮就结束了,gcd = 1078 = 2 × 7² × 11。

怎么算

步数 = O(log min(p, q))

意思是:步数的增长速度跟较小那个数的位数相当。数字的位数翻一倍,步数大约也只翻一倍。

为什么两步至少减半,可以这样看。设某一行是 a = q × b + r,且 a ≥ b。如果 b 不超过 a 的一半,那么 r < b 也不超过 a 的一半。如果 b 超过 a 的一半,那么 q = 1,r = a − b 不到 a 的一半。两种情况下,余数 r 都不到 a 的一半,而 r 两行之后就会坐到 a 原来的位置上。

常见误解

以为数越大,欧几里得算法的步数也同比例变多

数字从十位涨到二十位,数值涨了一百亿倍,步数大约只翻一倍。步数看的是位数。

试一下

课件的十位数例子里,第 4 轮的商是 31。为什么这一轮余数一下子少了一大截?

商大说明除数比被除数小很多。104314826 里能装下 31 个 3313772,余数 1587894 比被除数小了六十多倍。商越大,这一步缩得越快。

把它们串起来

gcd 是两个数共同的最大零件;gcd = 1 时叫互素;欧几里得算法不用分解质因数,只靠带余除法就能求出 gcd;它的步数只跟位数有关,所以对几百位的大数也能用。

这一页的算法只告诉你 gcd 是几。下一页 L02c 会把它的每一行倒着用回去:从最后一个余数出发,一行一行往上代入,把 gcd 写成两个原数的整数组合。那一步叫扩展欧几里得算法,它能求出模逆。

课件里的坑

  • [容易漏看] 课件 p.7 的四处填空全是边界情况,其中 gcd(a, 0) = |a| 是 p.9 递归的出口,不是凑数(p.7)
  • [口径差异] 课件 p.10 的流程图终止时输出 b;按 while b≠0: (a,b)←(b,a mod b) 写的代码退出时输出 a。两者都是最后一个非零余数,记规则不记变量名(p.10)
  • [课件留白] 课件 p.12 的十轮表格没有写最终答案,要自己看出是 1078(p.12)
  • [容易漏看] 课件 p.13 先算 gcd(93, 16) = 1,是在给 p.26 求 16⁻¹ mod 93 铺路:先证互素,再求逆(p.13)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写欧几里得算法的递归两行;再把课件例题从 p.11 起逐道自己算一遍;最后做变式题,回查最容易错的地方,答案取成了最后一行的余数 0。

必背

  1. gcd(a, b) 是同时整除 a、b 的最大整数;gcd(a, 0) = |a| 是欧几里得递归的出口,gcd(0, 0) 按惯例取 0。
  2. 互素指 gcd(a, b) = 1,与两个数是不是素数无关:8 与 15 都是合数但互素。
  3. 欧几里得算法 gcd(p, q) = gcd(q, p mod q),每一行的除数和余数变成下一行的被除数和除数。
  4. 算法的答案是最后一个非零余数,余数为 0 时停。
  5. 步数是 O(log min(p, q)):十位数的例子十轮就出 gcd = 1078,远快于分解质因数。

课件例题

例 1(课件 p.7):GCD 的边界情况

题面:填出 gcd(0, 0)、gcd(a, 0)、gcd(a, b) 与 gcd(|a|, |b|) 的关系、gcd(a·n, a),再算 gcd(6, 18)。

提示

每一条都回到定义:同时整除两个数的最大整数。任何整数都整除 0。

解答

gcd(0, 0) 按惯例规定为 0:任何整数都整除 0,找不出「最大」的公因数。

gcd(a, 0) = |a|:a 的最大因子是 |a|,它也整除 0。这条就是欧几里得递归的出口。

gcd(a, b) = gcd(|a|, |b|):GCD 与符号无关。gcd(a·n, a) = |a|:a 整除两者,且不可能更大。

gcd(6, 18) = 6:6 的因子 1, 2, 3, 6 全是 18 的因子,最大的是 6。

例 2(课件 p.8):8 和 15 互素吗

题面:分别写出 8 和 15 的正因子,判断两者是否互素。

提示

看两张因子清单的交集里有没有大于 1 的数。

解答

8 的正因子 1, 2, 4, 8;15 的正因子 1, 3, 5, 15。公共因子只有 1,所以互素。两个数都是合数,照样可以互素。

例 3(课件 p.11):手算 gcd(710, 310)

题面:用欧几里得算法求 710 和 310 的最大公因数,写出每一步除法式。

提示

每一行写成「被除数 = 商 × 除数 + 余数」,余数为 0 时停。

解答

710 = 2 × 310 + 90;310 = 3 × 90 + 40;90 = 2 × 40 + 10;40 = 4 × 10 + 0。余数为 0 时停,最后一个非零余数是 10。

每一行的除数和余数变成下一行的被除数和除数,每次替换 GCD 都不变。验算:710 = 2 × 5 × 71,310 = 2 × 5 × 31,公共部分 2 × 5 = 10。

例 4(课件 p.12):十位数的 GCD 只要十步

题面:a = 1160718174,b = 316258250,跑欧几里得算法求 gcd(a, b)。课件的表格列了十轮,没写最终答案。

提示

看第 10 轮的余数是不是 0。如果是,答案在第 9 轮的余数里。

解答

十轮的商依次是 3, 1, 2, 31, 2, 11, 1, 1, 31, 2。余数依次是 211943424、104314826、3313772、1587894、137984、70070、67914、2156、1078、0。

第 10 轮是 2156 = 2 × 1078 + 0,所以 gcd = 1078(= 2 × 7² × 11)。这道题要你体会的是速度:十位数只要十步,换成质因数分解是完全不同量级的工作量。

例 5(课件 p.13,Exercise-1):手算 gcd(93, 16)

题面:用欧几里得算法求 93 和 16 的最大公因数。

提示

第一步是 93 除以 16。一共四行。

解答

93 = 5 × 16 + 13;16 = 1 × 13 + 3;13 = 4 × 3 + 1;3 = 3 × 1 + 0。所以 gcd(93, 16) = 1,93 与 16 互素。

这一步是在给下一页的 16⁻¹ mod 93 铺路:互素才保证 16 模 93 的逆元存在。

例 6(课件 p.47,Exercise-7):手算 gcd(210, 28)

题面:用欧几里得算法求 210 和 28 的最大公因数。

提示

两行就结束。

解答

210 = 7 × 28 + 14;28 = 2 × 14 + 0,所以 gcd = 14。验算:210 = 2 × 3 × 5 × 7,28 = 2² × 7,公共部分 2 × 7 = 14。

完整例题

这一块的考法很固定:给两个数,要求写出欧几里得算法的每一行,再给出 gcd。

题面:用欧几里得算法求 gcd(1071, 462),并用质因数分解验算。

解法:

  1. 第一行,大数除以小数:1071 = 2 × 462 + 147。
  2. 除数 462 和余数 147 下移:462 = 3 × 147 + 21。
  3. 再下移:147 = 7 × 21 + 0,余数为 0,停。
  4. 最后一个非零余数是 21,gcd(1071, 462) = 21。
  5. 验算:1071 = 3² × 7 × 17,462 = 2 × 3 × 7 × 11,公共部分 3 × 7 = 21,一致。

答题格式:每一行都写完整的「被除数 = 商 × 除数 + 余数」;写出余数为 0 的那一行,表明算法停在哪;最后一句点明答案取的是最后一个非零余数。

变式题(先自己做)

改编自课件 p.11:用欧几里得算法求 gcd(252, 198)。

提示

一共四行除法。第三行的商是 1,别看漏。

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

判分点:① 每一行除法式正确;② 写出余数为 0 的行;③ 答案取最后一个非零余数。

252 = 1 × 198 + 54;198 = 3 × 54 + 36;54 = 1 × 36 + 18;36 = 2 × 18 + 0。

gcd(252, 198) = 18。验算:252 = 2² × 3² × 7,198 = 2 × 3² × 11,公共部分 2 × 3² = 18。

闪卡自测

1. gcd(a, 0) 等于多少?它在欧几里得算法里起什么作用?

等于 |a|。它是递归的出口:第二个数变成 0 时,第一个数就是答案(p.7、p.9)。

2. 8 和 15 都不是素数,它们互素吗?

互素。8 的因子是 1、2、4、8,15 的是 1、3、5、15,公共因子只有 1。互素说的是两数没有大于 1 的公因子,跟它们各自是不是素数无关(p.8)。

3. 为什么 gcd(p, q) = gcd(q, p mod q)?

p = kq + r 时,同时整除 q 和 r 的数也整除 p;同时整除 p 和 q 的数也整除 r。两对数的公因数完全相同,最大的那个自然也相同(p.9)。

4. 欧几里得算法终止时答案取 a 还是 b?

看停止条件。p.10 的流程图取 b;标准 while b≠0: (a,b)←(b,a mod b) 退出时则取 a。两者都返回最后一个非零余数。

5. 课件 p.12 那对十位数的 gcd 是多少?这道题想说明什么?

gcd = 1078。十位数十轮就出结果,说明欧几里得算法的步数只跟位数有关,比分解质因数快得多(p.12)。

6. 欧几里得算法的步数是什么量级?

O(log min(p, q)),大约跟较小那个数的位数成正比(p.9)。

下一讲

下一页 L02c:模逆与扩展欧几里得算法 讲模运算里的「除法」。去之前把 gcd(93, 16) 的四行除法再写一遍,下一页要把这四行倒着代回去。

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

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