扩展欧几里德算法简单证明数学

扩展欧几里德算法顾名思义，扩展欧几里德算法（Extended Euclidean algorithm）是在欧几里德（Euclidean algorithm）——（也就是辗转相除法）的基础上扩展得来的。
算法要求得出一个整数解x和y，使得a * x + b * y = gcd(a,b).
先简单说一下欧几里德算法：对于求解两个整数a，b（a>b）的最大公约数gcd(a,b)问题，等价于求解gcd(b,a mod b)，也就是说，（划重点）gcd(a,b) == gcd(b,a mod b)
这里就不给出证明了
gcd递归实现代码1：

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

gcd递归实现代码2(简化)：

int gcd(int a,int b){ return b!=0 ? gcd(b,a%b) : a; }

gcd非递归实现：

int gcd(int a,int b){ while(b){ int t = a; a = b; b = t%b; } return a; }

接下来我们直接利用上面的结论来证明扩展欧几里德算法
证明： 1 ：当 b = 0 时，显然 g c d ( a , b ) = a ，并且此时 x = 1 ， y = 0 1：当b=0时，显然gcd(a,b) = a，并且此时x=1，y=0 1：当b=0时，显然gcd(a,b)=a，并且此时x=1，y=0 2 ：当 b ≠ 0 时，假设： a ? x 1 + b ? y 1 = g c d ( a , b ) ， b ? x 2 + ( a % b ) ? y 2 = g c d ( b , a % b ) 把 a % b = a ? ( a / b ) ? b 和 g c d ( a , b ) = g c d ( b , a % b ) 代入得到： a ? x 1 + b ? y 1 = b ? x 2 + [ a ? ( a / b ) ? b ] ? y 2 a ? x 1 + b ? y 1 = a ? y 2 + b ? [ x 2 ? ( a / b ) ? y 2 ] \\2：当b\neq0时，假设：a\cdot x1+b\cdot y1 =gcd(a,b) ，b\cdot x2+(a\%b)\cdot y2 = gcd(b,a\%b)\\把a\%b=a-(a/b)*b 和 gcd(a,b) = gcd(b,a\%b)代入得到：\\a\cdot x1+b\cdot y1 = b\cdot x2+[a-(a/b)*b]\cdot y2 \\ a\cdot x1+b\cdot y1=a\cdot y2+b\cdot [x2-(a/b)\cdot y2] 2：当b??=0时，假设：a?x1+b?y1=gcd(a,b)，b?x2+(a%b)?y2=gcd(b,a%b)把a%b=a?(a/b)?b和gcd(a,b)=gcd(b,a%b)代入得到：a?x1+b?y1=b?x2+[a?(a/b)?b]?y2a?x1+b?y1=a?y2+b?[x2?(a/b)?y2]
这样可以推导出 x 1 = y 2 ， y 1 = [ x 2 ? ( a / b ) ? y 2 ] 将 b = 0 的情况作为递归基，不断递归算出 x 和 y 这样可以推导出x1=y2，y1=[x2-(a/b)\cdot y2] \\ 将b=0的情况作为递归基，不断递归算出x和y 这样可以推导出x1=y2，y1=[x2?(a/b)?y2]将b=0的情况作为递归基，不断递归算出x和y
容易得出递归是有穷的，因为辗转相除是有穷的，递归到最后b肯定会变成0.
递归实现：

void extgcd(int a,int b,int &x,int &y){ if(b==0){ x = 1; y = 0; return; } extgcd(b,a%b,x,y); int x1 = x,y1 = y; x = y1; y = x1 - (a/b) * y1; }

非递归实现比递归实现麻烦太多，就不写出来了

关于扩展欧几里德算法的时间复杂度：
看一下递归方法就能知道，扩展欧几里德算法和辗转相除法的复杂度一样，复杂度在 O(log max(a,b)) 以内
证明：
如果ab
在a>b的情况下，函数按gcd(a,b) => gcd(b,a%b) => gcd(a%b,b%(a%b))递归下去
当b>a/2时：a%b=a-b 当b 可以发现每两次递归之后第一个参数一定会小于原来的一半。
【扩展欧几里德算法简单证明】关于a * x+b * y = gcd(a,b)解的大小：
结论：|x|<=b 且 |y|<=a
利用归纳法来证明：
①在b=0的前一步，即a%b=0时有x=1且y=1，结论显然成立
②假设对于调用(b , a%b , x , y )后得到的x1和y1
存在 |x1|<=a%b，|y1|<=b
则 |x| = |y1| <= b，|y| = |x1-(a/b)*y1|<=|x1|+(a/b)|y1|<=a%b+(a/b)*b=a