用辗转相除法求下列两数的最大公约数

求两个数的最大公约数
——辗转相除法
已知两个数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的最大公约数，此方法得证。

C语言求任意两个数的最大公约数，通常可以使用辗转相除法进行实现。

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

其基本原理是通过依次取模运算，将两个数替换为除数和余数的过程，直到余数为0，此时除数即为最大公约数。

下面将通过C语言代码展示辗转相除法的实现过程。

1. 定义函数我们需要定义一个函数来实现辗转相除法。

该函数接受两个整数参数，然后利用while循环进行辗转相除，直到余数为0，返回最大公约数。

```cint gcd(int a, int b){int temp;while (b != 0){temp = a % b;a = b;b = temp;}return a;}```2. 主函数接下来，我们编写主函数来调用gcd函数，并输入两个整数作为参数。

在主函数中，我们可以通过用户输入实现任意两个数的最大公约数求解。

```c#include <stdio.h>int main(){int num1, num2;printf("请输入两个整数：");scanf("%d %d", &num1, &num2);int result = gcd(num1, num2);printf("最大公约数为：%d\n", result);return 0;}```3. 完整代码将上述定义的函数和主函数整合在一起，得到完整的C语言代码如下所示：```c#include <stdio.h>int gcd(int a, int b){int temp;while (b != 0){temp = a % b;a = b;b = temp;}return a;}int main(){int num1, num2;printf("请输入两个整数：");scanf("%d %d", &num1, &num2);int result = gcd(num1, num2);printf("最大公约数为：%d\n", result);return 0;}```通过上述代码，就可以在C语言中实现求任意两个数的最大公约数的功能。

辗转相除法‎求最大公约‎数和最小公‎倍数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）、判断三数是否公倍数关系（即两数的最大公约数等于另一数）等。

求最大公约数的方法辗转相除法证明全文共四篇示例，供读者参考第一篇示例：辗转相除法是求解最大公约数的一种有效方法，也叫做欧几里德算法。

其基本思想是通过反复地用较大数除以较小数，然后用除数去除余数，一直重复这个过程，直到余数为0为止。

最终能够得到这两个数的最大公约数。

下面我们来详细地介绍辗转相除法的原理和证明过程。

假设有两个正整数a和b，其中a>b，我们要求它们的最大公约数。

首先我们用a除以b，得到商q和余数r，即a = q*b + r。

接着我们将b赋值给a，r赋值给b，然后再次用b去除以r，得到商q1和余数r1，即b = q1*r + r1。

如此循环下去，直到r1等于0为止。

那么此时b就是a和b的最大公约数。

下面我们用数学归纳法来证明辗转相除法的正确性。

设a=k*b+r，其中k和r是整数。

若d是a和b的一个公约数，则d也是b和r的公约数，反之亦然。

因此a和b的公约数集合等于b和r的公约数集合，即gcd(a, b) = gcd(b, r)。

现在我们假设b和r的最大公约数是d。

根据辗转相除法的步骤，可以得到以下等式：b = q1*r + r1r = q2*r1 + r2r1 = q3*r2 + r3...最终我们会得到r(n-1) = qnrn，其中rn是0。

根据这些等式，我们可以得出以下结论：r(n-2) = r(n-3) - qn-1*r(n-2)r(n-3) = r(n-4) - qn-2*r(n-3)...rn = r1 - q2*r将这些等式带入最后的等式b = q1*r + r1，可以得出以下结论：d|r(n-2) = d|r(n-3) = ... = d|r1 = d|b所以最大公约数d同时也是a和b的最大公约数。

通过以上的推导和证明，我们可以得出结论：辗转相除法能够有效地求解两个数的最大公约数。

这个算法简单易懂，而且效率非常高，适用于各种情况。

在实际运用中，辗转相除法是一个非常重要的数学工具。

求最大公约数的方法辗转相除法证明
辗转相除法，又称为欧几里得算法，是一种用于求两个整数的最大公约数（GCD）的经典算法。

这个算法基于一个简单但重要的原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

证明辗转相除法的原理，我们可以按照以下步骤进行：
第一步，假设我们有两个正整数a和b，其中a > b。

根据整数的性质，我们知道a可以表示为b的倍数加上余数，即a = bq + r，其中0 ≤ r < b。

第二步，我们考虑a和b的最大公约数。

由于a = bq + r，a的任何公约数都必须是b 和r的公约数。

因此，a和b的公约数集合是b和r的公约数集合的子集。

第三步，反过来，考虑b和r的最大公约数。

由于r = a - bq，r的任何公约数也必须是a和b的公约数。

因此，b和r的公约数集合是a和b的公约数集合的子集。

第四步，结合第二步和第三步，我们可以得出a和b的公约数集合与b和r的公约数集合是相同的。

因此，a和b的最大公约数等于b和r的最大公约数。

第五步，根据第四步的结论，我们可以反复应用辗转相除法的原理，直到余数为0。

此时，非零的除数就是a和b的最大公约数。

因此，我们证明了辗转相除法可以正确地求出两个整数的最大公约数。

这个算法不仅简单有效，而且在实际应用中具有广泛的用途，包括密码学、计算机科学等领域。

最大公约数的辗转相除法
辗转相除法，也称为欧几里得算法，是一种用于计算两个整数的最大公约数（GCD）的经典算法。

这个算法基于一个简单的事实：两个整数的最大公约数与其中较小的数和两数的差的最大公约数相同。

以下是辗转相除法的步骤：
将两个数中较大的数除以较小的数，得到余数。

将较小的数和这个余数作为新的两个数，重复步骤1，直到余数为0。

当余数为0时，停止算法，较小的数就是两个数的最大公约数。

例如，计算252和105的最大公约数：
252 ÷105 = 2 余42
105 ÷42 = 2 余21
42 ÷21 = 2 余0
因此，252和105的最大公约数是21。

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;}。

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

它的基本思想是：用较大的数除以较小的数，得到余数，再用较小的数除以余数，得到新的余数，如此反复，直到余数为0为止。

此时，最后一次做除法得到的除数即为原来两个数的最大公约数。

例如，求出105和45的最大公约数。

用105除以45，得到余数15；然后用45除以15，得到余数0。

因此，105和45的最大公约数为15。

辗转相除法的优点在于它简单易懂、容易实现，只需进行一次递归即可求出最大公约数，而且它的时间复杂度为O(logn)，效率较高。

因此，在实际应用中，辗转相除法被广泛地使用。

- 1 -。

辗除法辗除法（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 的余数。

求两个正整数的最大公约数的辗转相除法算理如何求两个正整数的最大公约数？这是高中数学必修三算法一章中的内容。

用算法求解此问题时，教材中介绍了一种古老而有效的算法——辗转相除法。

对于辗转相除法以及同节中的更相减损术的算法易理解，但其中的算理，不少学生甚至老师都有一些疑惑，为了解决这个疑问，笔者进行了思考。

一、被除数与除数的公约数集与除数与余数的公约数集相等吗“用辗转相除法求 8151 与 6105 的最大公约数，我们可以考虑用两数中较大的数除以较小的数，求得商和余数：8251=6105×1+2146由此可得，6105 与 2146 的公约数也是 8251 与 6105 的公约数，反过来 8251 与 6105 的公约数也是 6105 与 2146 的公约数，所以它们的最大的公约数相等。

”从以上例子中不难看出，运用了“被除数与除数的公约数集与除数与余数的公约数集相等”这一结论。

下面对这一结论予以证明。

设 a=b×q+r，其中 a 为被除数，b 为除数，q 为商，r 为余数．①设 a、b 的公约数集为 A，则，a=mq1,b=mq2mq1= mq2q+rr=m(q1-q2q)故m是r的约数，所以a、b的公约数一定是b、r的公约数。

②设 n 为 b、r 的公约数集 B，n ∈ B，n 为 b、r 的公约数，则 b=nq1， r=nq2， a= nq1q+nq2a=n(q1q+ q2)故n是a的约数，所以b、r的公约数一定是a、b的公约数。

由①②知 A=B，所以被除数与除数的公约数集与除数与余数的公约数集相等。

二、辗转相除法与更相减损术两种方法之间有联系吗“用更相减损术求 98 与 63 最大公约数。

解：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减，如图示：所以，98 和 63 的最大公约数等于 7。

”将上图变化为下图：对比较辗转相除法，不难发现，更相减损术与辗转相除法算理一致，只不过更相减损术求解过程中的各式的商总是“1”这个定值。

辗转相除求最大公约数
辗转相除也叫欧几里得算法，是很重要的。

但是很多人看了乘式表达的算法，感到很迷惑，甚至大学毕业了还不懂什么叫做辗转相除。

下面用除式清晰地表达辗转相除的概念。

比如326和78的辗转相除：326÷78=4 (14)
78÷14=5 (8)
14÷8=1 (6)
8÷6=1 (2)
6÷2=3 0
第一步列式：大÷小=商…余数，以后每一步都用上一步的除数除以余数（红色部分），直到余数为零。

为什么一定能得到余数为零的式子呢？因为第一步的余数小于除数，第二步用它做除数，得出的余数更小，这样一步一步减少，余数不能为负数，最后肯定减为0。

以上的算法，就是辗转相除。

辗转相除法求最大公约的方法
1. 嘿，你知道辗转相除法求最大公约数吗？就比如说，咱们算 12 和
18 的最大公约数。

咱们用 18 除以 12 得到余数 6，然后再用 12 除以 6 就整除啦！这不就找到最大公约数 6 了嘛！神奇吧！
2. 辗转相除法求最大公约数可真是个好方法呀！想象一下，给你两个数，比如 24 和 36，用辗转相除法一步步算下去，就像在走一条清晰的路，最
后就能找到它们的最大公约数 12 啦，多有意思！
3. 哇哦，辗转相除法求最大公约数就像一把钥匙呀！你看，拿 40 和
50 来举例，通过不断地辗转相除，就能打开找到最大公约数10 的那扇门，这不是很妙吗？
4. 你可别小看辗转相除法求最大公约数哟！就像在解一个有趣的谜题，比如 30 和 42，一次次的除法运算就像是一步步揭开谜题的过程，最终找
到 6 这个最大公约数的时候，是不是很有成就感？
5. 嘿呀，辗转相除法求最大公约数真的超厉害的！举个例子，72 和 90，就这样用除法算呀算呀，最后就得出它们的最大公约数 18 了，这感觉就像
发现了一个宝藏！
6. 哎呀，辗转相除法求最大公约数太有用啦！比如要算 56 和 64 的最
大公约数，通过辗转相除，一路探索下去，找到了 8 这个答案，不是很赞吗？
7. 哇，辗转相除法求最大公约数简直是数学中的魔法呀！不信你试试
80 和 96，按照步骤去做，就能神奇地找到最大公约数 16 呢！所以说，辗
转相除法求最大公约数真的很牛啊！
我的观点结论就是：辗转相除法求最大公约数是非常实用且有趣的方法，值得大家好好掌握和运用呀！。

用碾转相除法求最大公约数碾转相除法是求解两个正整数的最大公约数的一种实用方法，使用它可以在不需要知道两个数质因数分解的情况下找到它们的最大公约数。

该方法也被称为辗转相除法或欧几里得算法，它基于重复使用两个整数之间的余数来逐步缩小数值。

碾转相除法的原理就是求两数的余数，然后将这两个数中较小数的位置替换成所得余数，再重复进行相同的操作，直到余数为0为止。

最后将整个过程中所曾经得到的非零余数的最后一个作为最大公约数。

1.第一步，输入正整数a和b，将两数作为被除数和除数。

2.第二步，用除数去除被除数，得到余数r。

a = qb + r例如，10÷6，商为1余4，所以r=4。

3.第三步，将上一步的除数b作为新的被除数，余数r作为新的除数，即：b = r, r = a mod b 或 r = a - bq其中mod表示求模运算，即a÷b的余数。

4.重复上述操作，直到余数r等于0。

5.结束，此时最大公约数为上一步的除数b。

下面通过一个例子来演示碾转相除法的求解过程：示例：求48和60的最大公约数。

Step 1: 用60去除48，得到余数12，即60 = 48 × 1 + 12终止，最大公约数为上一步的除数，即12。

所以，48和60的最大公约数为12。

通过以上例子可以看出，碾转相除法是一种比较简单直观的方法，因为它只需要进行除法运算和求模运算。

这种方法的时间复杂度为O(log(min(a,b)))，比其他几种求最大公约数的方法效率更高。

同时，通过这种方法还可以得到一组贝祖等式的解，即gcd(a,b)=sa+tb，其中s和t是贝祖恒等式的解。

需要注意的是，在实际应用中，如果两个数较大，就需要进行多次除法和求模运算，并且这种方法的精确度取决于计算机的整除操作。

同时，如果使用的是浮点数类型，则求模运算的结果可能存在误差，所以在确定最大公约数时需要避免使用浮点数类型。

最后，碾转相除法是一种比较实用的方法，不仅可以用于求最大公约数，还可以用于一些其他的数值计算问题。

利用辗转相除法求最大公约数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）是指两个或多个整数共有的约数中最大的一个。

求最大公约数的方法有许多种，其中辗转相除法和欧几里得算法是最为常用和简便的方法。

辗转相除法，又称欧几里得算法，用于求两个非负整数的最大公约数。

假设有两个整数a和b，其中a > b；通过反复将a除以b，得到的余数记作r，然后再用b除以r，再得到余数，如此反复，直到余数为0。

此时，b的值就是所求的最大公约数。

这个过程可以用以下的公式来表示：a =b * q + r，其中a和b为整数，q为商，r为余数。

该算法的详细步骤如下：- 将较大的数除以较小的数，并记录余数；- 再将较小的数除以刚才的余数，并记录新的余数；- 重复以上步骤，直到余数为0为止；- 最后的除数就是最大公约数。

以求解两个整数24和18的最大公约数为例，采用辗转相除法的步骤如下：24 ÷ 18 = 1 余数618 ÷ 6 = 3 余数0由此可得，最大公约数为6。

这个算法的优点在于，即使对于非常大的数，也能够通过反复除法运算得到最大公约数，具有较高的效率。

欧几里得算法不仅适用于两个数的最大公约数的求解，也适用于多个数的最大公约数。

通过求出其中两个数的最大公约数，再与第三个数求最大公约数，以此类推，直到最后一个数。

例如，求解24、18和30的最大公约数，我们可以先求24和18的最大公约数为6，再将6与30求最大公约数，得到最终的结果也为6。

在实际应用中，求最大公约数的方法可以帮助我们简化分数、约分、解方程、化简代数式等数学问题，具有很强的实用性。

而辗转相除法和欧几里得算法作为最为常用的方法，不仅计算简便，还能适用于各种情况。

总结起来，辗转相除法和欧几里得算法是最常用和简便的求最大公约数的方法。

辗转相除法通过不断除法运算和求余数的方式，迭代得到最大公约数；而欧几里得算法则不仅适用于两个数的求解，还适用于多个数的求解。

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

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

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

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

具体过程如下：
输入正整数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．
若要求这两个数的最小公倍数，其值就是这两数之积除以这两数的最大公约数得到的商。