擴展歐幾里德定理
對於與不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數。那么存在唯一的整數 x，y 使得 gcd（a，b）=ax+by。
c++語言實現
#include<iostream>using namespace std;
int x,y,q;
void extend_Eulid(int a,int b)
{
if (b==0)
{
x=1; y=0; q=a;
}
else
{
extend_Eulid(b,a%b);
int temp=x;
x=y; y=temp-a/b*y;
}
}
int main()
{
int a,b;
cin>>a>>b;
if (a<b) swap(a,b);
extend_Eulid(a,b);
printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
}
求解 x，y的方法的理解
設 a>b。1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
2，ab<>0 時
設 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根據樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);
則:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據恆等定理得：x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基於 x2，y2.
上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，所以遞歸可以
結束。
