歐幾里得演算法的故事

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，並返回第一步。