欧几里得算法的故事

1. 欧几里德算法

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

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

欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数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

3. 欧几里得算法是什么

欧几里得算法又称辗转相除法，是指用于计算两个非负整数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，并返回第一步。