“辗转相除法”是怎么用的?书上有个例子：8251与6105的最大公约数.8251=6105*1+2146“由此可得,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105的公约数也是6105与2146的公约数,所以他们

Question

“辗转相除法”是怎么用的?
书上有个例子：8251与6105的最大公约数.
8251=6105*1+2146
“由此可得,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105的公约数也是6105与2146的公约数,所以他们的最大公约数相等”.
为什么?

Answer 1

用辗转相除法求8251和6105的最大公约数
第一步 用两数中较大的数除以较小的数,求得商和余数
8251=6105*1+2146
由上式可知6105和2146的公约数也是8251和6105的公约数所以它们的最大公约数相等.
第二步 对6105和2146重复第一步的做法
6105=2146*2+1813
同理2146和1813的最大公约数也是6105和2146的最大公约数.
重复以上步骤：
2146=1813*1+333
1813=333*5+148
333=148*2+37
148=37*2
显然37是148和37的最大公约数,也就是8251和6105的最大公约数.
按照上述步骤再举例子进行巩固.