深入算法:从0开始证明欧几里得算法

什么是欧几里得算法?

学过算法或者程序设计递归实现的时候, 我们会经常会看到求解最大公约数的例子, 今天我们就介绍并证明求解公约数的方法: 辗转相除法： 又名欧几里德算法（Euclidean algorithm)。

int gcd(a, b)
{
	if (b == 0) return a;
	return gcd(b, a % b) 
}
1
2
3
4
5
6

我们先分析一下这个算法的大概流程: 假如a = 25, b = 10
第一次运行时gcd(25, 10) 我们会返回gcd(10, 25 % 10)也就是gcd(10, 5)
于是程序开始递归, 因为此时 b 不为0, 所有第二次返回的是gcd(5, 10 % 5)也就是gcd(5, 0)
此时的参数 b 已经为 0 了， 结果直接返回 a 也就是 5, 所以 25 和 10 的最大公约数是 5

那么, 想要证明欧几里得算法实际要证明 gcd=(a,b) = gcd(b,a%b) 就可以了， 也就是说如果 c 是 a 和 b 的最大公约数, 那么 c 也是 b 和 a % b 的最大公约数

命题

欧几里得算法最先提出的命题如下:
设 n 是一个自然数，q 表示一个正自然数，那么存在自然数 m 和 r 使得 0 <= r < q 并且 n = m*q + r

在证明这个命题前, 我们先要知道关于自然数的一个性质:
假设 a, b 为任意自然数, 那么 a < b 当且仅当 a + 1 <= b

知道这一性质后我们就可以通过数学归纳法证明欧几里得算法了:

顺便提一下， 正因这个算法标志着数论的开始，至于数论是什么? 可以打个比方, 密码学rsa(非对称加密)等算法的设计就是个数论问题

继续证明辗转相除法

回到正题, 现在我们知道自然数都可以表示为 n = m*q + r 的形式， 聪明的你会发现这条式子的意义: 当用一个正自然数去除一个自然数 n 的时候, m 为商, r 就是余数， 也就是(n % m)

假设 a 是n, m 的公约数，也就是 n, m 能被 a 整除
接下来我们只需要证明 r 也能被 a 整除

下面我们对其变形:
r = n - mq
同时除 a 得:
r / a = n / a - (mq) / a
由于 a 是n, m 的公约数, 所以 n / a 是整数, (m * q) / a 也是整数, 那么两个整数相减得到的还是一个整数 r / a
于是我们就证明了 r 也能被 a 整除, 这就是为什么说 a,b 和 b,a%b 的最大公约数相等了!

收获与感想

在学习欧几里得算法的时候搜索了大部分的证法, 他们第一步直接假设 n = mq + r , 并没有给出"自然数都可以表示为 n = mq + r 的形式"的证明。。。
证明的方法来自于<<陶哲轩实分析>>中介绍的数学归纳法，这真是个证明命题的好方法, 只要假设性质 P(n) 成立, 那么只要证明性质 P(n++) 就可以了, 实际上像自然数系，整数等数系的定义都是通过类似的递归定义得到的, 真是太奇妙了!!!