简述：a>b gcd表示最大公约数
试图证明 a = kb + r 且 gcd(a,b)==gcd(b,r)
a可以表示成a = kb + r ---------a，b，k，r皆为正整数
假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。跳转至1、
而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r因此d也是b,r的公约数。跳转至2、
因(a,b)和(b,r)的公约数相等，则其最大公约数也相等，得证。跳转至3、
1、 证明r是整数
a/d-bq/d=int
则r/d=int
2、 证明有相同公约数
以上显然得出 a,b与b,r 有相同公约数d
3、证明相同公约数是最大的
我们假设d不是最大公约数， a,b 有公约数e>d
a/e-bq/e=int => r/e=int
显然矛盾
则e==d d是最大公约数
4、推导到广泛意义的最大公约数
令a>=b r0=a、r1=b
r0=(((rn*qn*qn-1+rn)qn-2).....r3)q1+r2 -----------1
为方便对比
a = bq +r
显然1是一个嵌套，其中bq==(((rn*qn*qn-1+rn)qn-2).....r3)q1 可以依次像洋葱一样剥开公式
则 r0---r1-----r2-------rn 拥有相同公约数rn.
gcd(a,b)=gcd(r0,r1)=.....gcd(rn-1,rn)=gcd(rn,0)=rn
例子: rn-2 rn-1 q rn 相同公约数
248= 166* 1+ 82 2
166= 82* 2+ 2 2
82= 2* 41 2
版权声明：本文为lan_666原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。