辗转相除的原理是?题：求204和85的最大公约数解：204/85=2……3485/34=2……1734/17=2……0所以17是最大公约数问：为什么?能不能证出来?

Question

辗转相除的原理是?
题：求204和85的最大公约数
解：204/85=2……34
85/34=2……17
34/17=2……0
所以17是最大公约数
问：为什么?能不能证出来?

Answer 1

辗转相除法的证明
设两数为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 的最大公约数.