题目

用流程图表示：求两个数的最大公约数

提问时间：2020-11-20

答案

不妨设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