辗转相除法的原理是什么?请说的能看懂,

1个回答

  • 那我就按照你给的这个例子具体来说吧:

    8251=6105+2146,为了表示简单,我就用a=b+c表示这个吧

    于是有c=a-b

    那么如果有d|a,且d|b,就必然有d|a-b,也就是d|c,

    可见a和b的公约数必然也是c的约数.

    现在假设d是a,b的最大公约数,那么d也必然是c的约数,于是d是b,c的公约数,现在就要证明它是最大公约数——

    因为a=b+c,于是b,c的公约数也必然是a的约数,假设(b,c)=e,(根据"d是b,c的公约数"知道d|e)那么有e|b+c,即e|a,可见e也是a,b的公约数,e|d,综上有e=d

    可见(a,b)=(b,c)=d

    这个思想一推广,就成了辗转相除法了.

    说的够明白吧?.