用辗转相除法求204与85的最大公约数，并用更相减损术检验．

辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数（第一余数）去除除数。再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。得到最后的除数就是这两个数的最大公约数。扩展资料：扩展欧几里得算法可用于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

要用辗转相除法求四个数的最大公约数，需要分三步:第一步，求第一个和第二个数的最大公约数；第二步，求前两个数的最大公约数与第三个数的最大公约数，这也是前三个数的最大公约数；第三步，求前三个数的最大公约数与第四个数的最大公约数，这也是四个数的最大公约数。后两步可以改为:第二步，求第三个和第四个数的最大公约数；第三步，求前两个数的最大公约数与后两个数的最大公约数的最大公约数。如求15、27、51、69的最大公约数。第一步，27÷15=1……1215÷12=1……312÷3=415和27的最大公约数是3。第二步，51÷3=17，51和3的最大公约数是3，所以，15、27、51的最大公约数是3。第三步，69÷3=23，69和3的最大公约数是3，所以，15、27、51、69的最大公约数是3。或者第二步，69÷51=1……1851÷18=2……1518÷15=1……315÷3=551和69的最大公约数是3。第三步，3和3的最大公约数是3，所以15、27、51、69的最大公约数是3。

通俗的说就是我除以你，你除以我，我再除以你，你再除以我。如此循环，直到你变成1,或者我变成1。。

辗转相除法求最大公因数的原理 一、辗转相除法可以求两个因数的最大公因数。（欧几里德算法） 1.我们可以用列举法、筛选法及短除法求得，如：6和9的最大公因数（6，9）=3 2.辗转相除法。 9÷6=1……3 6÷3=2 3就是9和6的最大公因数。 再如：30和80的最大公因数。 80÷30=2……20 30÷20=1……10 20÷10=2 10就是30和80的最大公因数。 辗转相除法优点是可以求出两个大数的最大公因数 二、辗转相除法求最大公因数的原理 如果我们要求8251与6105的最大公因数的话，假设8251是这个数x的a倍，再假设6105是x的b倍，那么2146=8251-6105，是x的(a-b)倍，也是x的倍数，而无论这几个数如何加减，甚至相乘，都还是最大公约数的倍数，我们就可以把求8251与6105的最大公约数简化成求2146和6105的最大公约数，再把求2146与6105的最大公约数简化为求3959(=6105-2146)与2146的最大公约数，如此相减往复几次后，会发现两个数变相等了37=37，这个数就是两个原来数的最大公因数。  举个例子9和69-6=3，保留6,36-3=3，保留3,3发现两数相等，为3所以最大公因数为3 9和6的最大公因数，我们知道是3。9是3的倍数，6是3的倍数，那3也一定是3的倍数。 30和80的公因数为m，30是m的倍数，80是m的倍数。80里有的两个30也肯定是m的倍数，剩下的20也会是m倍数。10也会是m的倍数。10=10=m。

设多项式f(x),g(x)满足f(x)=g(x)h(x)+r(x),其中h(x),r(x)也是多项式，r(x)的次数小于g(x)的次数，大于0。以g(x),r(x)代替f(x),g(x),重复上述过程：g(x)=r(x)h1(x)+r1(x)。辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。另一种求两数的最大公约数的方法是更相减损法。

辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因数的算法。它是已知最古老的算法， 其可追溯至公元前300年前。 辗转相除法求两个数的最大公约数的步骤如下： 先用小的一个数除大的一个数,得第一个余数； 再用第一个余数除小的一个数,得第二个余数； 又用第二个余数除第一个余数,得第三个余数； 这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数） 要知道是怎了来的很简单！分析如下： A÷B=C……D B÷D=F（余数为零） 则A、B的公因数就是D 反过来推就很容易了： B=DxF，A=BxC+D 将B=DxF代入， A=DxFxC+D=D（FxC+1） A和B的最大公因数就是D例1：求6731和2809的最大公约数？ 6731÷2809=2……1113 2809÷1113=2……583 1113÷583=1……530 583÷530=1……53 530÷53=10（整除无余数） 6731和2809的最大公约数就是53例2：求6555和2530的最大公约数？ 肉眼可见两数都能被5整除，先把5除了再说 分别除1311得到和506，辗转相除的步骤和难度就降低了 1311÷506=2……299 506÷299=1……207 299÷207=1……92 207÷92=2……23 92÷23=4（整除无余数） 6555和2530的最大公约数是5×23=115

可以用a，b相除将b赋值给a将余数赋值给b若b为0，则a为最大公约数。在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。公约数，亦称“公因数”。它是一个能被若干个整数同时均整除的整数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”，公约数中最大的称为最大公约数。对任意的若干个正整数，1总是它们的公因数。

这是相关的一些知识点辗转相除法求最大公约数的方法：用所得的剩余除去除数，直至最终的剩余为0。辗转相除法求最大公约数的方法：先用小的数除大的数，得余数。再用所得的余数除小的数，得第二个余数。然后用第二个余数除第一个余数，得到第三余数，如此依次用后一位数除去前面的余数，直至其为0。最后一个除数就是所求的最大公约数。2.欧几里德算法也被称为翻转相除，它是用来求出两个非负数的最大公约数。它的应用范围包括数学和电脑。计算公式 gcd (a, b)= gcd (b, a modb).3.在数学上，辗转相除法是一种求解最大公约数的方法。它的算法步骤如下：a、 b相除；向 a分配 b;向 b分配剩余；如果 b是0, a是最大的，否则，步骤1-3直到 b是0为止。

解答：124：4；2；31；1；124；62 88：1；2；44；4；22；8；11；88 可见：最大公约数是4

以h(x)为f(x)和g(x)的最大公因式则h(x)|f(x),h(x)|g(x)为例子来讲解具体的求解方法：因为h(x)|[f(x)u(x)+g(x)v(x)]；又 f(x)u(x)+g(x)v(x)=d(x)；h(x)|d(x) ①；d(x)|f(x),d(x)|g(x)；所以d(x)是f(x)、g(x)的公因式；d(x)|h(x) ②；由①②得d(x)=c·h(x) 为f(x)和g(x)的最大公因式,这里c为常数。扩展资料：假设c = gcd(a,b),则存在m,n，使a = mc, b = nc;令r = a mod b，即存在k，使r = a-kb = mc - knc = (m-kn)c;故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)*c;假设d = gcd(n,m-kn), 则存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc;由于gcd(a,b) = c, 故d = 1;即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;故得证gcd(a,b) = gcd(b,a mod b)。

无论怎样除，若有一个数是被除数和除数的公约数，则余数一定也含有这个公约数。（被除数≥除数）

辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。例如求1515和600的最大公约数，第一次：用600除1515，商2余315；第二次：用315除600，商1余285；第三次：用285除315，商1余30；第四次：用30除285，商9余15；第五次：用15除30，商2余0。1515和600的最大公约数是15。辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数。

在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法.辗转相除法首次出现于欧几里得的《几何原本》（第VII卷,命题i和ii）中,而在中国则可以追溯至东汉出现的《九章算术》.两个整数的最大公约数是能够同时整除它们的最大的正整数.辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数.例如,252和105的最大公约数是21（252=21×12；105=21×5）；因为252−105=147,所以147和105的最大公约数也是21.在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零.这时,所剩下的还没有变成零的数就是两数的最大公约数.由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21=5×105+(−2)×252.这个重要的等式叫做贝祖等式.辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年）,所以它是现在仍在使用的算法中最早出现的.这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式.自此,现代抽象代数概念如欧几里得整环开始出现.后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式.辗转相除法有很多应用,它甚至可以用来生成全世界不同文化中的传统音乐节奏.在现代密码学方面,它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分.它还被用来解丢番图方程,寻找满足中国剩余定理的数,或者求有限域的倒数.辗转相除法还可以用来构造连分数,在施图姆定理和一些整数分解算法中也有应用.辗转相除法是现代数论中的基本工具.辗转相除法处理大数时非常高效,它需要的步骤不会超过较小数的位数（十进制下）的五倍.加百利·拉梅(GabrielLamé)于1844年证明了这点,开创了计算复杂性理论.

928/174=5.......58174/58=3故最大公约数为582468/1692=1......7761692/776=2......140776/140=5......76140/76=1......6476/64=1......1264/12=5......412/4=3故最大公约数为4

r＝m;m＝n;n＝r;m%n

m=7560 n=2700 r=2160m=2700 n=2160 r=540m=2160 n=540 r=0所以2700和7560最大公约数是540然后在还用540和3960求最大公约数m=3960 n=540 r=180m=540 n=180 r=0所以3个数最大公约数是180

1）324=243+81 　　243=81*3 　　其最大公约数是81, 　　所以324和243的最小公倍数是 　　243*324/81=972 2）972=135*7+27 　　135=27*5 　　972与135的最大公约数是27. 　　所以324和243的最小公倍数是 　　972*135/27=4 860 故三个数324,243,135的最小公倍数是 4860 .

还是我来吧。如果两个数有最大公约数A，那么这两个数，以及这两个数的差，还有大数除以小数的余数，必然都是A的倍数。所以当最后两个数刚好能整除时，较小的数就是最大公约数。

根据辗转相除法,我们可以先求出与的最大公约数为,再利用辗转相除法,我们可以求出与的最大公约数为,进而得到答案. 解:则与的最大公约数为又则与的最大公约数为所以,三个数,,的最大公约数为. 本题考查的知识点是辗转相除法与更相减损术,求三个或三个以上数的最大公约数,可以先求前两个数的最大公约数,再求所得最大公约数与第三个数的最大公约数,最后得到答案.

324-243=81243-81=162162-81=81∴324与243的最大公约数是81135-81=5481-54=2754-27=27∴81与135的最大公约数是27即324，243，135的最大公约数是27

不妨假设：a、b（a>=b>0）的最大公约数为c。引理：令t为 a 除以 b 的余数（t不为零），则b与t的的最大公约数也为c。引理的证明比较简单，简单讲一下。证明：由题设a、b可以写成：a=k1*c，b=k2*c；其中k1、k2为正整数。t为a 除以b 的余数（t不为零），于是a=kb+t，其中k为正整数。t = a - kb = k1*c - k*k2*c，所以t也是c的倍数。引理得证。由引理，我们就有了辗转相除法。在求a、b（a>=b>0）的最大公约数时，我们可以先求得a÷b的余数t，再求t与b的最大公约数，结果是一样的。在求b与t（显然b>t）的最大公约数时，我们还可以用同样的方法继续通过求余来求。直到当a÷b的余数为0时，显然它们的最大公约数为b。这时计算就完了。这就是辗转相除法。

辗转相除法：319=261×1+58261=58×4+2958=29×2∴319与261的最大分约数是29．更相减损术：319-261=58261-58=203203-58=145145-58=8787-58=2958-29=29∴319与261的最大分约数是29．

6731/2809=2---1113 2809/1113=2---583 1113/583=1---530 583/530=1---53 530/53=10---0 最大公约数就是53.

0分？？。。2个2个求咯

例如求325，130，270三个数的最大公约数.因为325=130×2+65，130=65×2，所以325与130的最大公约数是65.因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5.故325，130，270三个数的最大公约数是5.

可以.先求出两个数A、B的最大公约数M,再求出M和C的最大公约数N即为A,B,C三数的最大公约数. 原理：N是A,B,C的最大公约数==>N的因数是A,B,C因数的交集 M是A,B的最大公约数====>M的因数是A,B因数的交集 （M的因数是A,B因数的交集）与（C的因数）的交集就是是A,B,C因数的交集

从新编制

算法：为了求x和y的最大公约数（假设x大于y）,先计算x除以y的余数M1,M1如果为0,则y为最大公约数；如果不为0则计算y除以 M1,一直计算下去直到余数为0,这是除数Mn为最大公约数.（1）168%72=24；72%24=0；所以24为最大...

8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 333=148×2+37 148=37×4 所以8251与6105的最大公约数就是37．

辗转相除法用来求两个整数的最大公约数，而不是求多项式的因式。

例如求325,130,270三个数的最大公约数. 因为325=130×2+65,130=65×2,所以325与130的最大公约数是65. 因为270=65×4+10,65=10×6+5,10=5×2,所以65与270最大公约数是5. 故325,130,270三个数的最大公约数是5.

可以用f（x）导入那个数字。导数用辗转相除法，如果最后rn=0，那rn-1为常数，则无重因式，反之则有。欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。

8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 333=148×2+37 148=37×4 所以8251与6105的最大公约数就是37．

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252=21×12；105=21×5）；因为252−105=147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21=5×105+(−2)×252。这个重要的等式叫做贝祖等式。辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数，但在19世纪，辗转相除法被推广至其他类型的数，如高斯整数和一元多项式。自此，现代抽象代数概念如欧几里得整环开始出现。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，寻找满足中国剩余定理的数，或者求有限域的倒数。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。辗转相除法处理大数时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。加百利·拉梅(GabrielLamé)于1844年证明了这点，开创了计算复杂性理论。

就是连续不断的除，竖式除法

典型例题：一.辗转相除法例1 。求两个正数8251和6105的最大公因数。（分析：辗转相除→余数为零→得到结果）解：8251＝6105×1＋2146显然8251与6105的最大公因数也必是2146的因数，同样6105与2146的公因数也必是8251的因数，所以8251与6105的最大公因数也是6105与2146的最大公因数。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝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即为所求的最大公因数。

你有钻研的精神,加上严谨的治学态度,又精通数学领域的乘除加减,并能灵活运用小数点,更兼前后逻辑分明,汉语文化水平高超,且分析推断有理,让人欲辩难言,你在百度知道,也算屈才了

设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq......r1(0≤r)。若r1=0，则(a，b)＝b；若r1≠0，则再用r1除b，得b＝r1q......r2(0≤r2).若r2＝0，则(a，b)＝r1，若r2≠0，则继续用r2除r1,……如此下去，直到能整除为止。其最后一个非零余数即为..原理及其详细证明在介绍这个方法之前，先说明整除性的一些特点（下文的所有数都是正整数，不再重覆），我们可以这样给出整除性的定义：对于二个自然数a和b，若存在正整数q，使a=bq，则a能被b整除，b为a的因子，a为b的倍数。如果a能被c整除，并且b也能被c整除，则c为a、b的公因数（公有因数）。由此我们可以得出以下推论：推论1、如果a能被b整除（a=qb），若k为正整数，则ka也能被b整除（ka=kqb）推论2、如果a能被c整除（a=hc），b也能被c整除（b=tc），则(a±b)也能被c整除因为：将二式相加：a+b=hc+tc=(h+t)c同理二式相减：a－b=hc－tc=(h－t)c所以：(a±b)也能被c整除推论3、如果a能被b整除（a=qb），b也能被a整除（b=ta），则a=b因为：a=qbb=taa=qtaqt=1因为q、t均为正整数，所以t=q=1所以：a=b辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:如果q和r是m除以n的商及余数，即m=nq+r，则gcd(m,n)=gcd(n,r)。证明是这样的:设a=gcd(m,n)，b=gcd(n,r)证明：∵a为m,n的最大公约数，∴m能被a整除，且n也能被a整除，∴由推论1得：qn也能被a整除，∴由推论2得：m-qn也能被a整除，又∵m-qn=r，∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）∵b为n和r的最大公约数，a为n和r的公约数∴a≤b，同理∵b为n,r的最大公约数，∴n能被b整除，且r也能被b整除，∴由推论1得：qn也能被b整除，∴由推论2得：qn+r也能被b整除，又∵m=qn+r，∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）∵a为m,n的最大公约数，b为m和n的公约数，∴b≤a，由以上可知：a≤b与b≤a同时成立，故可得a=b，证毕。例如计算gcd(546,429)gcd(546,429)546=1*429+117=gcd(429,117)429=3*117+78=gcd(117,78)117=1*78+39=gcd(78,39)78=2*39=39

1890=4*462+42462=11*42因此最大公约数为42

辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。例如求1515和600的最大公约数，第一次：用600除1515，商2余315；第二次：用315除600，商1余285；第三次：用285除315，商1余30；第四次：用30除285，商9余15；第五次：用15除30，商2余0。1515和600的最大公约数是15。辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数。

辗转相除法又叫欧几里得算法,是欧几里得最先提出来的.不过这个名字有点不好,就如同在数学里说欧拉定理这个词一样,你不知道说的是哪个定理,因为欧拉发现的定理实在是太多……辗转相除法的实现,是基于下面的原理(在这里用(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称作辗转相除法里的步数.

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

需要计算3次：第一次：462对126求余，结果是84第二次：126对84求余，结果是42第三次：84对42求余，结果是0，计算结束。结果：两者的最大公约数是42.

928÷174余58 174÷58整除 所以最大公因数是58 2468÷1692余776 1692÷776余140 776÷140=76 140÷76余64 76÷64余12 64÷12余4 12÷4整除 所以最大公因数是4

1.首先我们要了解“同余”的概念 设整数a,b,n(n≠0)，如果a-b是n的整数倍（正的或负的），我们就说“a与b模n同余”，记做a≡b(mod n)。有时，b被叫做a模n的余数。 另一种描述：如果a与b的差能被n整除，就说a≡b(mod n)，即存在非零整数k，使得a=b+nk。2.乘法逆元素的一般提法 寻找一个x，使得1=(a×x)(mod n) 写成另一种形式，即 a^-1≡x(mod n) 解决乘法逆元素很困难，有时候有一个方案，有时候没有。例如2模14的乘法逆元素就不存在，5模14的乘法逆元素是3。3.扩展的欧几里得算法 由欧几里德算法可以得到下面的重要结论 设a和b是两个正整数（至少有一个非零），d=gcd(a,b)，则存在整数x和y使得ax+by=d成立，如果a和b都是素数，那么存在整数x和y使得ax+by=1成立。此时可以求出ax≡1(mod b)中的x（称x是a的模b逆）。4.用辗转相除法求逆元的实例： 求（26，9），并找出使26s+9t=1成立的整数s、t。 解：设a=26，b=9 26=9×2+8        r0=8 9=8×1+1          r1=1 8=1×8+0          r2=0 则有（26，9）=1 由上述结果可得：r0=a-2b r1= b-r0=b-(a-2b)= 3b-a=1 3×9-26=1 S=-1;t=3 则-1是26的模9逆

辗转相除法求两个整数的最大公约数的步骤：一、用一个数除以另一个数，列出第一个算式。注意第一步最好用较大的数除以较小的数；二、接下来，用上一个算式的除数除以余数；三、反复做第二步，直到余数为0为止；四、最后一个算式的除数，就是两个数的最大公约数。举例如下：求3854与216的最大公约数：3854÷216=17……182216÷182=1……34182÷34=5……1234÷12=2……1012÷10=1……210÷2=5……0得：3854与216的最大公约数是2。

分解质因数法：360=2x2x2x3x3x5, 204=2x2x3x17,（360,204）=2x2x3=12.辗转相除法：360÷204=1……156， 204÷156=1……48， 156÷48=3……12， 48÷12=4。【360,204】=360x204÷12=6120。

老师就教过俩数的没教过3数的567=405*1+162405=162*2+81162=81*2+0下面得就不会了`

27216=15750×1+11466 15750=11466×1+4284 11466=4284×2+2898 4284=2898×1+1386 2898=1386×2+126 1386=126×11 由以上步骤可知,15750和27216的最大公约数为126