辗转相除法求最大公因数

辗转相除法求最大公因数

辗转相除法原本是初等数论的内容，不过近年在中学数学里也有出现，是以算法初步的内容出现的，所以有必要简单介绍一下。并且我们在下一篇文章里，将结合菲波拉契数列导出辗转相除法的步数估计——拉梅定理。

　　辗转相除法又叫欧几里得算法，是欧几里得最先提出来的。不过这个名字有点不好，就如同在数学里说欧拉定理这个词一样，你不知道说的是哪个定理，因为欧拉发现的定理实在是太多……辗转相除法的实现，是基于下面的原理(在这里用(a,b)表示a和b的最大公因数)：

　　(a,b)=(a,ka+b)，其中a、b、k都为自然数。………………①

　　也就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数，其公约数不变，比如(4,6)=(4+6,6)=(4,6+2×4)=2。要证明这个原理很容易：如果p是a和ka+b的公约数，p整除a，也能整除ka+b。那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的。

　　基于上面的原理，就能实现我们的迭代相减法：

　　(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2

　　基本上思路就是大数减去小数，一直减到能算出来为止，在作为练习的时候，往往进行到某一步就已经可以看出得值。迭代相减法简单，不过步数比较多，实际上我们可以看到，在上面的过程中，由(78,14)到(8,14)完全可以一步到位，因为(78,14)=(14×5+8,14)=(8,14)，由此就诞生出我们的辗转相除法。

　　用辗转相除法求(a,b).设r0=b，r1=a，反复运用除法算式，得到一系列整数qi，ri和下面的方程：

　　相当于每一步都运用原理①把数字进行缩小，上面右边就是每一步对应的缩小结果，可以看出，最后的余数rn就是a和b的公约数。我们以一个题为例说明基本过程。

　　例题：求(326,78)

　　所以(326,78)=2。这和我们用迭代相减法算出来的结果是一样的。所以中学的同学们应该看到，迭代相减法和辗转相除法在本质上是一样的，相对来说，减法比较简单，但是除法步数少。

　　我们要看到的是，在辗转相除法中，我们必须算到最后一步才知道rn是不是所求的最大公因数，所以我们把n称作辗转相除法里的步数。在明天，我们将利用辗转相除法的过程来导出此方法的步数估计——拉梅定理。

928÷174余58 174÷58整除 所以最大公因数是58 2468÷1692余776 1692÷776余140 776÷140=76 140÷76余64 76÷64余12 64÷12余4 12÷4整除 所以最大公因数是4