輾轉相除法

輾轉相除法， 又名歐幾里德算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較大數除以較小數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。如果是求兩個數的最大公約數，那么最後的除數就是這兩個數的最大公約數。

另一種求兩數的最大公約數的方法是更相減損法。

基本介紹

• 中文名：輾轉相除法
• 外文名：Euclidean algorithm
• 別稱：歐幾里德算法
• 用途：求最大公約數
• 歸屬學科：數學
• 出現書目：《幾何原本》

基本原理

兩個數的最大公約數是指能同時整除它們的最大正整數。

設兩數為a、b(a≥b)，求a和b最大公約數 的步驟如下：

(1)用a除以b(a≥b)，得 。

(2)若 ，則 ；

(3)若 ，則再用b除以 ，得 .

(4)若 ，則 ；若 ，則繼續用 除以 ，......，如此下去，直到能整除為止。

其最後一個餘數為0的除數即為 的最大公約數。

證明

設兩數為a、b(a>b)，用 表示a，b的最大公約數，r=a (mod b) 為a除以b的餘數，k為a除以b的商，即 。輾轉相除法即是要證明 。

第一步：令 ，則設

第二步：根據前提可知

第三步：根據第二步結果可知， 也是 的因數

第四步：可以斷定 與 互質（這裡用反證法進行證明：設 ，則 ，則 ，則a與b的一個公約數 ，故c非a與b的最大公約數，與前面結論矛盾，因此c也是b與r的最大公約數）從而可知 ，繼而 。

證畢

註：以上步驟的操作是建立在剛開始時 的基礎之上的，即m與n亦互質。

算法描述

用輾轉相除法確定兩個正整數 a 和 b(a≥b) 的最大公因數：

當時， ；否則遞歸或循環運算得出結果。

算法流程圖如下：

偽代碼描述如下：

function gcd(a,b) {if b< >0        return gcd(b,a mod b);else        return a；}

示例

例1

123456 和 7890 的最大公因數是 6，這可由下列步驟（其中，“a mod b”是指取 a ÷ b 的餘數）看出：

a	b	a mod b
123456	7890	5106
7890	5106	2784
5106	2784	2322
2784	2322	462
2322	462	12
462	12	6
12	6	0

例2

已知不定方程為，利用輾轉相除法求出一組整數解

解：求的算式為：

所以

即

所以

所以是不定方程的一組解。

代碼實現

c語言

int GCD(int a,int b){    return b==0?a:GCD(b,a%b);}

C++語言實現

#include<iostream>using namespace std;int a , b , a1 , b2 , l;int gcd(int x , int y){    if(!y)       return x;else         return gcd(y , x%y); }int main(){cout << "請輸入兩個正整數，計算它們的最大公約數" << endl ;int a , b , ans;cin >> a >> b;if(a > b)ans = gcd(a , b);else     ans = gcd(b , a);cout << ans;return 0;}

C#語言實現

static int sucDivison(int m, int n)　/*除法*/{　int remainder = 0;　if (m % n == 0)　    {　return n;　}　else　    {　        do　        {　            remainder = m % n;　            m = n;　            n = remainder;　        } while (remainder > 0);　}　if (n == 0)　{　return m;　}　return n;　}

Basic實現

INPUT m,n DO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND

Pascal實現

function gcd(a,b:integer):integer;begin    if b=0 then         gcd:=a    else         gcd:=gcd(b,a mod b);end;

Java 實現

public static int gcd(int m, int n) {    while (true)     {    if ((m = m % n) == 0)        return n;        if ((n = n % m) == 0)            return m;}}

Python實現

#遞歸解決最大公約數問題def gcd(x , y):       if y == 0         return x     else gcd(y, x%y)   x = int(input('請輸入第一個數字：'))y = int(input('請輸入第二個數字：'))print('%d 和 %d 的最大公約數為：' %(x,y),gcd(x,y))#非遞歸def gcd(x, y):    while y:            x, y = y, x%y    return x