辗转相除法（欧几里得算法）的证明

欢迎访问我的主页: https://heeheeaii.github.io/

辗转相除法是一种用于计算两个非负整数最大公约数的有效算法。它的证明主要分为两个部分：

• 证明核心引理： gcd(a,b)=gcd(b,amodb)
• 证明算法的收敛性： 证明算法一定会在有限步内结束。

辗转相除法简介

在开始证明之前，先回顾一下辗转相除法的步骤。对于任意两个正整数 a 和 b (不妨设 a>b)：

1. 用 a 除以 b，得到商 q 和余数 r。即 a=qb+r，其中 0≤r<b。
2. 如果余数 r 为 0，那么 b 就是 a 和 b 的最大公约数。
3. 如果余数 r 不为 0，则将原来的除数 b 作为新的被除数，将余数 r 作为新的除数，重复第一步。

如此循环，直到余数为 0。此时，最后一次计算中的除数就是原始 a 和 b 的最大公约数。

引理： 设 a,b 为两个正整数，且 a=qb+r（其中 q 为商， r 为余数，0≤r<b），那么 a 和 b 的最大公约数等于 b 和 r 的最大公约数。即：gcd(a,b)=gcd(b,r)。

证明过程：

为了证明这个等式，只需要证明 (a,b) 的公约数集合与 (b,r) 的公约数集合是完全相同的。如果两个集合完全相同，那么它们各自的最大元素（即最大公约数）也必然相等。

1. 证明：任何 (a,b) 的公约数 d，也一定是 (b,r) 的公约数。

假设 d 是 a 和 b 的一个任意公约数。根据公约数的定义，有 d∣a 和 d∣b。（这里的 ∣ 表示“整除”）。

因为 d 能整除 a 和 b，所以 d 也能整除它们的任意线性组合。将算法中的等式 a=qb+r 变形为 r=a−qb。因为 d∣a 且 d∣b，所以 d 必然能整除 a−qb。因此，得到 d∣r。

既然已知 d∣b 且证明了 d∣r，那么 d 就是 b 和 r 的一个公约数。

2. 证明：任何 (b,r) 的公约数 d′，也一定是 (a,b) 的公约数。

假设 d′ 是 b 和 r 的一个任意公约数。根据定义，有 d′∣b 和 d′∣r。

因为 d′ 能整除 b 和 r，所以 d′ 也能整除它们的任意线性组合。从算法等式 a=qb+r 中，可以看到 a 正是 b 和 r 的一个线性组合。因为 d′∣b（所以 d′∣qb）且 d′∣r，所以 d′ 必然能整除 qb+r。因此，得到 d′∣a。

既然已知 d′∣b 且证明了 d′∣a，那么 d′ 就是 a 和 b 的一个公约数。

1. 算法为什么一定会终止？

在辗转相除法的每一步中，都有一个等式： ri−1=qi⋅ri+ri+1

其中 ri−1 是被除数，ri 是除数，ri+1 是余数。根据整数除法的性质，余数必须严格小于除数，且不能为负数。所以得到一个余数序列： b>r1>r2>r3>⋯>rn≥0

这是一个由非负整数组成的严格递减序列。任何由非负整数组成的严格递减序列最终必然会达到 0。因此，算法一定会在有限步内终止，即一定会出现某一步的余数 rn+1=0。

2. 为什么余数为 0 时，当时的除数就是最大公约数？

根据核心引理，可以将求 gcd(a,b) 的过程转化为一个链条： gcd(a,b)=gcd(b,r1)=gcd(r1,r2)=⋯=gcd(rn−1,rn)

当算法进行到最后一步时，余数为 0。假设这一步的表达式为： rn−1=qn+1⋅rn+0

这表示 rn 能够整除 rn−1。那么，需要求解的就是 gcd(rn−1,rn)。根据最大公约数的定义，一个数 (rn−1) 和它的约数 (rn) 的最大公约数就是那个约数本身 (rn)。 所以，gcd(rn−1,rn)=rn。

将这个结果代入上面的等式链条，得到： gcd(a,b)=gcd(rn−1,rn)=rn

这里的 rn 正是算法终止前的最后一个非零余数，也就是最后一步计算中的除数。

举例说明：

用 gcd(1071,462) 来演示这个过程：

• 1071=2⋅462+147 根据引理：gcd(1071,462)=gcd(462,147)
• 462=3⋅147+21 根据引理：gcd(462,147)=gcd(147,21)
• 147=7⋅21+0 根据引理：gcd(147,21)=gcd(21,0) 此时余数为 0，算法终止。最后一步的除数是 21。

把整个链条连起来： gcd(1071,462)=gcd(462,147)=gcd(147,21)=21

所以，1071 和 462 的最大公约数是 21。