如何证明展转相除法求两个数的最大公约数

不妨设a≥b,记(a,b)为a与b的最大公约数

令c=(a,b),d=(b,a mod b)=(d, a-qb),其中q=floor(a/b)为不大于a/b的最大整数
1) c|a且c|b故c|(a-qb), 则有c|(b,a-qb)=d
2) d|b且d|(a-qb),设ud=b, vd=a-qb, 则有a=vd+qb=(v+qu)d，即d|a, 故d|(a,b)=c
综上，c=d，即(a,b)=(b,a mod b)

由于a mod b是严格递减的，所以辗转相除最终可以收敛
(a,b)=(b,a mod b)=...=(c,0)=c