欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。

a mod b = r
(a-r) mod b = 0
假设q为大于等于1正整数，使得
(a-r) / bq = 1
a-r = bq
a = bq+r

其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即 gcd(a,b)=gcd(b,a%b)。

---

贝祖定理

已知不为零整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式

$$ax+by=gcd(a,b)$$

有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。

---

假设 a=47, b=30, 求二元一次不定式方程 47x+30y=1的整数解。

47 mod 30 = 17 //r=17
47 = 30*1 + 17 //q=1

30 mod 17 = 13 //r=13
30 = 17*1 + 13 //q=1

17 mod 13 = 4 //r=4
17 = 13*1 + 4 //q=1

13 mod 4 = 3 //r=3
13 = 4*3 + 1 //q=3

然后把它们改写成“余数等于”的形式

17 = 47 - 30
17 = 47*1 + 30*(-1) //式1，x=1,y=-1

13 = 30 - 17
13 = 30*1 + 17*(-1) //式2，x=1,y=-1

4 = 17 - 13
4 = 17*1 + 13*(-1) //式3，x=1,y=-1

1 = 13 - 4*3
1 = 13*1 + 4*(-3) //x=1,y=-3

最后把它们“倒回去”

1 = 13*1 - 4*(-3) //式3
1 = 13*1 + [17*1+13*(-1)]*(-3)
1 = 13*1 + 17*(-3) + 13*3
1 = 13*4 + 17*(-3)
1 = [30*1 + 17*(-1)]*4 + 17*(-3)//式2
1 = 30*4 + 17*(-7)
1 = 30*4 + [47*1+30*(-1)]*(-7)//式1
1=30*11+47*(-7)

所以解的 x=-7, y=11。

---

证明贝祖定理

证明：设 a>b。

显然当 b=0，gcd(a,b)=a。此时 x=1，y=0

当a，b != 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;

a mod b = a-(a/b)*b

即: ax1+by1 = bx2+(a-(a/b)*b)y2 = bx2+ay2-(a/b)*by2;

ax1+by1 = ay2+b(x2-(a/b)*y2);

根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

---

C语言实例

#include <stdlib.h>
#include <stdio.h>

void
exgcd(int a, int b, int* x, int* y) {
    if(b == 0) {
        *x = 1;
        *y = 0;
        return;
    }
    exgcd(b, a%b, x, y);
    int t = *y;
    *y = *x-(a/b)*(*y);
    *x = t;
    return;
}

int
main(int argc, char const *argv[]) {
    int a = 47;
    int b = 30;
    int* x = (int*)malloc(sizeof(int));
    int* y = (int*)malloc(sizeof(int));
    exgcd(a, b, x, y);
    printf("%d, %d\n", *x, *y);
    return 0;
}

输出结果：(-7, 11)