0. 欧几里得算法
欧几里得算法用于求解两个数的最大公约数。代码如下:
int gcd(int a, int b){
if(b == 0) return a;
return gcd(b, a % b);
}
当b为0时，结束递归，此时a即为a和b的最大公约数。
1. 裴蜀定理
定理内容：
如果a、b均是整数，则一定存在整数x和y，使得ax + by = gcd(a, b)成立。
我们可以再深层次的理解一下式子ax + by = gcd(a, b)的含义，也就是说，整数a和整数b进行线性运算，可以拼凑出他们的最大公约数。再想一想，是不是也可以拼凑出他们最大公约数的整数倍？是的，可以拼凑出他们最大公约数的在整数倍，只要x和y进行对应的放大或缩小就可以了。
那也就是说，只要等号右侧是gcd(a,b)的整数倍，就一定存在整数x和整数y。（注意这里，后边用扩展欧几里得求解线性同余方程时会用到）
注意定理中说的是一定存在整数x和整数y，但是并没有告诉我们如何找到x和y，扩展欧几里得算法可以找到整数x和整数y。
2. 扩展欧几里得算法
我们当前想求解的方程是
如果使用传统的欧几里得算法，递归的下一层应该是
其中
整理一下②式：
①和③等号右侧相等，所以左侧相等，即：
由④式可得：
x’和y’是下层的答案，所以，只要知道下层的答案，就可以得到本层的x和y。
那么这样递归的出口在哪里？
出口依然是欧几里得算法的出口，即b为0时，a为a和b的最大公约数。对于方程
来说，当b为0时，gcd(a, b)就是a。所以此时x = 1，y任意都可以，通常让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, y, x);
y -= (a / b) * x;
return d;
}
这里在递归的时候，x和y参数交叉传递，是为了方便代码书写，可以自己捋顺一下。
3. 扩展欧几里得应用
解二元一次不定方程
上边说到欧几里得可以解决解出裴蜀定理中的x和y，在裴蜀定理中方程为
等号右侧为a和b的最大公约数，其实这是一种特殊情况，更一般的情况应该是等号右侧是一个任意整数。即
对于这个更一般的方程来说，如果m不是gcd(a,b)的整数倍，则没有整数解，如果m是$gcd(a,b)$的$k$倍，则有整数解，且解为
其中，$x_0$和$y_0$是$ax+by=gcd(a,b)$的结果。
上边扩展欧几里得求出的x和y其实是一组特解。
方程$ax + by = m$的解=通解 + 特解。
特解已经有了，下面对通解进行说明。
现在假设(Xi,Yi)和(Xj, Yj)是不定方程ax + by = m的两组解，则有
联立两个方程有
左右两边，同时除以$gcd(a,b)$
a和b均除以他们的最大公约数以后的结果互质，所以
可见，任意两个解中的X之差，一定是$\frac{b}{gcd}$的倍数，Y同理，所以通解为：
其中$x_0$于$y_0$是一组特解。
最小正整数解
以X为例，要求X大于0，且是满足条件的最小的那个X值，即最小正整数解。
通解为
变形为
观察上式，则求原式的最小整数解的问题就转换为求：$x_0$ % $\frac{b}{gcd}$的正整数结果。
如果$x_0$ % $\frac{b}{gcd}$的结果是正数，那就已经是最小正整数解了，如果$x_0$ % $\frac{b}{gcd}$的结果是负数，则再加上一个 $\frac{b}{gcd}$转成正数即是答案。
解线性同余方程
线性同余方程：
ax = b(mod m)
即 ax % m = b，求满足条件的x。
对于这个方程，我们可以转化一下，可以理解为，ax减去m的y倍等于b，即
这个负号其实可以算作y本身的负号，上式就变成
到了这一步，只要用扩展欧几里得求出x和y就好了呀！
求逆元
当线性同余方程ax = b(mod m)中，当b = 1，a和m互质时，求出的x就是a的逆元，记作$a^-1$。