Question

用辗转相除法求最大公因数

928和174 2468和1692

Answer 1

辗转相除法原本是初等数论的内容，不过近年在中学数学里也有出现，是以算法初步的内容出现的，所以有必要简单介绍一下。并且我们在下一篇文章里，将结合菲波拉契数列导出辗转相除法的步数估计——拉梅定理。
　　辗转相除法又叫欧几里得算法，是欧几里得最先提出来的。不过这个名字有点不好，就如同在数学里说欧拉定理这个词一样，你不知道说的是哪个定理，因为欧拉发现的定理实在是太多……辗转相除法的实现，是基于下面的原理(在这里用(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称作辗转相除法里的步数。在明天，我们将利用辗转相除法的过程来导出此方法的步数估计——拉梅定理。

Answer 2

928÷174=5............58
174÷58=3
所以：928和174 的最大公约数为58

2468÷1692=1...........776
1692÷776=2...........140
776÷140=5.............76
140÷76=1........64
76÷64=1.......12
64÷12=5........4
12÷4=3
所以：2468和1692最大公约数为4

Answer 3

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

Answer 4

928/174=5.......58
174/58=3
故最大公约数为58

2468/1692=1......776
1692/776=2......140
776/140=5......76
140/76=1......64
76/64=1......12
64/12=5......4
12/4=3
故最大公约数为4