辗转相除法口诀
先除以前面的后除以后面的
什么是辗转相除法
辗转相除法，又名欧几里德算法（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，并返回第一步。
辗转相除法算法步骤
欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《TheElements》中最早描述了这种算法,所以被命名为欧几里得算法。
扩展欧几里得算法可用于RSA加密等领域。
假如需要求1997和615两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997/615=3(余152)
615/152=4(余7)
152/7=21(余5)
7/5=1(余2)
5/2=2(余1)
2/1=2(余0)
至此，最大公约数为1
以除数和余数反复做除法运算，当余数为0时，取当前算式除数为最大公约数，所以就得出了1997和615的最大公约数1。
辗转相除法和短除法的区别
辗转相除法是单除法。而短除法是双除法。
