04 欧几里得算法
学习目标
理解并会使用公式 gcd(a,b)=gcd(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)gcd(a,b)=gcd(b,amodb)。
1. 例子
求 gcd(252,105)\gcd(252,105)gcd(252,105)：
252=105×2+42252=105\times2+42 252=105×2+42
所以：
gcd(252,105)=gcd(105,42)\gcd(252,105)=\gcd(105,42) gcd(252,105)=gcd(105,42)
继续：
105=42×2+21105=42\times2+21 105=42×2+21
所以：
gcd(105,42)=gcd(42,21)=21\gcd(105,42)=\gcd(42,21)=21 gcd(105,42)=gcd(42,21)=21
2. 为什么欧几里得算法成立
欧几里得算法的核心公式是：
gcd(a,b)=gcd(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)gcd(a,b)=gcd(b,amodb)
初看这个公式时，最容易产生三个疑问：
1. 为什么把 (a,b)(a,b)(a,b) 换成 (b,a mod b)(b,a\bmod b)(b,amodb) 后，公共因子不会发生变化？
2. 只证明一边的公共因子也是另一边的公共因子，怎么能保证另一边不会“多出来”新的公共因子？
3. 为什么不断辗转相除，最后一个非零余数一定就是最大的那个公共因子？
下面一步一步解决。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.1 先把余数写出来
设 a>b>0a>b>0a>b>0。
根据带余除法，一定可以写成：
a=qb+ra=qb+ra=qb+r
其中：
* qqq 是商；
* rrr 是余数；
* r=a mod br=a\bmod br=amodb；
* 0≤r<b0\le r<b0≤r<b。
把式子移项：
r=a−qbr=a-qbr=a−qb
所以我们真正需要证明的是：
gcd(a,b)=gcd(b,r)\gcd(a,b)=\gcd(b,r)gcd(a,b)=gcd(b,r)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.2 先证明：(A,B)(A,B)(A,B) 的公共因子，(B,R)(B,R)(B,R) 一定也有
假设 *** 是 a,ba,ba,b 的一个公共因子。
也就是说：
d∣ad\mid ad∣a
并且：
d∣bd\mid bd∣b
因为 d∣bd\mid bd∣b，所以 *** 也一定能整除 qbqbqb：
d∣qbd\mid qbd∣qb
又因为 d∣ad\mid ad∣a，所以 *** 一定能够整除它们的差：
d∣(a−qb)d\mid(a-qb)d∣(a−qb)
而：
a−qb=ra-qb=ra−qb=r
因此：
d∣rd\mid rd∣r
于是 *** 同时整除 bbb 和 rrr。
所以：
> 任意一个 (a,b)(a,b)(a,b) 的公共因子，也一定是 (b,r)(b,r)(b,r) 的公共因子。
这里要特别注意：
*** 不是某一个特殊的公共因子，而是任意一个公共因子。
因此我们证明的是：
(a,b) 的所有公共因子⊆(b,r) 的所有公共因子(a,b)\text{ 的所有公共因子}\subseteq(b,r)\text{ 的所有公共因子}(a,b) 的所有公共因子⊆(b,r) 的所有公共因子
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.3 但是，只证明这个包含关系还不够
这是整个证明里非常容易忽略的一点。
假设有两个集合：
A=1,2A={1,2}A=1,2
B=1,2,4B={1,2,4}B=1,2,4
显然：
A⊆BA\subseteq BA⊆B
但是 BBB 比 AAA 多了一个 4。
所以如果我们只证明：
(a,b) 的公共因子⊆(b,r) 的公共因子(a,b)\text{ 的公共因子}\subseteq(b,r)\text{ 的公共因子}(a,b) 的公共因子⊆(b,r) 的公共因子
那么只能说明：
> (a,b)(a,b)(a,b) 有的公共因子，(b,r)(b,r)(b,r) 全都有。
但是我们还不知道：
> (b,r)(b,r)(b,r) 会不会额外多出一些公共因子？
甚至可能担心它会多出一个更大的公共因子。
因此，只证明一个方向，还不能推出两边的最大公约数相同。
我们必须再证明反方向。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.4 再证明：(B,R)(B,R)(B,R) 的公共因子，(A,B)(A,B)(A,B) 一定也有
现在反过来。
假设 *** 是 b,rb,rb,r 的一个公共因子。
也就是说：
d∣bd\mid bd∣b
并且：
d∣rd\mid rd∣r
因为：
d∣bd\mid bd∣b
所以：
d∣qbd\mid qbd∣qb
又因为：
d∣rd\mid rd∣r
所以 *** 一定能够整除：
qb+rqb+rqb+r
而前面已经知道：
a=qb+ra=qb+ra=qb+r
因此：
d∣ad\mid ad∣a
所以 *** 同时整除 aaa 和 bbb。
也就是说：
> 任意一个 (b,r)(b,r)(b,r) 的公共因子，也一定是 (a,b)(a,b)(a,b) 的公共因子。
于是：
(b,r) 的所有公共因子⊆(a,b) 的所有公共因子(b,r)\text{ 的所有公共因子}\subseteq(a,b)\text{ 的所有公共因子}(b,r) 的所有公共因子⊆(a,b) 的所有公共因子
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.5 两个方向合起来，才能说明公共因子完全一样
现在已经有：
(a,b) 的所有公共因子⊆(b,r) 的所有公共因子(a,b)\text{ 的所有公共因子}\subseteq(b,r)\text{ 的所有公共因子}(a,b) 的所有公共因子⊆(b,r) 的所有公共因子
同时又有：
(b,r) 的所有公共因子⊆(a,b) 的所有公共因子(b,r)\text{ 的所有公共因子}\subseteq(a,b)\text{ 的所有公共因子}(b,r) 的所有公共因子⊆(a,b) 的所有公共因子
两个集合互相包含，所以它们只能完全相等：
(a,b) 的公共因子集合=(b,r) 的公共因子集合\boxed{(a,b)\text{ 的公共因子集合}=(b,r)\text{ 的公共因子集合}}(a,b) 的公共因子集合=(b,r) 的公共因子集合
这句话意味着：
* (b,r)(b,r)(b,r) 不会多出新的公共因子；
* (a,b)(a,b)(a,b) 也不会少掉任何公共因子；
* 两边拥有的是完全同一批公共因子。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.6 为什么公共因子完全一样，就能说明最大公约数一样？
举个具体例子。
取：
a=48a=48a=48
b=18b=18b=18
有：
48=18×2+1248=18\times2+1248=18×2+12
所以：
r=12r=12r=12
现在看 (48,18)(48,18)(48,18) 的所有公共因子：
1,2,3,61,2,3,61,2,3,6
再看 (18,12)(18,12)(18,12) 的所有公共因子：
1,2,3,61,2,3,61,2,3,6
两边完全一样。
既然公共因子集合都是：
1,2,3,6{1,2,3,6}1,2,3,6
那么其中最大的元素当然也一样，都是 6。
所以：
gcd(48,18)=gcd(18,12)=6\gcd(48,18)=\gcd(18,12)=6gcd(48,18)=gcd(18,12)=6
一般地，因为 (a,b)(a,b)(a,b) 与 (b,r)(b,r)(b,r) 的公共因子集合完全相同，所以它们最大的公共因子也必然相同：
gcd(a,b)=gcd(b,r)\gcd(a,b)=\gcd(b,r)gcd(a,b)=gcd(b,r)
又因为：
r=a mod br=a\bmod br=amodb
所以得到欧几里得算法的核心公式：
gcd(a,b)=gcd(b,a mod b)\boxed{\gcd(a,b)=\gcd(b,a\bmod b)}gcd(a,b)=gcd(b,amodb)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.7 为什么可以一直辗转相除？
既然每一次都有：
gcd(a,b)=gcd(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)gcd(a,b)=gcd(b,amodb)
那么我们就可以不断把问题换成更小的一组数。
例如：
gcd(48,18)\gcd(48,18)gcd(48,18)
第一次：
48=18×2+1248=18\times2+1248=18×2+12
所以：
gcd(48,18)=gcd(18,12)\gcd(48,18)=\gcd(18,12)gcd(48,18)=gcd(18,12)
第二次：
18=12×1+618=12\times1+618=12×1+6
所以：
gcd(18,12)=gcd(12,6)\gcd(18,12)=\gcd(12,6)gcd(18,12)=gcd(12,6)
第三次：
12=6×2+012=6\times2+012=6×2+0
所以：
gcd(12,6)=gcd(6,0)\gcd(12,6)=\gcd(6,0)gcd(12,6)=gcd(6,0)
连起来就是：
gcd(48,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)\gcd(48,18)=\gcd(18,12)=\gcd(12,6)=\gcd(6,0)gcd(48,18)=gcd(18,12)=gcd(12,6)=gcd(6,0)
这里最重要的不是：
> 数字越来越小。
而是：
> 数字虽然一直在变小，但最大公约数从头到尾都没有发生变化。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.8 为什么辗转相除一定会停止？
每次计算余数：
r=a mod br=a\bmod br=amodb
余数一定满足：
0≤r<b0\le r<b0≤r<b
如果 r≠0r\ne0r=0，那么：
r<br<br<b
也就是说，新的第二个数一定严格小于旧的第二个数。
于是会出现类似：
18>12>6>018>12>6>018>12>6>0
这样的过程。
这些数：
* 都是非负整数；
* 每一步都严格变小。
非负整数不可能无限地严格变小。
所以经过有限次计算以后，一定会出现余数为 0。
因此欧几里得算法一定会停止。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.9 为什么最后一个非零余数就是最大公约数？
最后一定会走到：
gcd(d,0)\gcd(d,0)gcd(d,0)
现在看 *** 和 0 的公共因子。
假设 k∣dk\mid dk∣d。
那么 kkk 也一定整除 0，因为：
0=k×00=k\times00=k×0
所以：
> *** 的所有因子，也全部都是 *** 和 0 的公共因子。
而 *** 的最大因子显然就是 *** 自己。
因此：
gcd(d,0)=d\gcd(d,0)=dgcd(d,0)=d
再回头看前面的过程：
gcd(a,b)=⋯=gcd(d,0)=d\gcd(a,b)=\cdots=\gcd(d,0)=dgcd(a,b)=⋯=gcd(d,0)=d
因为每一步的最大公约数都没有改变，所以：
> 最后一个非零余数 ***，就是最开始 a,ba,ba,b 的最大公约数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.10 最容易产生的误解
不要把辗转相除理解成：
> “不断除下去，最后剩下的数碰巧是最大的公共因子。”
真正的逻辑是：
> 每一次从 (a,b)(a,b)(a,b) 变成 (b,a mod b)(b,a\bmod b)(b,amodb) 时，都证明了新旧两组数的所有公共因子完全相同。
因此：
> 最大公约数从头到尾根本没有改变。
算法只是不断把数字变小，使这个一直没有改变的最大公约数最终变得“直接可见”。
当问题变成：
(d,0)(d,0)(d,0)
时，我们立刻就知道：
gcd(d,0)=d\gcd(d,0)=dgcd(d,0)=d
于是 *** 就是答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.11 整个证明的逻辑链
第一步，带余除法：
a=qb+ra=qb+ra=qb+r
其中：
r=a mod br=a\bmod br=amodb
第二步，证明：
(a,b) 的公共因子⊆(b,r) 的公共因子(a,b)\text{ 的公共因子}\subseteq(b,r)\text{ 的公共因子}(a,b) 的公共因子⊆(b,r) 的公共因子
第三步，再证明反方向：
(b,r) 的公共因子⊆(a,b) 的公共因子(b,r)\text{ 的公共因子}\subseteq(a,b)\text{ 的公共因子}(b,r) 的公共因子⊆(a,b) 的公共因子
第四步，得到：
(a,b) 的公共因子集合=(b,r) 的公共因子集合(a,b)\text{ 的公共因子集合}=(b,r)\text{ 的公共因子集合}(a,b) 的公共因子集合=(b,r) 的公共因子集合
第五步，因此：
gcd(a,b)=gcd(b,r)\gcd(a,b)=\gcd(b,r)gcd(a,b)=gcd(b,r)
也就是：
gcd(a,b)=gcd(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)gcd(a,b)=gcd(b,amodb)
第六步，不断重复：
(a,b)→(b,a mod b)→⋯→(d,0)(a,b)\rightarrow(b,a\bmod b)\rightarrow\cdots\rightarrow(d,0)(a,b)→(b,amodb)→⋯→(d,0)
整个过程中最大公约数始终不变。
最后：
gcd(d,0)=d\gcd(d,0)=dgcd(d,0)=d
所以：
gcd(a,b)=d\boxed{\gcd(a,b)=d}gcd(a,b)=d
也就是说：
> 辗转相除法中最后一个非零余数，就是最开始两个数的最大公约数。
3. C++ 模板
循环版：
4. 复杂度
可以记为 O(logmin(a,b))O(\log\min(a,b))O(logmin(a,b))。
5. 和后续知识的连接
以后经常会写：
6. 小练习
求：
1. gcd(48,18)\gcd(48,18)gcd(48,18)
2. gcd(100,35)\gcd(100,35)gcd(100,35)
3. gcd(17,13)\gcd(17,13)gcd(17,13)
答案
1. 6
2. 5
3. 1
