辗转相除法(辗转相除法的原理)

一、什么是辗转相除法

辗转相除法，又名欧几里德算法（Euclideanalgorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。另一种求两数的最大公约数的方法是更相减损法。

扩展资料：

辗转相除法是利用以下性质来确定两个正整数a和b的最大公约数的：

1、若r是a÷b的余数,则gcd(a,b)=gcd(b,r)

2、a和其倍数之最大公约数为a。

另一种写法是：

1、a÷b，令r为所得余数（0≤r<b），若r=0，算法结束；b即为答案。

2、互换：置a←b，b←r，并返回第一步。

二、什么叫做辗转相除法举几个例子

辗转相除法最大的用途就是用来求两个数的最大公约数。

用（a,b）来表示a和b的最大公约数。有定理：已知a,b,c为正整数，若a除以b余c，则（a,b）=(b,c)。（证明过程请参考其它资料）

例：求15750与27216的最大公约数。

解：

∵27216=15750×1+11466∴（15750，27216）=（15750，11466）

∵15750=11466×1+4284∴（15750，11466）=(11466,4284)

∵11466=4284×2+2898∴(11466,4284)=（4284，2898）

∵4284=2898×1+1386∴（4284，2898）=（2898，1386）

∵2898=1386×2+126∴（2898，1386）=（1386，126）

∵1386=126×11∴（1386，126）=126

所以（15750，27216）=216

辗转相除法比较适合用来求两个比较大的数的最大公约数。

三、辗转相减法和辗转相除法区别

辗转相减法和辗转相除法是两种用于求两个数的最大公约数的算法，它们在计算过程和原理上有所不同。

1.辗转相减法：

-辗转相减法是一种通过反复相减较大数与较小数的差来求最大公约数的方法。

-首先，从两个数中较大的数减去较小的数，得到一个新的差值。

-然后，将较小的数与新的差值比较，再次进行减法运算，得到一个新的差值。

-反复进行上述步骤，直到两个数相等或差值为0，此时的数即为最大公约数。

2.辗转相除法：

-辗转相除法是一种通过反复求两个数的余数来求最大公约数的方法。

-首先，用较大的数除以较小的数，得到一个余数。

-然后，将较小的数与余数比较，再次进行除法运算，得到一个新的余数。

-反复进行上述步骤，直到余数为0，此时的除数即为最大公约数。

总结来说，辗转相减法通过反复相减较大数与较小数的差来求最大公约数，而辗转相除法通过反复求两个数的余数来求最大公约数。这两种方法在计算过程和原理上有所不同，但都可以用于求解最大公约数。