歐幾里德除法

歐幾里德算法又稱輾轉相除法，用於計算兩個整數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)的公約數是一樣的，其最大公約數也必然相等，得證。

基本介紹

• 中文名：歐幾里德除法
• 用途：計算兩個整數ab的最大公約數
• 定理：gcd(a,b) = gcd(b,a mod b)
• 又稱：輾轉相除法

歐幾里德算法

歐幾里德算法又稱輾轉相除法，用於計算兩個整數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)的公約數是一樣的，其最大公約數也必然相等，得證。

步驟

歐幾里德算法（輾轉相除法）求兩個數的最大公約數的步驟如下：

先用小的一個數除大的一個數，得第一個餘數；

再用第一個餘數除小的一個數，得第二個餘數；

又用第二個餘數除第一個餘數，得第三個餘數；

這樣逐次用後一個數去除前一個餘數，直到餘數是0為止。那么，最後一個除數就是所求的最大公約數（如果最後的除數是1，那么原來的兩個數是互質數）。

例如求1515和600的最大公約數，

第一次：用600除1515，商2餘315；

第二次：用315除600，商1餘285；

第三次：用285除315，商1餘30；

第四次：用30除285，商9餘15；

第五次：用15除30，商2餘0。

1515和600的最大公約數是15