欧几里德与扩展欧几里德算法欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b 的最大公约数。基本算法：设 a=qb+r，其中 a，b，q，r 都是整数，则 gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。第一种证明： a可以表示成 a = kb + r，则 r = a mod b 假设 d 是 a,b 的一个公约数，则有d|a, d|b，而 r = a - kb，因此 d|r 因此 d 是(b,a mod b) 的公约数假设 d 是(b,a mod b)的公约数，则d | b , d |r ，但是 a = kb +r 因此 d 也是 (a,b) 的公约数因此 (a,b) 和(b,a mod b) 的公约数是一样的，其最大公约数也必然相等，得证第二种证明：要证欧几里德算法成立，即证: gcd(a,b)=gcd(b,r),其中 gcd 是取最大公约数的意思， r=a mod b 下面证 gcd （a，b）=gcd（b，r ）设 c是 a，b 的最大公约数，即 c=gcd（a，b），则有 a=mc，b=nc，其中 m，n 为正整数，且 m，n 互为质数由 r= a mod b可知， r= a- qb 其中， q 是正整数，则 r=a-qb=mc-qnc= （m-qn）c b=nc,r=(m-qn)c，且 n，（m-qn）互质（假设 n，m-qn 不互质，则 n=xd, m-qn=yd 其中 x,y,d都是正整数，且 d>1 则a=mc=(qx+y)dc, b=xdc,这时 a,b 的最大公约数变成dc，与前提矛盾，所以n ，m-qn一定互质）则 gcd（b,r ）=c=gcd（a,b ）得证。算法的实现：最简单的方法就是应用递归算法，代码如下：1 int gcd( int a, int b) 2 { 3if (b==0) 4return a; 5return6 gcd(b,a%b); 7 } 代码可优化如下：1 int gcd( int a, int b) 2 { 3return b ? gcd(b,a%b) : a; 4 } 当然你也可以用迭代形式：1 int Gcd( int a, int b) 2 { 3while (b != 0) 4 { 5int r = b; 6b = a % b; 7a = r; 8 } 9return a; 10 } 扩展欧几里德算法基本算法：对于不完全为 0 的非负整数 a ，b，gcd（a，b）表示 a ，b 的最大公约数，必然存在整数对 x ，y ，使得 gcd （a，b）=ax+by。证明：设 a>b。1，显然当 b=0，gcd（a，b）=a。此时 x=1 ，y=0；2，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; ...
