中科新闻网蚕的蚕变化过程视频:辗转相除法
来源：百度文库 编辑：中科新闻网 时间：2024/05/09 09:40:06
为什么可以用来计算两数之间最大的公倍数
“辗转相除法”可以方便地找出某数的全部因数。
对于两个数，用“辗转相除法”找出其全部因数后：
相同较小因数的积——最大公约数。
所有较大因数的积——最小公倍数。
这就是“辗转相除法”常用来计算两数之间的“最小公倍数”和“最大公约数”的原因。
如果两个数有最大公约数A，那么这两个数，以及这两个数的差，还有大数除以小数的余数，必然都是A的倍数。
所以当最后两个数刚好能整除时，较小的数就是最大公约数。
辗转相除法又称欧几里得算法。求几个数目较大或不易看出它们的质因数的数的最大公约数，常可采用此法。求两个数的最大公约数一般步骤如下：先用较小的一个数除较大的一个数，得第一个余数；再用第一个余数除较小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个余数去除前一个余数，直到余数是0为止。那么，0之前最后的一个余数就是所求的最大公约数。