关于辗转相除法
问题描述：
关于辗转相除法
用辗转相除法求8251与6105的最大公约数
8251=6105*1+2146
6105=2146*2+1813
2146=1813*1+333
1813=333*5+148
333=148*2+37
148=37*4
弱弱的问一下^^为什么说6105与2146的公约数也是8251与6105的公约数?
答
第一个式子左边提取出6105和2146的公约数,设为a,则a必是8251的因子,否则的话,左边右边同时除以a,则右边必是整数,若a不是8251的约数,则右边,也就是说8251/a必然不是整数,左边右边就会矛盾了,无法相等.