裴蜀定理
对于任意的整数a、b，都存在一对整数x、y（注意x和y可以是负整数），使得\(ax+by = gcd(a,b)\)成立。或者可以这样描述：对方程\(ax+by = c，(a,b,c∈Z)\)，只有满足\(gcd(a,b)|c\)（即a和b的最大公约数可以整除c），方程才有整数解。
扩展欧几里得算法的证明
已知\(gcd(a,b) = gcd(b,a\%b)\)，递归边界就是\(b=0，a=gcd(a,b)\)。这个时候\(ax+by = gcd(a,b)\)，只需令\(x = 1, y = 0\)，即可。
从递归边界回归的过程中，当前存在整数x'和y'满足：\(a'x' + b'y' = gcd(a,b)\)，再往上一层，则有：\(a' = b ， b' = a%b = a - a/b*b\)，代入上式有：
\(bx' + (a-a/b*b)y' = gcd(a,b)\)，即：\(bx' + ay' - a/b*by' = ay' +b(x'-a/b*y') = gcd(a,b)\)。
比较\(ax + by = gcd(a,b)\)得：\(x = y'，y = (x' - a/b*y')\)。
因为\(y'\)是整数，\(x'\)也是整数，而\(a/b\)也是向下取整后的整数结果，因此，可以得知：\(x\)和\(y\)也是整数。由此可归纳得证。
扩展欧几里得算法模板
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);
int k = x; //K 为 x'
x = y; //x 为 y'
y = k - a/b*y; //y 为 x' - a/b*y'
return d;
}
求解不定方程
通过调用扩展欧几里得函数\(exgcd(a,b,x,y)\)，得到函数返回值为\(gcd(a,b)\)，可知方程\(ax+by = gcd(a,b)\)的一组解\((x_0,y_0)\)。
对于方程\(ax+by = c, gcd(a,b)|c\) ，设 \(d=c/gcd(a,b)\)，则\(ax_0*d+by_0*d=gcd(a,b)*d=c\)，故\((x_0*d,y_0*d)\)是方程\(ax+by = c\) 的特解。
求不定方程\(ax+by = c\) 的任意解，设 x, y 是方程的任一组解
则有 \(ax + by = c\)与 \(ax' + by' =c\) 相减得 \(a(x−x') = b(y'-y)\)
从而\(\dfrac{a}{gcd(a, b)}(x−x') = \dfrac{b}{gcd(a, b)}(y'−y)\), 因为\(gcd(\dfrac{a}{gcd(a, b)},\dfrac{b}{gcd(a, b)})=1\)，所以\(\dfrac{a}{gcd(a, b)}|y' − y\)。
故存在整数t，使得 \(y'-y =\dfrac{a}{gcd(a, b)}t\)，即 \(y = y'−\dfrac{a}{gcd(a, b)}t\)，同理有 \(x = x'+\dfrac{b}{gcd(a, b)}t\)
由 x, y 的任意性，方程的全部解都可以表示为 \((x'+\dfrac{b}{gcd(a, b)}t，y'−\dfrac{a}{gcd(a, b)}t)\) , 其中\((x',y')\)由\((x_0*d,y_0*d)\)得来，\(t∈Z\)。
求x的最小正整数解，设\(P=\dfrac{b}{gcd(a, b)}\)，那么
当\(x'>0\)时，则\(x=x'\%P\)，相当于\(t\)为负整数，让\(x'\)减少\(t\)倍\(P\)，直到最小正整数解，例如当\(x'=11，P=3,t=-3\) 时，使\(x=11-3*3=2\) , 相当于 \(x=11\%3=2\)
当\(x'< 0\)时，则\(x=(x'\%P+P)\%P\)，相当于\(t\)为正整数，让\(x'\)增加到最小正整数,例如当\(x'=-11，P=3,t=4\) 时，使\(x=-11+3*4=1\) , 相当于 \(x=(-11\%3+3)\%3=(-2+3)\%3=1\)
