扩展欧几里得（exgcd）证明及笔记
RE_Prince
·
·
个人记录
来一发数论笔记/cy
\gcd
先放个代码：
```cpp
inline int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
```
当然，还可以用系统自带的 `__gcd()` 函数，但是我的 VS 没有（哭）
那为什么可以这么写呢？
$\text{gcd}$ 的证明如下：
从 $\text{gcd}(a,b)=\gcd(b,a\bmod b)$ 可以推出 $\text{gcd}(a,b)=\gcd(b,a-b)$。
设 $\gcd(a,b)$ 为 $1$ 式，则 $\gcd(b,a-b)$ 为 $2$ 式。
若 $\text{gcd}(a,b)=\gcd(b,a - b)$，则两边的约数应该相同。
那么有 $a\bmod p=b\bmod p=0$。（$p$ 为约数）
那么还有 $b\bmod p=(a-b)\bmod p=0$。
从 $b\bmod p=(a-b)\bmod p=0$ 可以推出，在 $2$ 式中，$a\bmod p$ 也等于 $0$。（相减）
从 $a\bmod p=b\bmod p=0$ 可以推出， $a\bmod p=b\bmod p=(a-b)\bmod p=0$。（相减）
则两边的约数都为 $p$。
得证。
## $\text{exgcd}
```cpp
inline 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 r = x;
x = y;
y = r - a / b * y;
}
```
再给出简化后的模板：
```cpp
inline void exgcd(int a, int b, int& x, int& y)
{
if (b == 0)
{
x = 1; y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
```
$\text{exgcd}$ 是解决 $ax+by=\gcd(a,b)$ 这样一个方程组的，保证有解。
它的证明方式如下：
根据上方 $\gcd$ 证明，可以得知 $\gcd(a,b)$ 最后一定能转化成 $\gcd(a,0)$ 的情况。所以如果 $b$ 变成了 $0$，这个方程就成为了 $ax+0y=a$。最后的解就是 $x=1,y=0$。
那如果不是这种情况呢？
把 $ax+by=\gcd(a,b)$ 这个方程组进行一次递归，可变成 $bx'+(a-a/b\times b)y'=\gcd(b,a\bmod b)$（就是把 $a\ b$ 替换了一下）
从上面的式子可以推出 $bx'+by'+ay'(a/b\times b)=\gcd(b,a\bmod b)$，再进行一步结合，可变成 $ay'+b(x'-a/b\times b)$。
令 $x=y',y=x'-a/b\times b$，就可得出 $ax+by=\gcd(a,b)$。
得证。
本质上在原始模板里递归求完 `exgcd(b, a%b, x, y)` 后，对 $x$ 和 $y$ 进行了交换，然后再减去原本交换前得到的 $x$ 值。那么我们考虑，这两个值的交换是不是没必要？
答案是：确实。
再进行一步简化，就得到了简化后的代码。
$\text{exgcd}$ 有一道非常经典的题，就是同余方程那道题，可以试着用 $\text{exgcd}$ A 掉它。
--------
综上是 $\text{exgcd}$ 和 $\gcd$ 的所有内容。