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 就是那个较小数。
-
求 gcd(6, 18)。先列 6 的因子:1、2、3、6。
-
再列 18 的因子:1、2、3、6、9、18。
-
两张清单都有的是 1、2、3、6,最大的是 6。
-
所以 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 时就叫互素。
-
写出 8 的因子:1、2、4、8。
-
写出 15 的因子:1、3、5、15。
-
把两张清单放在一张表里对比:
数 因子 8 1、2、4、8 15 1、3、5、15 公共 只有 1 -
公共因子只有 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)。
-
710 除以 310:710 = 2 × 310 + 90。问题换成 gcd(310, 90)。
-
310 除以 90:310 = 3 × 90 + 40。问题换成 gcd(90, 40)。
-
90 除以 40:90 = 2 × 40 + 10。问题换成 gcd(40, 10)。
-
40 除以 10:40 = 4 × 10 + 0。余数为 0,停。
-
最后一个非零余数是 10,所以 gcd(710, 310) = 10。
再看一个结果为 1 的例子,gcd(93, 16),写成竖式:
怎么算
课件给的递归写法:
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 轮:1160718174 = 3 × 316258250 + 211943424。
-
第 2 到第 4 轮:余数依次变成 104314826、3313772、1587894。
-
第 5 到第 8 轮:余数依次变成 137984、70070、67914、2156。
-
第 9 轮:67914 = 31 × 2156 + 1078。第 10 轮:2156 = 2 × 1078 + 0。
-
十轮就结束了,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。
必背
- gcd(a, b) 是同时整除 a、b 的最大整数;gcd(a, 0) = |a| 是欧几里得递归的出口,gcd(0, 0) 按惯例取 0。
- 互素指 gcd(a, b) = 1,与两个数是不是素数无关:8 与 15 都是合数但互素。
- 欧几里得算法 gcd(p, q) = gcd(q, p mod q),每一行的除数和余数变成下一行的被除数和除数。
- 算法的答案是最后一个非零余数,余数为 0 时停。
- 步数是 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),并用质因数分解验算。
解法:
- 第一行,大数除以小数:1071 = 2 × 462 + 147。
- 除数 462 和余数 147 下移:462 = 3 × 147 + 21。
- 再下移:147 = 7 × 21 + 0,余数为 0,停。
- 最后一个非零余数是 21,gcd(1071, 462) = 21。
- 验算: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) 的四行除法再写一遍,下一页要把这四行倒着代回去。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。