欧几里得算法证法二假设c = gcd(a,b),则存在m,n，使a = mc, b = nc;令r = a mod b，即存在k，使r = a-kb = mc - knc = (m-kn)c;故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)c;则c为b与a mod b的公约数;假设d = gcd(n,m-kn), 则存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc;由于gcd(a,b) = c, 故d = 1;即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;故得证gcd(a,b) = gcd(b,a mod b).注意:两种方法是有区别的
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
