笔记百科什么叫做辗转相除法？举几个例子？
辗转相除法，又名欧几里德算法（Euclideanalgorithm），是求最大公约数的一种方法。
它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。示例：123456和7890的最大公因数是6，这可由下列步骤（其中，“amodb”是指取a÷b的余数）看出：另一种求两数的最大公约数的方法是更相减损法。扩展资料：更相减损法与辗转相除法：
1、两者都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。
2、从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。
更相损减法在两数相差较大时，时间复杂度容易退化成O(N)，而辗转相除法可以稳定在O(logN)。
但辗转相除法需要试商，这就使得在某些情况下，使用更相损减法比使用辗转相除法更加简单。
而stein算法便由此出现。
延伸阅读
什么叫做辗转相除法？举几个例子？
辗转相除法最大的用途就是用来求两个数的最大公约数。
用（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
辗转相除法比较适合用来求两个比较大的数的最大公约数 。
辗转相除原理？
欧几里德算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
其计算原理依赖于下面的定理：
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)
证法一
a可以表示成a = kb + r（a，b，k，r皆为正整数，且r
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。
而r = a – kb，两边同时除以d，r/d=a/d-kb/d=m，由等式右边可知m为整数，因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数。
进而d|a.因此d也是a,b的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。
证法二
第一步：令c=gcd(a,b)，则设a=mc，b=nc
第二步：可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互素【否则，可设m-kn=xd,n=yd,(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)，得证
注意:两种方法是有区别的。
辗转相除法例题及解法？
比如，求2564与326的最大公约数。2564÷326商是7余数是282；326÷282商是1余数是44；282÷44商是6余数是8；44÷8商是5余数是4；8÷4=2余数是0，所以2564与326的最大公因数是2。辗转相除法就是除前两次除法外，每次都是用前面两次除法所得的余数作为被除数和除数。
辗转相除法的原理？
辗转相除法一般指欧几里得算法。欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。那么辗转相除法的原理是什么？
1、 原理：设两数为a、b(ab)，用gcd(a，b)表示a，b的最大公约数，r=a(mod b)为a除以b的余数，k为a除以b的商，即a÷b=k。。。。。。。r。辗转相除法即是要证明gcd(a，b)=gcd(b，r)。
2、 第一步：令c=gcd(a，b)，则设a=mc，b=nc。
3、 第二步：根据前提可知r=a-kb=mc-knc=(m-kn)c。
4、 第三步：根据第二步结果可知c也是r的因数。
5、 第四步：可以断定m-kn与n互质(假设m-kn=xd，n=yd(d1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cdc，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。
6、 从而可知gcd(b，r)=c，继而gcd(a，b)=gcd(b，r)。
7、 证毕。以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。
8、 解释：辗转相除法，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法，其可追溯至公元前300年前。
9、 来源：设两数为a、b(ab)，求a和b最大公约数(a，b)的步骤如下：用a除以b，得a÷b=q。。。。。。r1(0≤r1)。若r1=0，则(a，b)=b；若r1≠0，则再用b除以r1，得b÷r1=q。。。。。。r2(0≤r2）。若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，……如此下去，直到能整除为止。其最后一个余数为0的除数即为(a， b)的最大公约数。
10、 例如：a=25，b=15，a/b=1。。。。。.10，b/10=1。。。。。.5，10/5=2。。。。。。.0，最后一个余数为0d的除数就是5， 5就是所求最大公约数。
以上的就是关于辗转相除法的原理是什么的内容介绍了。
辗转相除法例子？
典型例题：
一.辗转相除法
例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即为所求的最大公因数。
辗转相除法步骤？
辗转相除法的算法步骤为,两个数中用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。得到最后的除数就是这两个数的最大公约数。
