擴展歐幾里德定理

由擴展歐幾里德定理，可以通過擴展歐幾里德算法求解線性同餘方程

基本介紹

• 中文名：擴展歐幾里德定理
• 作用：求解線性同餘方程
• 表達式： gcd（a，b）=ax+by
• 實現方式：c++語言實現

擴展歐幾里德定理

對於不完全為 0 的整數 a，b，gcd（a，b）表示 a，b 的最大公約數。那么一定存在整

數 x，y 使得 gcd（a，b）=ax+by。

c++語言實現

#include <cstdio>using namespace std;int x, y, q;void extend_Euclid(int a, int b){    if( b == 0 )    {        x = 1;        y = 0;        q = a;    }    else    {        extend_Euclid(b, a % b);        int temp = x;        x = y;        y = temp - a / b * y;    }}int main(void){    int a, b;    scanf("%d%d", &a, &b);    if(a < b)    {        int t = a;        a = b;        b = t;    }    extend_Euclid(a,b);    printf("%d=(%d)*%d+(%d)*%d\n", q, x, a, y, b);    return 0;}

求解 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，所以遞歸可以

結束。