耐心的看下去终究会懂的。
♦ 我们规定gcd(a,0)=a
♦ 欧几里德算法中需要明确的是，gcd(a,b) = gcd(b,r)
证明：设x=gcd(a,b)，那么b能整除以x（即b/x没有余数，觉得"整除以"比"整除"更直观，下同）。
∵a=bq+r
∴r=a-bq
∴r能整除以x
∴x为b,r的公约数（没有证明是最大）
假设y为gcd(b,r)，所以x≤y（y是最大的约数！）
显然，b能整除以y
∵a=bq+r
∴a能整除以y.
∴y是a,b的约数
∴y≤x
∴x=y=gcd(b,r)
∴gcd(a,b) = gcd(b,r)
求两个数的最大公约数——辗转相除法（欧几里德算法）
1 int gcd(int a, int b) 2 { 3 if(a < b) swap(a,b); 4 5 int r = a%b; 6 7 while (r) 8 { 9 a = b; 10 b = r; 11 r = a%b; 12 } 13 14 return b; 15 }
给定a,b,c，求满足ax+by=gcd(a,b)的整数解(x,y)——扩展欧几里德算法
1 int extended_gcd(int a, int b, int &x, int &y) 2 { 3 if (a < b) swap(a,b); 4 5 if (b == 0) 6 { 7 x = 1, y = 0; 8 return a; 9 } 10 11 int p,q; 12 13 int ans = gcd(b, a%b, p, q); 14 15 x = q; 16 17 y = p - a/b*q; 18 19 return ans; 20 }
♦ 假设给定a,b. 那么我们知道a,b的最大公约数必定可以表示成a,b的线性组合,ax+by=gcd(a,b),问题是x,y是多少呢？
证明：已知a%b=r,gcd(a,b)=ax+by(x,y未知)
∵gcd(a,b)=gcd(b,r)
∴gcd(b,r) = bp+rq = bp+(a%b)q = bp+(a-a/b*b)q = aq+b(p-a/b*q)
即ax+by = gcd(a,b) = aq+b(p-a/b*q)
解得x=q, y=p-a/b*q;
ok,到这里为止,我们得到ax+by=gcd(a,b)的一组解, x和y。
♦ 那么不失一般性，给定a,b,c，ax+by=c的解又怎么求呢？
思路：等式两边同时乘以gcd(a,b)/c
假设ax+by=gcd(a,b)的解为x0,y0.则x=x0*c/gcd(a,b),y=y0*c/gcd(a,b)