关于欧几里得算法和拓展欧几里德定理的证明（不定方程求解方法）

---------------------------------欧几里得算法和拓展欧几里得定理-------------------------------------------------------

欧几里得算法就是

gcd ( a ,b ) == gcd ( b , a%b )

拓展欧几里得定理就是对于ax+by = gcd ( a , b )中a,b为正整数， 那么至少存在一组整数解

--------------------------------欧几里得算法的证明--------------------------------------------------------------------------

欧几里得算法其实就是辗转相除，那么gcd(a,b) == gcd ( b ,a%b )是为什么呢？

设gcd ( a, b ) = d;

那么a = d*p , b = q*d , p和q互质

a%b = a - (a/b)*b = p*d - ( p/q)*q*d = d * ( p - (p/q)*q),

所以当(p/q)*q == p的时候，a已经能够整除b，这个时候我们可以知道b就是最大公约数

但是如果(p/q)*q != p 的时候，也就是p不能够整除q，那么得到了一个更小的数，d*(p-(p/d)*q)，

那么我们只需要证明这个数是一个与q互质即可,

如果gcd ( p - (p/q)*q , q ) != 1, 那么gcd ( p , q ) != 1 , 那么与p和q互质矛盾，所以p-(p/q)*q与q互质

-----------------------------拓展欧几里得定理的证明-----------------------------------------------------------------------

ax + by == gcd ( a , b )

     == gcd ( b , a%b ) (秦九韶算法)

     == b*x1 + ( a - (a/b)*b ) *y1

     == a*y1 + b*(x1 - (a/b)*y1

所以x = y1 , y1 = x1 - (a/b)y1

可以一直递归的加深深度

根据欧几里得算法我们我们可以知道，会到达某一深度的时候，a%b == 0 ,那个时候 axi + byi = b*x(i+1) == gcd ( 0 , b ) == b ,所以 yi == x(i+1) == b , xi == 0

所以回溯计算，就能够得到不定方程额一个解。

--------------------------不定方程利用exgcd进行求解---------------------------------------------------------------------------

那么对于普通的ax+by == c 的情况，我们应该如何求解呢？

x1=x*(c/gcd(a,b)),y1=y*(c/gcd(a,b))

为什么呢？

就是方程左右两边同时扩大c/gcd(a,b)倍，原方程依旧相等

--------------不定方程的通解的求取----------------------------------------------

d=gcd(a,b). 那么x=x0+b/d*t; y=y0-a/d*t;其中t为任意常整数。

很容易想，不做赘述！！！！