高二算法初步| 用辗转相除法求得459和357的最大公因数是（）？

用辗转相除法求得459和357的最大公因数是（）？
答案是 51
这是怎么做出来的？
请写出详细过程及思路，谢谢~~

459/357，商=1，余数=102，没有整除，继续
357/102，商=3，余数=51，没有整除，继续
102/51，整除
所以459和357的最大公因数51

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