《算法基础》——2.2　寻找最大公约数

本节书摘来自华章计算机《算法基础》一书中的第2章，第2.2节，作者：（美）罗德·斯蒂芬斯（Rod Stephens）著，更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.2　寻找最大公约数

两个整数的最大公约数（Greatest Common Divisor，GCD）是指两个整数共有约数中最大的一个。例如，GCD(60，24)为12，因为12是60和24共有约数中最大的。（最大公约数也许看起来像一个深奥的功能，但是它实际上在加密程序中十分有用，这些加密程序被广泛用于金融通信安全等领域。）
注　如果GCD(A，B)＝1，那么A和B被称作互质（relatively prime或coprime）。
一个找到最大公约数的方法是将两个因数分解并且找到它们共有的因数。但是希腊数学家欧几里得在他著于公元前300年的论述《几何原本》中记录了一个更快捷的方法。以下伪代码展示了这个算法的现代版。因为它是基于欧几里得的著作，这个算法被叫做欧几里得算法（Euclidian algorithm或Euclid抯 algorithm）：

例如，计算GCD(4831，3003)。表2-2展示了A、B和每一步B除以A的余数M的值。

当B为0时，变量A即为最大公约数，本例中最大公约数为231。验证一下结果，考虑到4851＝231×21，而3003＝231×13，因此231是两数的公约数。21和13除1之外没有共同的因数，所以231是4851和3003的最大公约数。
最大公约数
如果你愿意的话，这是另一个可以跳过的数学解释。
欧几里得算法的关键是这个事实：GCD(A, B)＝GCD(B, A Mod B)。
要理解为什么这是正确的，可以考虑取模运算符的定义。如果余数R＝A Mod B，那么对于整数m，A＝m×B＋R。如果g是A和B的最大公约数，g是B的约数，所以g也必定是m×B的约数。因为g是A的约数并且A＝m×B＋R，g必定是m×B＋R的约数。因为g是m×B的约数，它也一定是R的约数。
这证明了g是B和R的约数。g＝GCD(B，R)的意思是g是能够约分B和R的最大整数。
假设G是一个比g大的整数，并且G 是B和R的约数，那么G也是m×B的约数。但是A＝m×B＋R，所以G也是A的约数。这就意味着g不是A和B的最大公约数。这与g是A和B最大公约数的条件矛盾，因为这与G＞g的假定产生了矛盾，因此不存在这样的G，故g为A和B的最大公约数。

这个算法是较为快捷的，每两次While循环中，B值被一个因数至少减少为其1/2。因为B值在每两次迭代中被一个因数减少至少1/2，所以这个算法的运行时间复杂度至多为O(log B)。
对速度的需求
欧几里得算法中的B值在每两次While循环中被一个因数至少减少为其1/2。为了一探究竟，令Ak、Bk和Rk为第k次迭代中A、B和R的值，并且认为对于任意整数m，A1＝ m1×B1＋R1。在第二次迭代中，A2＝B1而B2＝A1。
如果R1≤B1/2，那么可知B2≤B1。
假设R1＞B1，在第三次迭代中，A3＝B2＝R1并且B3＝R2。根据定义，R2＝A2 Mod B2，且与B1 Mod R1相等。由于我们假设R1＞B1/2，所以R1能够除B1一次并且留下余数(B1-R1)。
由于我们假设R1＞B1/2，故可知(B1-R1)≤B1/2。
回到最初的方程式：(B1-R1)＝(B1 Mod R1)＝(A2 Mod R2)＝R2＝B3。因此B3≤B1/2，这是我们要证明的。