辗转相除法

例子：
求 86和32 的最大公约数：
（86,32）：

86=32*2+22；

假设86和32的最大公约数为m，则86%m==0,32%m==0——————–>22%m==0

可以转化为32和22的最大公约数（32,22）：

32=1*22+10；

同理转化为22,10的最大公约数（22,10）：

22=2*10+2；

转化为10和2的最大公约数（10,2）：
10=5*2；

变为（2,0）；

所以最大公约数为2；

可得程序：

c++

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

拓展欧几里得

裴蜀定理定义：给定两个整数a和b，假设他们的最大公约数是p，那么下面(x,y)方程有整数解当且仅当n是p的倍数：

一般性证明：

设a>b.

当b=0,gcd(a,b)=a.此时x=1,y=0;

当ab!=0时

设ax1+by1=gcd(a,b);

bx2+(a mod b)y2=gcd(b, a mod b);

根据朴素的欧几里得原理有gcd(a,b)=gcd(b,a mod b);

所以：ax1+by1=bx2+(a mod b)y2;

即ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)\by2;

由恒等定理可以得到：x1=y2;y1=x2-(a/b)*y2;

因此x1,y1的值是基于x2,y2的

由上面的证明可知，不断的递归，其结果肯定有个时候b为0，此时递归可以结束：

cpp

int e_gcd(int a,int b,int &x,int &y){
	if(!b){
		x=1;y=0;
		return a;
	}
	int gcd=e_gcd(b,a%b,y,x);
	y-=a/b*x;
	return gcd;
}

此时算出的结果只是众多解中的一个，可以通过如下公式求得所有解：
$$
\begin{cases}
x’=x+\frac{b}{\gcd}\times k\
y’=y-\frac{a}{\gcd}\times k\
\end{cases}
（如果k为任意整数）
$$
可以进行简单的证明：
设新的解为x+s1,y-s2,即有a(x+s1)+b\(y-s2)=gcd成立，通过代入ax+by=gcd之中可以得到as1=bs2;

于是
$$
\frac{s1}{s2}=\frac{b}{a}
$$
成立，为了让s1和s2尽可能的小，可以让分子分母同时除以尽可能大的数，因而同出gcd,此时
$$
\frac{s1}{s2}=\frac{b}{a}=\frac{b/gcd}{a/gcd}
$$
可得s1和s2的最小取值为b/gcd和a/gcd;也就是说x,y的所有解分别以b/gcd和a/gcd为周期取值，那么x的最小非负解直观上来看是x%(b/gcd)，但是计算出来的x，y可正可负，因而x%(b/gcd)可能会得到一个负数，即使是负数，x%(b/gcd)的取值范围也是在（-b/gcd，0）的，因而对于任意的数最小非负整数的结果是：(x%b/gcd）+b/gcd)%b/gcd;因而可得1所有的解为：
$$
\begin{cases}x’=x+\frac{b}{\gcd}\times k\y’=y-\frac{a}{\gcd}\times k\\end{cases}（如果k为任意整数）
$$