辗转相除法的证明
设两数为a、b(b<a),求它们最大公约数的步骤如下:用b除a,得a=bq+r(0≤r<b)(q是这个除法的商).若r=0,则b是a和b的最大公约数.若r≠0,则继续考虑.
首先,应该明白的一点是任何a和b的公约数都是r的公约数.要想证明这一点,就要考虑把r写成r=a-bq.现在,如果a和b有一个公约数d,而且设a=sd,b=td,那么r=sd-tdq=(s-tq)d.因为这个式子中,所有的数(包括s-tq)都为整数,所以r可以被d整除.
对于所有的d的值,这都是正确的;所以a和b的最大公约数也是b和r的最大公约数.因此我们可以继续对b和r进行上述取余的运算.这个过程在有限的重复后,可以最终得到r=0的结果,我们也就得到了a和b的最大公约数.