当前位置: article > 正文

碾转相除求最大公约数最大公倍数_辗转相除法求最大公倍数

作者：我家自动化 | 2024-06-02 11:55:07

踩

辗转相除法求最大公倍数

关键词:求最大公约数

在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题yⅠ和Ⅱ）中，而在中国则可以追溯至东汉出现的《九章算数》。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 / 105 = 2余42，所以105和42的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21 = 5 × 105 + （−2） × 252。这个重要的等式叫做贝祖等式。

比如求10000和115的最大公约数，不用把因数一个一个找出来，只要按以下做法就行了：

15000÷115=130……50

115÷50=2……15

50÷15=3……5

15÷5=3

它们的公约数是5.

求a和b的最大公倍数

a*b/最大公约数

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/662608

碾转相除求最大公约数 最大公倍数_辗转相除法求最大公倍数

碾转相除求最大公约数最大公倍数_辗转相除法求最大公倍数