4.7　对最大公约数算法进行验证

要想证明刚才那个求整数最大公约数的算法是正确的，我们需要从两个方面入手。第一，证明该算法会终止；第二，证明该算法可以算出最大公约数。

为了证明算法确实能够终止，我们需要根据下面这条规律来做出推理：

根据这个规律，每轮循环所产生的余数都比上一轮小。由于任何一个由正整数所构成的递减数列都是有限数列，因此，该算法必定会在某处终止。

为了证明算法确实能够算出最大公约数，我们首先注意到，在每轮循环中算法都会计算a与b的余数r。根据余数的定义可知：

其中的q是a除以b所得的整数商。a与b的任何一个公约数都可以整除a，而该公约数同时又能够整除b，进而也能够整除bq，因此，它必定可以整除a与bq的差也就是r。此外，我们还可以把刚才那个等式变换为：

根据同样的道理，b与r的任何一个公约数都可以整除b，进而也可以整除bq，而该公约数同时又能够整除r，因此，它必定可以整除bq与r的和，也就是a。综上可知：a与b的任何一个公约数都是b与r的公约数，而b与r的任何一个公约数也都是a与b的公约数，因此，（a，b）与（b，r）这两组数字肯定具备同一套公约数，于是，它们之间的最大公约数也一定是相同的。我们可以说：

每次循环时，算法都会通过计算余数及交换参数这两项操作来把gcd（a，b）化为gcd（b，r）。我们从a ₀ 与b ₀ （也就是a与b这两个参数的初始值）开始，列出算法在每一轮所求出的余数：

r ₁ =remainder（a ₀ ，b ₀ ）

r ₂ =remainder（b ₀ ，r ₁ ）

r ₃ =remainder（r ₁ ，r ₂ ）

...

r _n =remainder（r _n-2 ，r _n-1 ）

根据余数的定义，上面那些式子可以分别写为：

r ₁ =a ₀ -b ₀ q ₁

r ₂ =b ₀ -r ₁ q ₂

r ₃ =r ₁ -r ₂ q ₃

...

r _n =r _n-2 -r _n-1 q _n

根据等式（4.1）可知，算法刚开始想要求出的那个最大公约数与每轮循环中那两个参数之间的最大公约数始终是相同的。也就是说：

gcd（a ₀ ，b ₀ ）=gcd（b ₀ ，r ₁ ）=gcd（r ₁ ，r ₂ ）=…=gcd（r _n-1 ，r _n ）

由于我们刚才已经证明该算法必然会终止，因此，对于终止之前的那一轮来说，r _n-1 除以r _n 的余数必定是0。由此可知，gcd（r _n-1 ，r _n ）等于gcd（r _n ，0），而根据gcd（x，0）=x这一规律，又可知gcd（r _n ，0）=rn，因此，gcd（r _n-1 ，r _n ）就等于r _n 。于是：

gcd（a ₀ ，b ₀ ）=…=gcd（r _n-1 ，r _n ）=gcd（r _n ，0）=r _n

这个r _n 正是算法最终所返回的值。由此可见，该算法能够根据初始的参数值计算出这两个数的最大公约数。 5BCZUY4jFAda+i5eu1Loc/V/lzZUK24Xvbf7tj0X2Pi4SC5q6fS9HCBEb6Yr2cgs