歐幾里得演算法有什麼

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