Question

求最大公约数为什么可以用求余数的方法

Answer 1

比如对正整数A和B，假设其最大公约数为C，则可设A=pC，B=qC，p，q互素；
则辗转相除法为：A(i+1)=ri=Ai-KiBi，B(i+1)=Bi或B(j+1)=rj=Bj-HjAj，A(i+1)=Ai;
可以发现右边每一个单项式中都有一个Ai或Bi,而假设Ai,Bi都是C的倍数，则：
A(i+1)，B(i+1)都是C的倍数，所以可以把每个式子都除以C,结果再乘上C；
而：A/C=p，B/C=q，所以只要证明p，q经过辗转相除法得到结果1就好了；
而对两个互素的数，由于r(i+1)<ri<min{Ai,Bi}，而两个互素的数相减肯定不是0，所以最后一定会变成1，再乘上C，得证。