求两个正整数的最大公约数的辗转相除法算理

求两个数的最大公约数
——辗转相除法
已知两个数a和b，求他们的最大公约数。

解：若a>b,则用a除以b，得其余数t1;
再用b除以t1，得其余数t2；
再用t1除以t2，得其余数t3；
再用t2除以t3，得其余数t4；
…………
再用t n−1除以t n，得其余数t n+1；
最后t n除以t n+1，得其余数0；
按照上述运算，余数为0时停止，最后一个非零余数t n+1就是两个数的最大公约数。

若a<b，道理相同。

下面我们再来证明辗转相除法：
由上面的阐述我们可以得到，辗转相除法的证明可以转化为证明两个数的最大公约数等于这两个数中的较小者和两个数商的余数的最大公约数。

假设a>b,a除以b的商是t，余数是s，故只需证a和b的最大公约数等于b和s的最大公约数即可；
a=tb+s ①
设a和b的最大公约数是k,则a、b可以表示为：
a=km ②
b=kn ③
因k为最大公约数，故m和n互质
由①②③可得：
s=a-tb=km-ktn=k(m-tn) ④
所以k是b和s的一个公约数，接下来只需要证明n和m-tn互质，就可以证明k是b和s的最大公约数；
这里我们用反证法，假设n和m-tn存在最大公约数w（w>1）,则n 和m-tn可表示为：
n=wA ⑤
m-tn=wB ⑥
A和B互质；
由⑤⑥可得：
m=wB+tn=wB+twA=w(B+tA)
n=wA
m和n存在公约数w，这和m、n互质矛盾，所以假设不成立，所以n和m-tn互质。

所以k也是b和s的最大公约数。

故a和b的最大公约数等于b和s的最大公约数，此方法得证。

《算法案例-辗转相除法与更相减损术》(一)算法案例-辗转相除法与更相减损术算法，是指在确定性有限时间内，解决特定问题的一系列清晰指令。

辗转相除法和更相减损术，均为求解最大公约数问题的算法。

下面将分别介绍这两种算法的基本思想和实现方式。

一、辗转相除法辗转相除法，也叫欧几里得算法，是求两个正整数的最大公约数的一种方法。

其基本思想是：设两个正整数为 a 和 b （a > b），如果a%b = 0，则 b 即为两数的最大公约数；否则，a 和 b 的最大公约数就是 b 和 a%b 的最大公约数，即 gcd(a,b) = gcd(b,a%b)。

这一思想可以用代码实现：```int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}```辗转相除法的优点在于其计算量比较小，并且只用到了简单的加减操作，适用于大数据处理的场景。

同时，其时间复杂度为 O(log a + log b)，在实际使用中速度较快。

二、更相减损术更相减损术，也是用于求两个正整数的最大公约数的一种方法。

其基本思想是：设两个正整数为 a 和 b （a > b），则 a-b 可以得到一个差值，而这个差值与 b 的最大公约数，也是 a 和 b 的最大公约数。

但是，由于上面的操作导致了数字的不停减少，如果两个数字差距较大，会导致较长的计算时间且容易出现递归调用栈溢出。

因此，更相减损术需要进行优化。

这时，我们可以使用辗转相除法来缩小数字差距。

当 a 和 b 中有一个数大于等于另一个数的两倍时，我们可以使用辗转相除法把两个数尽可能的靠近，再进行更相减损术的操作。

更相减损术的代码实现如下：```int gcd(int a, int b){if (a == b) return a;if (a < b) return gcd(b, a);if ((a & 1) == 0 && (b & 1) == 0) return gcd(a >> 1, b >> 1) << 1;else if ((a & 1) == 0) return gcd(a >> 1, b);else if ((b & 1) == 0) return gcd(a, b >> 1);else return gcd(b, a - b);}```三、总结辗转相除法和更相减损术，都是基于整除法和减法的扩展，通过不停地迭代缩小数字大小，最终得到两个数字的最大公约数。

注：q(i），r(i），括号中的是下标，lcm是求最小公倍数
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。
证毕。
编辑本段
算法
自然语言描述
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余数，则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
scanf(&quot;%u%u&quot;,&amp;m,&amp;n);
printf(&quot;%u与%u的最大公约数为：%u\n&quot;,m,n,gcd ( m,n ) );
return 0;
}
/* 功能：返回正整数m和n的最大公约数*/
unsigned gcd ( unsigned m,unsigned n )
else
return a；
}
C语言实现
/*题目：输入两个正整数，求其最大公约数。*/
#include &lt;stdio.h&gt;
unsigned gcd ( unsigned,unsigned ) ;
int main( void )
{
unsigned m,n;
printf(&quot;请输入两个正整数：&quot;);
辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数，但在19世纪，辗转相除法被推广至其他类型的数，如高斯整数和一元多项式。自此，现代抽象代数概念如欧几里得整环开始出现。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。

辗转相除法‎求最大公约‎数和最小公‎倍数1: /*辗转相除法‎基于如下原‎理：两个整数的‎最大公约数‎等于其中较‎小的数和两‎数的差的最‎大公约数。

2: 例如，252和1‎05的最大‎公约数是2‎1（252 = 21 ×12；105 = 21 ×5）；3: 因为252‎? 105 = 147，所以147‎和105的‎最大公约数‎也是21。

在这个过程‎中，较大的数缩‎4: 小了，所以继续进‎行同样的计‎算可以不断‎缩小这两个‎数直至其中‎一个变成零‎。

这时，所剩下的5: 还没有变成‎零的数就是‎两数的最大‎公约数。

6: */7: #inclu‎d e <stdio‎.h>8:9: int getGC‎D AndL‎C M(int a,int b){10: int max=a>b?a:b;//将较大的数‎赋给max‎11: int min=(max=a)?b:a;//将较小的数‎赋给min‎12: int temp;//暂时存储变‎量13: while‎(max!=0){14: temp=min%max;15: min=max;16: max=temp;17: }18: print‎f("最大公约数‎为%d\n",min);19: print‎f("最小公倍数‎为%d\n",a*b/min);20: }21:22: int main(){23: print‎f("输入两个数‎整数值\n");24: int a,b;25: scanf‎("%d",&a);26: scanf‎("%d",&b);27: getGC‎D AndL‎C M(a,b);28: retur‎n0;29: }C语言水仙‎花数算法打印出所有‎的“水仙花数”，所谓“水仙花数”是指一个三‎位数，其各位数字‎立方和等于‎该数本身。

求最大公约数辗转相除法最大公约数是数学中一个重要的概念，又称最大公因数。

它是两个或多个整数中最大的能被这些整数整除的整数，它也是整除这些数的所有自然数中最大者。

最大公约数辗转相除法（Euclidean algorithm）是计算最大公约数最有效的方法之一。

本文将详细介绍最大公约数辗转相除法的原理和计算步骤。

一、原理最大公约数辗转相除法是古希腊数学家厄拉多塞（Euclid）发现的，是一种减法运算的数学方法，以此可以求出两个或多个整数的最大公约数。

该法的基本思想是：给定任意两个正整数a和b（a>b），求它们的最大公约数，先取倍数较大的数a和较小的数b做相减，即a-b，若差值d=a-b不等于零，则把a,b赋值为最初的a,d，再重复上述减法运算，直到减法运算的差值d=0，此时最大公约数即为a和b的最初除数。

二、步骤最大公约数辗转相除法的计算步骤如下：（1）确定a和b的值，其中a>b；（2）求a与b的差d=a-b；（3）将a,b赋值为a,d；（4）重复上述第二步和第三步的运算，直到d=0，此时最大公约数即为a和b的最初除数。

例：求最大公约数36和24，如下：（1）确定a和b的值，其中a>b：a=36，b=24（2）求a与b的差d=a-b：d=36-24=12（3）将a,b赋值为a,d：a=36，b=12（4）重复上述第二步和第三步的运算，直到d=0，此时最大公约数即为a和b的最初除数：d=36-12=24a=36，b=24d=36-24=12a=36，b=12d=36-12=24a=36，b=24d=36-24=12a=36，b=12d=36-12=24d=0最大公约数则为12.三、应用最大公约数辗转相除法在数学中有着广泛的应用，是有效求解问题的重要方法。

它不仅可以求解最大公约数，还可以求解最小公倍数、判断两数是否互素（即两数的最大公约数为1）、判断三数是否公倍数关系（即两数的最大公约数等于另一数）等。

c++辗转相除法求最大公约数和最小公倍数介绍：欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。

应用领域有数学和计算机两个方面。

计算公式gcd(a,b) =gcd(b,a mod b)。

算法简介：欧几里德算法是用来求两个正整数最大公约数的算法。

是由古希腊数学家欧几里德在其著作《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。

cpp代码实现#include<iostream>using namespace std;int GCD(int a, int b){int c;while (b > 0){c = a % b;a = b;b = c;}return a;}int LCM(int a,int b){int c;c = a * b / GCD(a, b);return c;}int main(){int x, y;cin >> x >> y;cout << "x和y的最大公约数为：" << GCD(x, y) << endl;cout << "x和y的最小公倍数为：" << LCM(x, y) << endl;return 0;}。

辗除法辗除法（zhǎnchúfǎ）——辗转相除法，又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。

它是已知最古老的算法，其可追溯至3000年前。

它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

它并不需要把二数作质因子分解。

证明：设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a=bq......r 1(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)。

[编辑] 算法辗转相除法是利用以下性质来确定两个正整数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，并返回第一步。

[编辑] 虚拟码这个算法可以用递归写成如下:functiongcd(a, b) {if b<>0returngcd(b, a mod b);elsereturn a;}或纯使用循环:functiongcd(a, b) {define r as integer;while b ≠ 0 {r := a mod b;a := b;b := r;}return a;}pascal代码（递归）求两数的最大公约数functiongcd(a,b:integer):integer;beginif b=0 then gcd:=aelsegcd:=gcd (b,a mod b);end ;其中“a mod b”是指取a ÷ b 的余数。

利用递归求两个数的最大公约数(利用辗转相除法)最大公约数，也叫做最大公因数，是指两个或多个整数共有的约数中最大的一个。

求两个数的最大公约数可以使用递归方法，特别是采用辗转相除法。

所谓辗转相除法，是指通过不断地用较小的数去除较大的数，然后再用除数去除余数，直到最后余数为0为止。

最后一个不为0的除数即为最大公约数。

下面我们就来看一个具体的例子，以便更好地理解递归求解最大公约数的方法。

假设我们要求解的两个数是36和48。

首先，我们使用48去除36，得到余数为12。

然后，将36作为新的被除数，余数12作为新的除数，再进行一次相除操作。

我们用36去除12，得到余数0。

此时，我们得到的不为0的除数12就是最大公约数。

我们可以使用递归方法来实现这个过程。

首先，设定递归函数gcd(a, b)表示求解a和b的最大公约数。

如果b等于0，那么gcd(a, b)就等于a；如果b不等于0，那么gcd(a, b)等于gcd(b, a%b)。

这样，我们就可以利用递归不断地缩小问题规模，直到规模最小为止。

接下来，我们将上述方法转化为函数的形式，方便我们进行编程实现。

```pythondef gcd(a, b):if b == 0:return aelse:return gcd(b, a % b)```在调用这个函数时，我们只需要传入要求解的两个数即可。

```pythonresult = gcd(36, 48)print("36和48的最大公约数为：" + str(result))```通过以上步骤，我们成功地求解出了36和48的最大公约数，即12。

这个方法不仅仅适用于36和48，对于任意两个正整数，我们都可以采用相同的方法求解它们的最大公约数。

在实际应用中，求解最大公约数经常用于简化分数、约分、化简等操作。

比如，在算术题中，我们需要将一个分数化简为最简形式，就需要求解其分子和分母的最大公约数，然后将分子和分母都除以这个最大公约数，得到最简形式的分数。

辗转相除法原理辗转相除法，又称为欧几里得算法，是一种用来求两个正整数的最大公约数的方法。

它的原理简单易懂，而且在实际应用中具有很高的效率和准确性。

本文将详细介绍辗转相除法的原理及其应用。

辗转相除法的原理是基于以下定理，两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

设两个正整数为a和b（a>b），则它们的最大公约数记为gcd(a, b)。

根据上述定理，可以得出以下递推关系式，gcd(a, b) = gcd(b, a mod b)，其中“a mod b”表示a除以b的余数。

具体来说，辗转相除法的步骤如下，首先将a除以b，得到商q和余数r，即a = b q + r。

然后将b赋值给a，将r赋值给b，继续进行相同的除法运算，直到余数为0为止。

此时，b即为最大公约数gcd(a, b)。

辗转相除法的优点在于它的迭代过程非常简单，而且每一步都能够有效地减小问题的规模。

因此，即使对于非常大的整数，辗转相除法也能够在较短的时间内得到最大公约数。

辗转相除法不仅可以用来求两个整数的最大公约数，还可以推广到求多个整数的最大公约数。

具体做法是先求出前两个数的最大公约数，然后再将这个最大公约数与第三个数求最大公约数，以此类推，直到所有的数都求出最大公约数为止。

在实际应用中，辗转相除法被广泛地应用于数论、密码学、计算机算法等领域。

例如，在RSA公钥加密算法中，需要大素数的乘积，而辗转相除法可以用来验证两个大素数是否互质。

又如，在计算机程序设计中，辗转相除法可以用来简化分数的运算，求解线性同余方程等。

总之，辗转相除法作为一种简单而有效的求最大公约数的方法，具有广泛的应用前景。

它的原理简单易懂，而且在实际应用中具有很高的效率和准确性。

希望本文对辗转相除法的原理及其应用有所帮助。

辗转相除法例题
辗转相除法，也称为欧几里德算法，是求两个正整数的最大公约数的一种常用方法。

它的基本原理是通过反复用较小数除较大数，并用余数替换较大数，直到余数为0为止。

最后的除数即为两个数的最大公约数。

下面给出一个辗转相除法的例题：
例题：求出60和48的最大公约数。

解析：按照辗转相除法的步骤，我们先用60除以48，并得到商1余12。

然后用48除以12，得到商4余0。

余数为0，说明此时的除数12即为60和48的最大公约数。

拓展：
辗转相除法除了可以求两个正整数的最大公约数，还可以用于求解一些其他问题。

例如，我们可以利用辗转相除法来判断两个正整数是否互质。

如果两个正整数的最大公约数为1，那么我们称这两个数为互质数。

互质数的特点是除了1以外没有其他公约数。

我们可以通过辗转相除
法来判断两个数是否互质。

例如，我们要判断12和35是否互质，首先用35除以12，得到商2余11。

然后用12除以11，得到商1余1。

最后用11除以1，得到商11余0。

由于最后余数为0，所以12和35的最大公约数为1，即它们是互质数。

辗转相除法的应用还可以扩展到更复杂的问题，比如求解线性同余方程、计算模逆元等。

它在数论和密码学中有着广泛的应用。

总之，辗转相除法是求解最大公约数的一种简单有效的方法。

它的应用范围广泛，不仅仅局限于求两个正整数的最大公约数，而且可以应用于更复杂的数学问题中。

使用辗转相除法求最大公约数
最大公约数是指两个或多个数共同拥有的最大因数，也就是能够同时整除这些数的最大正整数。

而求最大公约数的一种常用方法就是辗转相除法。

辗转相除法的基本思路是，在两个整数 a 和 b 中，将较大的那个数除以较小的那个数，然后用余数替换较大的数，再继续进行除法运算，直到余数为零。

此时，较小的数就是这两个数的最大公约数。

以求 30 和 45 的最大公约数为例，具体步骤如下：
1. 用 45 除以 30，得到商 1 和余数 15。

2. 用 30 除以 15，得到商 2 和余数 0。

3. 因为余数为零，所以最大公约数为 15。

辗转相除法求最大公约数的优点在于，它的计算速度比较快，而且不需要列出所有的因数。

但是，它的缺点是可能需要多次除法运算，特别是当两个数较大时，计算量会比较大。

总之，辗转相除法是求最大公约数的一种有效方法，它可以用于解决许多数学和计算问题。

- 1 -。

接下来是在网上看到求两个数的最大公约数的方法：
用辗转相除法求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是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 先比较大小假设比较出较小的数b 然后 for i:=b downto 1 do
if(a mod i=0) and (b omd i=0)
then begin
write(i);readln;
halt;
end;。

辗转相除法例题及解析
辗转相除法，也叫作欧几里德算法，是一种用于求两个正整数的最大公约数的算法。

下面我们来看一个辗转相除法的例题及解析。

例题：求246和198的最大公约数。

解析：首先，我们用246除以198，得到商为1，余数为48（246 = 198 * 1 + 48）。

接下来，我们用198除以48，得到商为4，余数为6（198 = 48 * 4 + 6）。

再次，我们用48除以6，得到商为8，余数为0（48 = 6 * 8 + 0）。

因为最后的余数为0，所以我们可以得出结论，246和198的最大公约数为6。

解析过程中，我们不断用较小的数去除较大的数，再用得到的余数去除上一轮的除数，重复这个过程，直到余数为0。

此时，最后一次的除数就是最大公约数。

通过辗转相除法，我们可以高效地求出两个数的最大公约数，理解原理和掌握使用方法能够帮助我们在解决实际问题中快速得到结果。

利用辗转相除法求最大公约数1. 引言最大公约数（Greatest Common Divisor，简称GCD）是指两个或多个整数共有的约数中最大的一个。

求最大公约数是数学中常见的问题，解决这个问题的方法有很多种。

其中一种常用且高效的方法就是辗转相除法。

辗转相除法，又称欧几里德算法，是古希腊数学家欧几里德提出的一种快速求解两个整数最大公约数的方法。

这种方法基于一个简单而重要的原理：两个正整数a和b（a > b）的最大公约数等于b和a%b（a除以b所得余数）的最大公约数。

本文将详细介绍辗转相除法求最大公约数的原理、步骤和实现过程，并给出相关代码示例。

2. 辗转相除法原理设两个正整数a和b（a > b），它们的最大公约数为d。

根据辗转相除法原理，我们可以得到以下结论：•如果b能够整除a，则d = b；•如果b不能整除a，则d等于b和a%b（即a除以b所得余数）的最大公约数。

通过不断将余数作为除数，上一步的除数作为被除数，重复这个过程，直到余数等于0为止，此时的被除数就是最大公约数。

3. 辗转相除法步骤辗转相除法的求解步骤如下：1.输入两个正整数a和b（a > b）；2.计算a%b的值，并将结果赋给r（即r = a%b）；3.若r等于0，则b即为最大公约数；4.若r不等于0，则将b的值赋给a，将r的值赋给b，返回第2步继续执行。

通过以上步骤，不断循环直到余数等于0时，最后得到的b就是两个正整数a和b的最大公约数。

4. 辗转相除法实现下面是使用Python语言实现辗转相除法求最大公约数的示例代码：def gcd(a, b):while b != 0:r = a % ba = bb = rreturn a# 测试代码print(gcd(48, 36)) # 输出：12print(gcd(1071, 462)) # 输出：21在上述代码中，我们定义了一个名为gcd的函数来实现辗转相除法。

该函数接受两个参数a和b，并返回它们的最大公约数。

两数的最大公约数最大公约数（Greatest Common Divisor，简称GCD）是指能同时整除两个或多个整数的最大正整数。

求最大公约数有多种方法，包括辗转相除法、欧几里德算法等。

本文将介绍辗转相除法和欧几里德算法，并比较它们的优缺点。

一、辗转相除法辗转相除法又称为欧几里德算法，是一种求两个整数最大公约数的简便方法。

其基本思想是将两个整数中较大的数除以较小的数，然后再用较小的数去除所得余数，直到余数为零为止，此时的除数即为最大公约数。

例如，求取36和48的最大公约数，按辗转相除法的步骤操作如下：1. 48除以36，商为1，余数为12；2. 36除以12，商为3，余数为0；3. 因此，36和48的最大公约数为12。

辗转相除法的优点是简单易懂，计算量相对较小。

然而，该方法在处理大整数时会消耗较多的时间和内存资源，不适用于涉及大数运算的场景。

二、欧几里德算法欧几里德算法是一种更高效的求解最大公约数的方法。

它基于一个定理：两个整数的最大公约数等于其中较小数和两数相除的余数的最大公约数。

以36和48为例，按欧几里德算法的步骤操作如下：1. 48除以36，商为1，余数为12；2. 36除以12，商为3，余数为0；3. 因此，36和48的最大公约数为12。

与辗转相除法相比，欧几里德算法通过连续取余的方式，减少了除法的运算次数，提高了计算效率。

尤其在处理大整数时，欧几里德算法明显快于辗转相除法。

三、辗转相除法与欧几里德算法比较辗转相除法和欧几里德算法都可以求解最大公约数，但在一些细节上存在差异。

1. 算法原理：- 辗转相除法：依赖于除法的基本原理，将大数除以小数，然后用余数递归地继续求解，直到余数为零。

- 欧几里德算法：基于两个整数的最大公约数等于其中较小数和两数相除余数的最大公约数的定理。

2. 计算效率：- 辗转相除法：简单易懂，计算量较小，但在处理大数时效率较低。

- 欧几里德算法：通过连续取余的方式，减少了除法的运算次数，在处理大数时效率更高。

辗转相处法
两个重要定理 一般定理： 如果a是任一整数而b是任一大于零的整数，则我们总能
找到一整数q，使 a=bq+r，这里r是满足不等式0≤r<b的一个 整数（余数）。
二、最大公因子的表示方法： 如果整数a和b的最大公因子是d，则表示为d=(a,b)
给定a和b（a>=b)两个整数，求最大公因子d。 根据上边给的定理，可以将a写成 a=bq+r 辗转相除法是告诉我们： (a,b)=(b,r) 即a和b的最大公因数和b和r（r是a除以b的余数）的最大
因子，反之亦然。这样由于a和b的全体公因子集合与 b和r的全体公因子集合相同，所以a和b的最大公因子 必须等于b和r的最大公因子，这就证明了 (a,b)=(b,r)。
完整的过程 8251=6105×1+2146
例2 用辗转相除法求225和135的最大公约数 225=135×1+90
6105=2146×2+1813
S1：用大数除以小数
S2：除数变成被除数，余数变成除数
S3：重复S1，直到余数为0
利用辗转相除法求两数4081与20723的最大公约数 思考：你能把辗转相除法编成程序吗？
算法1： 第一步：任意给定两个正整数； 第二步：用两数中较大那个除以较小那个，求得
商和余数； 第三步：比较上一步的余数与除数的大小关系，
1、求两个正整数的最大公约数
（1）求25和35的最大公约数 （2）求49和63的最大公约数
（1）5 25 35 57
（2）7 49 63 79
所以，25和35的 最大公约数为5
所以，49和63的 最大公约数为7
2、求8251和6105的最大公约数
辗转相除法（欧几里得算法）

辗转相除法求最大公约数
辗转相除法求最大公约数是一种常用的求两个数的最大公约数的方法。

方法是：以小数除大数，如果能整除，那么小数就是所求的最大公约数。

否则就用余数来除除数；再用新除法的余数去除刚才的余数。

依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。

具体过程如下：
输入正整数m和n，保证m不小于n；
如果n≠0，则求r=m%n，然后m=n，n=r；重复此操作直到n=0；
如果n=0，则此时m就是最大公约数。

例如：求4453和5767的最大公约数时，可作如下除法．
5767÷4453＝1余1314
4453÷1314＝3余511
1314÷511＝2余292
511÷292＝1余219
292÷219＝1余73
219÷73＝3
于是得知，5767和4453的最大公约数是73．
若要求这两个数的最小公倍数，其值就是这两数之积除以这两数的最大公约数得到的商。