euclidean算法

① 用“辗转相除方法”计算两个数 x,y 的最大公约

辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。
简单的想法
设两数为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)。

本题中，要求x,y的最大公约数，不妨设x>y，是将上面的a,b换成x,y就得到计算的过程。

供参考！江苏吴云超祝你学习进步

② 迭代算法是什么

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法，即一次性解决问题。迭代法又分为精确迭代和近似迭代。

“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法（Iterative Method）。

辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。另一种求两数的最大公约数的方法是更相减损法。

③ 辗转相除法的原理

辗转相除法， 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。辗转相除法的原理：
设两数为a、b(a>b)，用gcd(a,b)表示a，b的最大公约数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a÷b=k.......r。辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
第一步：令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)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
证毕。
以上步骤的操作是建立在刚开始时r≠0的基础之上的。即m与n亦互质。

④ 辗转相除法为什么能求出的就是最大公因数

辗转相除法,
又名欧几里得算法（Euclidean
algorithm）乃求两个正整数之最大公因数的算法。
辗转相除法是利用以下性质来确定两个正整数
a
和
b
的最大公因数的：
若
r
是
a
÷
b
的余数,
则
gcd(a,b)
=
gcd(b,r)
a
和其倍数之最大公因数为
a。
另一种写法是：
a
÷
b，令r为所得余数（0≤r＜b）
若
r
=
0，算法结束；b
即为答案。
互换：置
a←b，b←r，并返回第一步。

⑤ 辗转相除法怎么做二元一次方程组

辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。

辗转相除法可以求出不定方程的一组整数解。
设不定方程为a x+b y=c，其中a,b,c为整数且lcm(a,b)|c
a,b辗转相除的算式为
b=q(1) a+r(2)
a=q(2) r(2)+r(3)
r(2)=q(3) r(3)+r(4)
...
r(n-2)=q(n-1)r(n-1)+r(n)
r(n-1)=q(n)r(n)
其中r(n)为lcm(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0
第i个算式为
r(i-1)=q(i)r(i)+r(i+1)
所以r(i+1)=r(i-1)-q(i)(ri) (*)
用公式(*)可以得到r(n)=lcm(a,b)关于a,b的线性组合sa+tb=lcm(a,b)
所以不定方程a x+b y=c的一组特解为
x=sc/lcm(a,b) y=tc/lcm(a,b)
注：q(i)，r(i)，括号中的是下标，lcm是求最大公约数

⑥ 若给定两个正整数m和n，试写出求他们的最大公因子（既能够同时整除m和n的最大整数）的算法——欧几里德算

辗转相除法
开放分类： 数学、最大公约数

辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。

证明：
设两数为a、b(b＜a)，求它们最大公约数(a、b)的步骤如下：用b除a，得a＝bq�1＋r�1（0≤r�1＜b）。若r�1=0，则(a，b)＝b；若r�1≠0，则再用r�1除b，得b＝r�1q�2＋r�2（0≤r�2＜r�1）。若r�2＝0，则(a，b)＝r�1，若r�2≠0，则继续用r�2除r�1，……如此下去，直到能整除为止。其最后一个非零余数即为(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，并返回第一步。

[编辑] 虚拟码

这个算法可以用递归写成如下:

function gcd(a, b) {
if a mod b<>0
return gcd(b, a mod b);
else
return a;
}

或纯使用循环:

function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}

其中“a mod b”是指取 a ÷ b 的余数。

例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出：
a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0

只要可计算余数都可用辗转相除法来求最大公因子。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。

辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。

⑦ 欧几里德算法的简单解释

[编辑本段]欧几里得算法的概述 欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b ， d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 [编辑本段]欧几里得算法原理 Lemma 1.3.1 若 a, b 且 a = bh + r, 其中 h, r , 则 gcd(a, b) = gcd(b, r). 证明. 假设 d1 = gcd(a, b) 且 d2 = gcd(b, r). 我们证明 d1| d2 且 d2| d1, 因而可利用 Proposition 1.1.3(2) 以及 d1, d2 皆为正数得证 d1 = d2. 因 d1| a 且 d1| b 利用 Corollary 1.1.2 我们知 d1| a - bh = r. 因为 d1| b, d1| r 且 d2 = gcd(b, r) 故由 Proposition 1.2.5 知 d1| d2. 另一方面, 因为 d2| b 且 d2| r 故 d2| bh + r = a. 因此可得 d2| d1. Lemma 1.3.1 告诉我们当 a > b > 0 时, 要求 a, b 的最大公因数我们可以先将 a 除以 b 所得馀数若为 r, 则 a, b 的最大公因数等于 b 和 r 的最大公因数. 因为 0r < b < a, 所以当然把计算简化了. 接着我们就来看看辗转相除法. 由于 gcd(a, b) = gcd(- a, b) 所以我们只要考虑 a, b 都是正整数的情况. Theorem 1.3.2 (The Euclidean Algorithm) 假设 a, b 且 a > b. 由除法原理我们知存在 h0, r0 使得 a = bh0 + r0, 其中 0r0 < b. 若 r0 > 0, 则存在 h1, r1 使得 b = r0h1 + r1, 其中 0r1 < r0. 若 r1 > 0, 则存在 h2, r2 使得 r0 = r1h2 + r2, 其中 0r2 < r1. 如此继续下去直到 rn = 0 为止. 若 n = 0 (即 r0 = 0), 则 gcd(a, b) = b. 若 n1, 则 gcd(a, b) = rn - 1. 证明. 首先注意若 r0 0, 由于 r0 > r1 > r2 > ... 是严格递减的, 因为 r0 和 0 之间最多仅能插入 r0 - 1 个正整数, 所以我们知道一定会有 nr0 使得 rn = 0. 若 r0 = 0, 即 a = bh0, 故知 b 为 a 之因数, 得证 b 为 a, b 的最大公因数. 若 r0 > 0, 则由 Lemma 1.3.1 知 gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = ... = gcd(rn - 1, rn) = gcd(rn - 1, 0) = rn - 1. 现在我们来看用辗转相除法求最大公因数的例子 Example 1.3.3 我们求 a = 481 和 b = 221 的最大公因数. 首先由除法原理得 481 = 2 . 221 + 39, 知 r0 = 39. 因此再考虑 b = 221 除以 r0 = 39 得 221 = 5 . 39 + 26, 知 r1 = 26. 再以 r0 = 39 除以 r1 = 26 得 39 = 1 . 26 + 13, 知 r2 = 13. 最后因为 r2 = 13 整除 r1 = 26 知 r3 = 0, 故由 Theorem 1.3.2 知 gcd(481, 221) = r2 = 13. 在利用辗转相除法求最大公因数时, 大家不必真的求到 rn = 0. 例如在上例中可看出 r0 = 39 和 r1 = 26 的最大公因数是 13, 利用 Lemma 1.3.1 马上得知 gcd(a, b) = 13. 在上一节 Corollary 1.2.5 告诉我们若 gcd(a, b) = d, 则存在 m, n 使得 d = ma + nb. 当时我们没有提到如何找到此 m, n. 现在我们利用辗转相除法来介绍一个找到 m, n 的方法. 我们沿用 Theorem 1.3.2 的符号. 首先看 r0 = 0 的情形, 此时 d = gcd(a, b) = b 所以若令 m = 0, n = 1, 则我们有 d = b = ma + nb. 当 r0 0 但 r1 = 0 时, 我们知 d = gcd(a, b) = r0. 故利用 a = bh0 + r0 知, 若令 m = 1, n = - h0, 则 d = r0 = ma + nb. 同理若 r0 0, r1 0 但 r2 = 0, 则知 d = gcd(a, b) = r1. 故利用 a = bh0 + r0 以及 b = r0h1 + r1 知 r1 = b - r0h1 = b - (a - bh0)h1 = - h1a + (1 + h0h1)b. 因此若令 m = - h1 且 n = 1 + h0h1, 则 d = r1 = ma + nb. 依照此法, 当 r0, r1 和 r2 皆不为 0 时, 由于 d = gcd(a, b) = rn - 1 故由 rn - 3 = rn - 2hn - 1 + rn - 1 知 d = rn - 3 - hn - 1rn - 2. 利用前面推导方式我们知存在 m1, m2, n1, n2 使得 rn - 3 = m1a + n1b 且 rn - 2 = m2a + n2b 故代入得 d = (m1a + n1b) - hn - 1(m2a + n2b) = (m1 - hn - 1m2)a + (n1 - hn - 1n2)b. 因此若令 m = m1 - hn - 1m2 且 n = n1 - hn - 1n2, 则 d = ma + nb. 上面的说明看似好像当 r0 0 时对每一个 i {0, 1,..., n - 2} 要先将 ri 写成 ri = mia + nib, 最后才可将 d = rn - 1 写成 ma + nb 的形式. 其实这只是论证时的方便, 在实际操作时我们其实是将每个 ri 写成 mi'ri - 2 + ni'ri - 1 的形式慢慢逆推回 d = ma + nb. 请看以下的例子. Example 1.3.4 我们试着利用 Example 1.3.3 所得结果找到 m, n 使得 13 = gcd(481, 221) = 481m + 221n. 首先我们有 13 = r2 = 39 - 26 = r0 - r1. 而 r1 = 221 - 5 . 39 = b - 5r0, 故得 13 = r0 - (b - 5r0) = 6r0 - b. 再由 r0 = 481 - 2 . 221 = a - 2b, 得知 13 = 6(a - 2b) - b = 6a - 13b. 故得 m = 6 且 n = - 13 会满足 13 = 481m + 221n. 要注意这里找到的 m, n 并不会是唯一满足 d = ma + nb 的一组解. 虽然上面的推演过程好像会只有一组解, 不过只能说是用上面的方法会得到一组解, 并不能担保可找到所有的解. 比方说若令 m' = m + b, n' = n - a, 则 m'a + n'b = (m + b)a + (n - a)b = ma + nb = d. 所以 m', n' 也会是另一组解. 所以以后当要探讨唯一性时, 若没有充分的理由千万不能说由前面的推导过程看出是唯一的就断言是唯一. 一般的作法是假设你有两组解, 再利用这两组解所共同满足的式子找到两者之间的关系. 我们看看以下的作法. Proposition 1.3.5 假设 a, b 且 d = gcd(a, b). 若 x = m0, y = n0 是 d = ax + by 的一组整数解, 则对任意 t , x = m0 + bt/d, y = n0 - at/d 皆为 d = ax + by 的一组整数解, 而且 d = ax + by 的所有整数解必为 x = m0 + bt/d, y = n0 - at/d 其中 t 这样的形式. 证明. 假设 x = m, y = n 是 d = ax + by 的一组解. 由于已假设 x = m0, y = n0 也是一组解, 故得 am + bn = am0 + bn0. 也就是说 a(m - m0) = b(n0 - n). 由于 d = gcd(a, b), 我们可以假设 a = a'd, b = b'd 其中 a', b' 且 gcd(a', b') = 1 (参见 Corollary 1.2.3). 因此得 a'(m - m0) = b'(n0 - n). 利用 b'| a'(m - m0), gcd(a', b') = 1 以及 Proposition 1.2.7(1) 得 b'| m - m0. 也就是说存在 t 使得 m - m0 = b't. 故知 m = m0 + b't = m0 + bt/d. 将 m = m0 + bt/d 代回 am + bn = am0 + bn0 可得 n = n0 - at/d, 因此得证 d = ax + by 的整数解都是 x = m0 + bt/d, y = n0 - at/d 其中 t 这样的形式. 最后我们仅要确认对任意 t , x = m0 + bt/d, y = n0 - at/d 皆为 d = ax + by 的一组整数解. 然而将 x = m0 + bt/d, y = n0 - at/d 代入 ax + by 得 a(m0 + bt/d )+ b(n0 - at/d )= am0 + bn0 = d, 故得证本定理. 利用 Proposition 1.3.5 我们就可利用 Example 1.3.4 找到 13 = 481x + 221y 的一组整数解 x = 6, y = - 13 得到 x = 6 + 17t, y = - 13 - 37t 其中 t 是 13 = 481x + 221y 所有的整数解

希望采纳

⑧ 展转相除法

辗转相除法, 又名“欧几里德算法”（Euclidean algorithm）乃求两数之最大公因数算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因数分解。辗转相除法是利用以下性质来确定最大公因数的：

若 r 是 b ÷ a 的余数, 则
<math>\gcd(a, b) = \gcd(b, r)</math></div>
a 和其倍数之最大公因数为 a。
于是, 这个算法便可以用递归写成如下:

function gcd(a, b) {
if (a 不整除 b)
return gcd(b, a mod b);
else
return a;
}
或纯使用循环:

function gcd(a, b) {
define r as integer;
while b ≠ 0 {
r := a mod b;
a := b;
b := r;
}
return a;
}
其中“a mod b”是指取 a ÷ b 的余数。

例如，123456 和 7890 的最大公因数是 6, 这可由下列步骤看出：

a b a mod b
123456 7890 5106
7890 5106 2784
5106 2784 2322
2784 2322 462
2322 462 12
462 12 6
12 6 0

只要可计算馀数都可用辗转相除法来求最大公因数。这包括多项式、复整数及所有欧几里德定义域（Euclidean domain）。

辗转相除法的运算速度为 <math>O(n^2)</math>，其中 n 为输入数值的位数。bg:Алгоритъм на Евклид cs:Euklidův algoritmus de:Euklidischer Algorithmus en:Euclidean algorithm es:Algoritmo de Euclides fr:Algorithme d'Euclide hu:Euklidészi algoritmus ja:ユークリッドの互除法 nl:Algoritme van Euclides pl:Algorytm Euklidesa pt:Algoritmo de Euclides ru:Алгоритм Евклида

取自"http://wiki.keyin.cn/index.php/%E8%BE%97%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95"

⑨ 高中数学的辗转相除法问题

辗转相除法 网络名片 欧几里德辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。简单的想法 设两数为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，若存在正整数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=qta qt=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 [编辑本段]计算机算法自然语言描述 辗转相除法是利用以下性质来确定两个正整数 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，并返回第一步。 流程图 流程图(当型) 伪代码 这个算法可以用递归写成如下: function gcd(a, b) { if b<>0 return gcd(b, a mod b); else return a; } c语言实现 /* 辗转相除法（递归）*/ #include <stdio.h> int Gcd(int a,int b); int main(void ) { int m,n,t; printf("Enter the two figures:"); scanf("%d %d",&m,&n); printf("Gcd:%d\n",Gcd(m,n)); return 0; } int Gcd(int m,int n)//最大公约数 { int t; if(m<n) {t = n,n = m,m = t;} if(n == 0) return m; else return Gcd(n,m%n); } pascal实现 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; 数据举例 其中“a mod b”是指取 a ÷ b 的余数。 例如，123456 和 7890 的最大公因子是 6, 这可由下列步骤看出： a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 12 6 0 时间复杂度 辗转相除法的运算速度为 O(n2)，其中 n 为输入数值的位数。 辗转相除法求不定方程的特解 辗转相除法可以求出不定方程的一组整数解。 设不定方程为a x+b y=c，其中a,b,c为整数且lcm(a,b)|c a,b辗转相除的算式为 b=q(1) a+r(2) a=q(2) r(2)+r(3) r(2)=q(3) r(3)+r(4) ... r(n-2)=q(n-1)r(n-1)+r(n) r(n-1)=q(n)r(n) 其中r(n)为lcm(a,b)，不妨令b=r(0)，a=r(1)，r(n+1)=0 第i个算式为 r(i-1)=q(i)r(i)+r(i+1) 所以r(i+1)=r(i-1)-q(i)(ri) (*) 用公式(*)可以得到r(n)=lcm(a,b)关于a,b的线性组合sa+tb=lcm(a,b) 所以不定方程a x+b y=c的一组特解为 x=sc/lcm(a,b) y=tc/lcm(a,b) 例如： 不定方程为326x+78y=4 求(163,39)的算式为 326=4*78+14 14=326-4*78 78=5*14+8 8=78-5*14 14=1*8+6 6=14-1*8 8=1*6+2 2=8-1*6 6=3*2 所以 2 =8-6=8-(14-8) =2*8-14=2*(78-5*14)-14 =2*78-11*14=2*78-11*(326-4*78) =46*78-11*326 即2=(-11)*326+46*78 所以4=(-22)*326+72*78 所以x=-22,y=72是不定方程326x+78y=4的一组特解 注：q(i)，r(i)，括号中的是下标，lcm是求最大公约数按此方法 6497 3869 2628 3869 2628 1241 2628 1241 1387 1387 1241 146 1241 146 1095 1241 1095 146 1095 146 949 949 146 803 803 146 657 657 146 511 511 146 365~~~~~~~~~~~~146 73 73最大公约数为73 3869=73*53 6497=89*73最小公倍数 73*53*89=344341

⑩ 辗转相除法求最大公约数c语言代码

辗转相除法是在在维基网络中的意思是：
在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（ {\displaystyle 252=21\times 12;105=21\times 5} {\displaystyle 252=21\times 12;105=21\times 5}）；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如 21 = 5 × 105 + (−2) × 252 。这个重要的结论叫做裴蜀定理。
在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分

简单的来说辗转相除法的原理就是：

先比较两个数使第一个数为最大数a，第二个数为最小数b
使最大数%最小数得到余数a%b=temp
后将余数赋值给最小数a=temp再去除最大数b即b%a
一直往复直到余数不为0