欧几里得算法（辗转相除法）

求两个数的最大公因数

int gcd(int a,int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b.a%b)
}

它的过程大概是这样

为什么欧几里得算法是成立的？

不妨设$ a>b $,设$ q=\left\lfloor \frac{a}{b} \right\rfloor $（相当于C++中的a/b），$ m=a\mod b $（相当于C++中的a%b），$ d_1 =gcd(a,b),d_2 = gcd(b,m) $，那么：

1.a和b都是d₁ 的倍数

2.那么qb也是d₁ 的倍数

3.那么a-qb也是d₁ 的倍数

4.由于a=qb+m，所以m是d₁ 的倍数

5.所以d₁ 是b和m的公因数

6.由于d₂ =gcd(b,m)，所以d₁ 是d₂ 的因数

另一方面：

1.b和m是d₂ 的倍数

2.那么qb也是d₂ 的倍数

3.那么a=qb+m也是d₂ 的倍数

4.所以d₂是a和b的公因数

5.由于d₁=gcd(a,b)，所以d₂ 是d₁ 的因数

d₁ 是d₂ 的因数，d₂ 也是d₁ 的因数，所以d₁ =d₂

对于$ a<b $的情况，$ m=a\mod b=a $，显然$ gcd(a,b)=gcd(b,a) $

扩展欧几里得算法

扩展欧几里得算法可以在辗转相除途中求出不定方程$ ax+by=c $的一组解

注意到上图中倒数第二行的$ 3+6\times 3=21 $，可以改写为$ 3=6 \times(-3)+21 $，也就是说3可以被表示为6和21的线性组合

然后倒数第三行，$ 6+21 \times 1=27 $，说明6可以被表示为21和27的线性组合，那么3也就可以被表示为21和27的线性组合

有$ 3=6 \times (-3)+21=(27-21) \times (-3)+21=27 \times (-3)+21 \times 4 $

这样一路推下去即知3可以表示为75和48的线性组合。那么$ 75x+48y=3 $就能找到解了

那么如果c是其他的数，能不能找到解呢？实际上，c必须是$ gcd(a,b) $的倍数，因为我们由方程$ ax+by=c $两边除以$ gcd(a,b) $可得$ \frac{a}{gcd(a,b)}x+\frac{b}{gcd(a,b)}y=\frac{c}{gcd(a,b)} $，方程左边当然是整数，那么方程右边也必须是整数，所以c是$ gcd(a,b) $的倍数

裴蜀（贝祖）定理

设a，b为正整数，则关于x，y的方程$ ax+by=c $有整数解当且仅当c是$ gcd(a,b) $的倍数

既然如此，我们只要求$ ax+by=gcd(a,b) $的解就好了，对于方程$ ax’+by’=k gcd(a,b) $，只需要令$ x’=kx,y’=ky $即可

可以看到，通过求$ bx_0+(a \mod b)y_0=c $的解，可以得出$ ax+by=c $的解

实际上，前者等价于$ bx_0+(a-b\left\lfloor a/b \right\rfloor)y_0=c $，也就是$ ay_0+b(x_0-\left\lfloor a/b \right\rfloor y_0)=c $

对比系数发现，我们可以令：

$ \begin{cases}x=y_0 \ y=x_0-\left\lfloor a/b \right\rfloor y_0 \end{cases} $

和普通的辗转相除法相同，当$ b=0 $时递归结束，由上图右下角那个式子可知，此时应令$ x=1,y=0 $

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y), x0 = x, y0 = y;
    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}

目前还没有完全理解通过程序算出方程的解，只能通过上文的推导手算，以下内容待补充吧

参考文献：
https://zhuanlan.zhihu.com/p/100567253

原文链接：
https://www.yuque.com/fragrantveget/ucxpnh/aqsi5bwss9yiwfpv?singleDoc# 《(未完)扩展欧几里得算法》