答案解析

查看更多优质解析解答一举报　　最简单的算公约数的方法叫做：辗转相除法.

　　比如求145和25的公约数　　先用145减去25的若干倍,

使得减剩下的数比25小.

也就是145-5乘以25=20.

　　然后只需要求25和20的公约数,

重复上述过程：　　用25减去20的若干倍,

使得减剩下的数比20小.

也就是25-20=5.

　　然后只需要求20和5的公约数,

显然是5.

　　当然,

还可以继续一步,

就是20-4乘以5=0.

到0了,

因为0不能做公约数,

所以之前的那个5就是公约数.

　　这个原理很简单,

假设x和y的公约数是a,

那么y,

x都能被a整除,

从而y-kx能被a整除,

k是某个正整数.

　　于是a也是x与y-kx的公约数.

因为越小的数,

越容易看出来公约数,

而y-kx比y小.

更多推荐