欧几里得定理和扩展欧几里得定理

本人数学菜语文菜所以很多证明过程写的肯定是有不严谨甚至很不严谨的地方，希望你能感性理解或者去别人的博客里理解一下！

欧几里得定理

问题提出

给您两个数\(a,b\)，让您求出它们的最大公因数，你怎么办？

想必你会从这几种方法中做出选择：

1. 最暴力的从1枚举到\(min(a,b)\)检查是否为\(a,b\)公因数的毒瘤做法
2. 稍微优化了一些常数但没有什么卵用的从1枚举到\(\frac{min(a,b)}{2}\)的奇葩做法
3. 辗转相减法
4. 欧几里得定理

显而易见，他们的优秀程度是递增的。其中，方法①、②的复杂度是\(O(n)\)，②只不过是把①常数对半砍了，方法③的复杂度如果优化到极限似乎也是\(O(log_2n)\)，但朴素的方法③最差会是\(O(n)\)，而方法④的最差复杂度是可爱的严格\(O(log_2n)\)，稍后我将给出证明。这意味着欧几里得定理的算法理论上是最快的。那么我们步入正题：

算法

欧几里得定理这个东西对于高中生应该是非常熟悉的（见必修三第一章）。具体的操作方式也是非常简单：

1. 用较大数对较小数做带余除法
2. 用较小数和上一步的余数再进行第1步运算
3. 当余数为0时，较小数极为两数的最大公约数

写成代码出来更是十分的简短：

代码

int GCD(int a,int b){
	return a%b?GCD(b,a%b):b;
}

如果再把换行一压，就是一行的事情，如此简单。那么我们来证明一下为什么可以这样做。

证明

算法正确性证明

让我们倒过来想。在\(!a\%b\)时意味着此时b为a的因数。而向上一层想，此处的a,b分别是上一层的b和a%b，为了便于区别不妨把上一层的a,b分别重命名为x,y。很明显我们可以得出来这样的式子：

$$
a=kb\\
a=y\\
b=x\%y\\
x=ky+x\%y=ka+b=k’b+b=Kb
$$

所以b一定是x和y的公约数，再向上一路如此回去，易证b时\(x_0,y_0\)的公约数。而为什么b就是最大的？假设有比b更大的公约数b’，那么在不断递归的过程中，当\(a\%b=b’\)时，即会停止递归，则不会到达b，又：b是在递归到a%b=b时得到的结果，假设与条件相矛盾。因此b一定是 \(x_0,y_0\)的最大公约数了！

算法复杂度证明

前面我们提到辗转相除法的最差复杂度是严格的\(O(log_2n)\)，为什么呢？

因为对于初始的两个数\(a,b\)（不妨设a>b），a%b必然小于\(\frac{a}{2}\)（想一想，为什么）

这个其实很容易想明白，但需要一个小小的分类讨论：首先设r=a%b

①\(b<\frac{a}{2}\)，那么a对b做带余除法得到的\(r\)一定严格小于\(b\)
②\(b=\frac{a}{2}\)，a是b的2倍，r=0
③\(b>\frac{a}{2}\)，那么a对b做带余除法商一定为1，而\(r=a-b<\frac{a}{2}\)

因此每进行一层的深入，a都会变成一个严格小于上一层的a的一半的数。因此其最差复杂度为严格的\(O(log_2n)\)。

举个例子说吧：

如何用辗转相除法计算268和1024的最大公约数：

由于1024>268所以1024放前面！

1. 1024=268*3+220
2. 268=220*1+48
3. 220=48*4+28
4. 48=28*1+20
5. 28=20*1+8
6. 20=8*2+4
7. 8=4*2

由此，在七步的运算中我们求出了268和1024的最大公约数为4. 不妨计算一下理论上的最差步数\(log_21024=10>7\)，确实\(log_2n\)是最差情况下的复杂度。

扩展欧几里得定理

由于偷懒，所以后文中我就把扩展欧几里得定理简称为扩欧了！

知识补充：裴蜀定理 （Bézout’s identity）

内容： 如果a、b是整数，那么一定存在整数x、y使得\(ax+by=GCD(a,b)\)

裴蜀定理的简单证明

这里我们证明的方法就是证明 \(不定方程ax+by=c有解的充要条件是c=k*GCD(a,b)\)（想一想，为什么）。
为了便于证明的书写我们不妨先 #define d GCD(a,b)
//证明中所有的k,q,p∈\(N^*\)

必要性证明：

使用反证法：

假设c不是GCD(a,b)的整数倍，那么一定有\(c=pd+q\)

因为d=GCD(a,b)，易知\(a=k_1d , b=k_2d\)

原式\(ax+by=c\)可化为\(k_1d*x+k_2d*y=pd+q\)

若b=0，则原式可化为\(ax=c，则c=ka=k*GCD(a,0)\)

若b≠0，在等式左右两边同时除以d，原式变为$$k_1x+k_2y=p+\frac{q}{d}$$显然\(\frac{q}{d}\not\in Z\)，原方程无解，与有整数解的假设相矛盾，因此只有当\(c=k*GCD(a,b)\)时，原方程有整数解

在c=GCD(a,b)时， \(易证ax+by=GCD(a,b)一定有整数解x,y\)
//我没有给出证明方法，但是这里百度百科写的还可以https://baike.baidu.com/item/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86/5186593?fr=aladdin#2

证毕！

充分性证明：

已知\(ax+by=d\)一定有整数解，设其解为\((x_0,y_0)\)。由于d∣c，则存在k∈Z，使得\(c=kd=k(ax+by)=a(kx)+b(ky)\)，即解为\((kx_0,ky_0)\)。

证毕！

算法

有了裴蜀定理，那么不难想到有一种特殊的情况，即\(ax+by=1\)的情况，此时要使方程有整数解，则GCD(a,b)=1，即a与b互质。但是在做题的过程中，对于任意的\(ax+by=m\)我们往往不仅需要求出其是否有整数解，还需要知道整数解是谁，这时就需要用到扩欧。

扩欧的主体还是基于辗转相除法的，比如扩欧求乘法逆元的代码还是很简短：

int exGCD(int a,int b,int &x,int &y){  
     if(b==0){  
         x=1;  
         y=0;  
         return a;  
     }  
     int ans=exGCD(b,a%b,x,y);  
     int tmp=x;  
     x=y;  
     y=tmp-a/b*y;
     return ans;
 }  

嘤！