擴充歐幾裡得算法---Extended Euclidean algorithm

概述

歐幾裡德算法又稱輾轉相除法，用于計算兩個整數a,b的最大公約數。其計算原理依賴于下面的定理： gcd函數就是用來求(a,b)的 最大公約數的。 gcd函數的基本性質： gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|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)的公約數是一樣的，其最大公約數也必然相等，得證

擴充的：

用數學語言來表述：求整數x和y使得 ax+by=c.可以發現如果gcd(a,b) | c 不成立，也就是c不是a,b最大公約數的倍數，那麼顯然無整數解。

是以我們一般求ax+by=gcd(a,b),隻要求得一對整數解 （x,y）那麼任意的c(整除gcd(a,b))就可以得到，隻要在兩邊同時乘以一個倍數即可。

代碼：

#include <iostream>
using namespace std;
int ext_gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=ext_gcd(b,a%b,y,x);
	y=y-(a/b)*x;			//  x=_y;
	return d;			//  y=_x-(a/b)*_y;
} 
int main()
{
	int x,y,a=99,b=78;
	cout<<ext_gcd(a,b,x,y)<<endl;
	cout<<x<<" "<<y<<endl;
}
           

說明：

假設我們已經得到了：

_d=gcd(b,a mod b) 和 _d=b*_x+(a mod b)*_y 的（_d,_x,_y）對于遞歸過程來說，有

d=gcd(a,b)=_d=gcd(b,a mod b),那麼為了得到滿足 d=ax+by的x和y，利用上述等式d=_d進行變形：

d=b*_x+(a-(a/b))*_y=a*_y+b(_x-(a/b)*_y)

當選擇x=_y和y=_x-(a/b)*_y就可以滿足等式。這樣遞歸就可以進行下去，當然遞歸的終止條件是： b==0, return (a,1,0)