欧几里得算法有什么

1. 什么是欧几里得算法，它有什么意义

欧几里得算法即辗转相除法，用以求两个数的最大公约数（或者最小公倍数）
证明如下
假设x,y的最大公约数为d
且设x=k1*d，y=k2*d;
则有z=x-y=(k1-k2)*d;
也必定能被d整除，所以通过两个数不断辗转，直到其中一个变为0为止，以此最终快速得出两个数的最大公约数。
在算法的应用上是用求余以加速运算的速度。
总的来说，欧几里得算法的意义就是快速求得两个数的最大公约数。

2. 拓展欧几里得算法(Extended Euclidean)

作为一只码农每当学习个新知识尤其是数学知识时。我觉得最好得搞清楚它是为了解决一个什么问题。欧几里得算法是为了求两个数的最大公约数 Greatest Common Divisor 后文都以 gcd 简称，而拓展欧几里得算法则可以帮助我们求出倒数的模 如果对这个写法不太熟悉，我们换一种表示就是——已知两个正整数a和n，我们想求一个数e使得a与e的乘积除以n的余数为1。而在大名鼎鼎的RSA算法中就有这样一步需要求倒数的模，并且还多加了一个限制条件即a与n互质。

拓展欧几里得(简称EEA) 人如其名是基于欧几里得算法(EA) 的，那么我们来回顾下小学所学怎么求两个数m,n的最小公约数 如果这个公式还没勾起你的回忆，那么我们来一段计算过程吧。这里我们求39和69的最大公约数

实话说，小时候学只是机械式地记得这个操作。但当看到EA的表达式后发现写作 能够更好地理解它的本质。

一句话为了概括EEA就是求两个数 和 使得

在具体讲怎么求 , 之前我想先介绍为什么它能让我们求得倒数的模。如前面提到的A，B两数互质的情况下我们有 而我们要求的是 所以对等式两边对A取余

下面我们来讲讲怎么一步一步地来求 , 。改写前面求39和69公约数的式子并令

归纳总结，为了求 我们需要 和

所以我们有

其中初始的 这点我们可以当 时 来验证

3. 关于欧几里得算法，主要是看不懂。请高手指点迷津。。。。

1、 欧几里德算法：给定两个正整数m和n，求他们的最大公因子，即能够同时整除m和n的最大的正整数。
E1：【求余数】以n除m并令r为所得余数（我们将有0<=r<n）。
E2：【余数为0？】若r=0，算法结束；n即为答案。
E3：【互换】置mßn,nßr,并返回步骤E1.
证明：
我们将两个正整数m和n的最大公因子表示为：t = gcd（m，n）；
重复应用等式：gcd（m，n）= gcd（n，m mod n）直到m mod n 等于0；
m可以表示成m = kn + r；则 r = m mod n ， 假设 d是 m 和 n的一个公约数，则有：
d|m 和 d|m 而 r =m – kn ，因此 d|r ，因此 d 是 (n,m mod n) 的公约数；假设 d 是 (n,m mod n) 的公约数，
则 d|n ，d|r ，但是 m=kn+r ，因此 d 也是 (a,b) 的公约数；因此 (a,b) 和
(b,a mod b) 的公约数是一样的，其最大公约数也必然相等，得证。

具体步骤描述如下：
第一步：如果 n=0 ，返回 m 的值作为结果，同时过程结束；否则，进入第二步。
第二步：用 n 去除 m ，将余数赋给 r 。
第三步：将 n 的值赋给 m，将 r的值赋给 n，返回第一步。

伪代码描述如下：
Euclid(m,n)
// 使用欧几里得算法计算gcd(m,n)
// 输入：两个不全为0的非负整数m，n
// 输出：m，n的最大公约数
while n≠0 do
r ← m mod n
m ← n
n ← r
注：(a,b) 是 a,b的最大公因数
(a,b)|c 是指 a,b的最大公因数 可以被c整除。

java实现：
package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class GreatestCommonDivisor {

int a,b,temp = 0;

public static void main(String args[]) throws IOException {

GreatestCommonDivisor gcd = new GreatestCommonDivisor();
gcd.readNum();
gcd.MaxNum();
System.out.print(gcd.a+"和"+gcd.b+"的最大公约数是:");

while (gcd.b != 0) {
gcd.temp = gcd.b;
gcd.b = gcd.a % gcd.b;
gcd.a = gcd.temp;
}
System.out.println(gcd.temp);
}
//输入两个正整数,中间用空格分开.
public void readNum() throws IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String str = buf.readLine();
for(int i = 0;i<str.length();i++){

if(str.charAt(i)==' ' && temp == 0){
a = Integer.parseInt(str.substring(temp,i));
temp = i;
b = Integer.parseInt(str.substring(temp+1,str.length()));
break;
}
}
}
public void MaxNum(){
if (a < b) {
temp = b;
b = a;
a = temp;
}
}

}

4. 欧几里得算法

计算过程一模一样，只是最后对1001取模：
1 = 167 - 166
= 167 - (834 - 4 * 167)
= 5 * 167 - 834
= 5 *(1001 - 834) - 834
= 5 * 1001 - 6 *834
= 5 * 1001 - 6 * (3837 -3 *1001)
= 23 * 1001 - 6 *3837
然后对等式两端同时除以模1001得

6 * 3837 = 1 (mod 1001)
于是 x ＝ 6

5. 欧几里得求最大公约数算法问题

因为d是a、b的一个公约数，所以a、b都能被d整除，假设a=xd，b=yd，则由a=kb+r可得xd=kyd+r，则r=xd-kyd=(x-ky)d，因此r也能被d整除，即d是(b,a mod b)的公约数。

6. 欧几里得算法——计算最大公因数

计算最大公因数的欧几里得算法

最大公因数

最大公因数，也称最大公约数，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b）。求最大公约数有多种方法，常见的有质因数分解法、辗转相除法等等。

欧几里得算法

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里得算法在RSA加密算法中有运用。

源码

//当N>M时，第一次循环之后两数将进行交换

int Gcd(int m,int n){

    int r;

    while(n > 0){

        r = m % n;

        m = n;

        n = r;

    }

    return m;

}

算法分析

算法通过连续计算余数，知道余数是0为止，最后所得的非0余数就是最大公因数。例如 M=1989 ，N=1590，则余数序列为399，393，6，3，0。因而，Gcd(1989,1590)=3，从余数的序列可知，这是一个快速收敛的算法。要想得出该算法的运行时间，就需要确定余数序列究竟有多长？不妨大胆的猜测log(N)看似是非常理想的答案，但是余数序列递减的规律并非是按照常数因子所递减的，事实上，数学家们已经证明了，在两次迭代以后，余数的值最多是原始值的一半。由此可知，迭代次数之多是2log(N) = O(logN)从而得到算法的时间复杂度。下面，我们从数学家那里问来了证明过程。

时间复杂度证明

定理：

如果 M > N ，则 M mod N < M/2

证明：如果 N<=M/2 ，则余数小于N，故定理在这种情况下成立

如果 N>M/2 ，此时M仅含有一个N，从而余数为M-N

从上面的例子来看，2logN 大约是20，但是实际上，我们只是运行了7次计算，可能有人会说，这个常数2不是最好的界限值。事实上，欧几里得算法的平均时间复杂度是需要大量的数学分析进行证明的，算法迭代的平均次数是（12ln2lnN）/pi^2+1.47。

有兴趣的同学可以研究一下质因数分解等其他算法哦

7. 欧几里德算法

The Euclidean Algorithm
欧几里德算法(又称辗转相除法)是一种用于快速寻找两个整数的最大公约数的技巧。

最大公约数 Greatest Common Divisor (GCD)：整数 A 和 B 的最大公约数是指能够同时整除 A 和 B 的最大整数。

使用欧几里德算法寻找 GCD(A,B) 的过程如下：

欧几里德算法使用了下述特性：

如果 A 和 B 其中一个为 0，便可利用前两个特性得出 GCD。 第三个特性帮助我们将大而复杂的问题化简为小而容易解决的问题。 欧几里德算法先利用第三个特性迅速化简问题，直至可以通过前两个特性求解为止。

证明 GCD(A,0)=A 的过程如下：

GCD(0,B)=B 的证明过程与此类似，区别仅在于用 B 替换 A。

先证明较简单的 GCD(A,B)=GCD(B,A-B)，再证明 GCD(A,B)=GCD(B,R)

根据定义 GCD(A,B) 可均分 A。因此，A 一定是 GCD(A,B) 的倍数，即 X⋅GCD(A,B)=A ，此处的 X 是某个整数。 根据定义 GCD(A,B) 可均分 B。因此，B 一定是 GCD(A,B) 的倍数，即 Y⋅GCD(A,B)=B ，此处的 Y 是某个整数。

根据 A-B=C 可得出：

由此可见 GCD(A,B) 可均分 C。 上图的左侧部分展示了此证明，提取如下：

证明 GCD(B,C) 均分 A
根据定义 GCD(B,C) 可均分 B。因此，B 一定是 GCD(B,C) 的倍数，即 M⋅GCD(B,C)=B ，此处的 M 是某个整数。 根据定义 GCD(B,C) 可均分 C。因此，C 一定是 GCD(B,C) 的倍数，即 N⋅GCD(B,C)=B ，此处的 N 是某个整数。

根据 A-B=C 可得出:

B+C=A
M⋅GCD(B,C) + N⋅GCD(B,C) = A
(M + N)⋅GCD(B,C) = A
由此可见 GCD(B,C) 可均分 A。 下图展示了此证明：

证明 GCD(A,B)=GCD(A,A-B)
根据定 GCD(A,B) 均分 B
同时，已证明 GCD(A,B) 均分 C
因此，GCD(A,B) 是 B 和 C 的公约数
由于 GCD(B,C) 是 B 和 C 的最大公约数，所以 GCD(A,B) 必须小于或等于 GCD(B,C)。

根据定义 GCD(B,C) 均分 B
同时，已证明 GCD(B,C) 均分 A
因此，GCD(B,C) 是 B 和 A 的公约数
由于 GCD(A,B) 是 A 和 B 的最大公约数，所以 GCD(B,C) 必须小于或等于 GCD(A,B)。

∵ GCD(A,B)≤GCD(B,C) 且 GCD(B,C)≤GCD(A,B) ∴ GCD(A,B)=GCD(B,C) 即 GCD(A,B)=GCD(B,A-B)

下图的右侧部分展示了此证明的图示：

前面已证明了 GCD(A,B)=GCD(B,A-B) 另外，对于 GCD( ) 而言，括号中各项的顺序并不重要，因此 GCD(A,B)=GCD(A-B,B) 那么，如果反复应用 GCD(A,B)=GCD(A-B,B)，便可得到： GCD(A,B)=GCD(A-B,B)=GCD(A-2B,B)=GCD(A-3B,B)=...=GCD(A-Q⋅B,B) 由于 A= B⋅Q + R 可得 A-Q⋅B=R，所以 GCD(A,B)=GCD(R,B) 。 由于括号中各项的顺序并不重要，因此最终可得： GCD(A,B)=GCD(B,R)

找寻 270 和 192 的最大公约数：

A=270, B=192

A=192, B=78

A=78, B=36

A=36, B=6

A=6, B=0

从上面的过程可以看出： ∵ GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6 ∴ GCD(270,192) = 6

8. 欧几里德算法的简单解释

[编辑本段]欧几里得算法的概述 欧几里德算法又称辗转相除法，用于计算两个整数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 所有的整数解

希望采纳

9. 欧几里德算法是什么啊

欧几里德算法
欧几里德算法又称辗转相除法,用于计算两个整数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)的公约数是一样的,其最大公约数也必然相等,得证.
欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为：
void swap(int & a,int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
{
a = b;
b = c;
}
return b;
}
参考资料：internet

10. 欧几里得算法是什么

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数除除数。

再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：

1、若r是a ÷ b的余数，且r不为0，则gcd(a,b) = gcd(b,r)。

⒉、a和其倍数之最大公因子为a。

另一种写法是：

⒈、令r为a/b所得余数（0≤r），若r= 0，算法结束；b即为答案。

⒉、互换：置a←b，b←r，并返回第一步。