一、欧几里得算法
欧几里得算法，也叫辗转相除，简称 gcd，用于计算两个整数的最大公约数
引理：\(\gcd(a,b)=\gcd(b,a\%b)\)
证明：
设 \(r=a%b\) , \(c=gcd(a,b)\)
则 \(a=xc\) , \(b=yc\) , 其中 \(x , y\) 互质
\(r=a\%b=a-pb=xc-pyc=(x-py)c\)
而 \(b=yc\)
假设 \(y\) 与 \(x-py\) 不互质：
设 \(y=nk\) , \(x-py=mk\) , 且 \(k>1\) （互质）
将 \(y\) 带入可得
\(x-pnk=mk\)
\(x=(pn+m)k\)
则 \(a=xc=(pn+m)kc\) , \(b=yc=nkc\)
那么此时 \(\gcd(a,b)=kc\ne k\)，矛盾！
所以 \(y\) 与 \(x-py\) 互质，\(\gcd(r,b)=c\)
即 \(\gcd(b,r)=c=\gcd(a,b)\)
得证！
当 \(a\%b=0\) 时， \(\gcd(a,b)=b\)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
二、扩展欧几里得算法
扩展欧几里得算法，简称 exgcd，一般用来求解不定方程，求解线性同余方程，求解模的逆元等
引理：存在 \(x\) , \(y\) 使得 \(\gcd(a,b)=ax+by\)
证明：
当 \(b=0\) 时，\(\gcd(a,b)=a\)，此时 \(x=1 , y=0\)
当 \(b\ne0\) 时，
设 \(ax_1+by_1=\gcd(a,b)=\gcd(b,a\%b)=bx_2+(a\%b)y_2\)
又因 \(a\%b=a-\frac{a}{b}\times b\)
则 \(ax_1+by_1=bx_2+(a-\frac{a}{b}\times b)y_2\)
\(ax_1+by_1=bx_2+ay_2-\frac{a}{b}\times by_2\)
\(ax_1+by_1=ay_2+bx_2-b\times \frac{a}{b}\times y_2\)
\(ax_1+by_1=ay_2+b(x_2-\frac{a}{b}\times y_2)\)
解得 \(x_1=y_2\) , \(y_1=x_2-\frac{a}{b}\times y_2\)
因为当 \(b=0\) 时存在 \(x\) , \(y\) 为最后一组解
而每一组的解可根据后一组得到
所以第一组的解 \(x\) , \(y\) 必然存在
得证！
根据上面的证明，在实现的时候采用递归做法
先递归进入下一层，等到到达最后一层即 b=0 时就返回x=1 , y=0
再根据 \(x=y’\) , \(y=x’-\frac{a}{b}\div y’\)（\(x’\) 与 \(y’\) 为下一层的 \(x\) 与 \(y\)）得到当层的解
不断算出当层的解并返回，最终返回至第一层，得到原解
void exgcd(int a,int b)
{
if(b)
{
exgcd(b,a%b);
int k=x;
x=y;
y=k-a/b*y;
}
else y=(x=1)-1;
}
-
应用一：
exgcd解不定方程（使用不将 \(a\) 与 \(b\) 转为互质的方法）
对于 \(ax+by=c\) 的不定方程，设 \(r=gcd(a,b)\)
当 \(c\%r \ne 0\) 时无整数解
当 \(c\%r=0\) 时，将方程右边 \(\times r\div c\) 后转换为 \(ax+by=r\) 的形式
可以根据扩展欧几里得算法求得一组整数解 \(x_0\) , \(y_0\)
而这只是转换后的方程的解，原方程的一组解应再 \(\times c\div r\) 转变回去
则原方程解为 \(x_1=x_0\times c\div r\) , \(y_1=y_0\times c\div r\)
通解 \(x=x_1+b\times r\div t\) , \(y=y_1-a\times r\div t\) ，其中 \(t\) 为整数 -
应用二：
exgcd解线性同余方程
关于 \(x\) 的模方程 \(ax\%b=c\) 的解
方程转换为 \(ax+by=c\) 其中 \(y\) 一般为非正整数
则问题变为用exgcd解不定方程
解得 \(x_1=x_0\times c\div r\)
通解为 \(x=x_1+b\div r\times t\)
设 \(s=\frac{b}{r}\) （已证明 \(\frac{b}{r}\) 为通解的最小间隔）
则 \(x\) 的最小正整数解为 \((x_1\%s+s)\%s\)