辗转相除是什么

辗转相除是什么

典型例题：
一.辗转相除法
例1 。求两个正数8251和6105的最大公因数。
（分析：辗转相除→余数为零→得到结果）
解：8251＝6105×1＋2146
显然8251与6105的最大公因数也必是2146的因数，同样6105与2146的公因数也必是8251的因数，所以8251与6105的最大公因数也是6105与2146的最大公因数。
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
则37为8251与6105的最大公因数。
以上我们求最大公因数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。
1． 为什么用这个算法能得到两个数的最大公因数？
利用辗转相除法求最大公因数的步骤如下：
第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；
第二步：若r0＝0，则n为m，n的最大公因数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；
第三步：若r1＝0，则r1为m，n的最大公因数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；
……
依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公因数

辗转相除是为了求两个数的公因数的，每次用两个数中大的数减去小的数，得到的余数代替大的数成为新的数，直到两数相等为止。举个例子： 14和49 辗转相除： (1)49-14=35 用35代替49，两数变为14和35 (2)35-14=21 用21代替35，两数变为14和21 (3)21-14=7 用7代替21，两数变为14和7 (4)14-7=7 用7代替14，两数变为7和7 两数相等为7，所以最大公约数是7.

辗转法相除：先将大数除以小数，如果整除，小数就是它们的最大公因数，如果不能整除，就记下余数，用前面的除数（就是小数），除以这个余数，以下类推，每一次都用前一个除式的除数除以自己的余数，直到有一个除法能整除，这时，最后能整除的除式的除数，就是这两个数的最大公因数。 如：437÷323＝1.....114 323÷114＝2......95 114÷95＝1......19 95÷19＝5 所以437和323的最大公因数是19 很好用，采纳吧。