最大公约数与最小公倍数

另见:质数

最大公约数最大公因数最大公因子,英语:Greatest Common Divisor,简写为GCD)是几个自然数公有约数中最大的一个。例如,16和40公约数有:1、2、4、8, 其中最大的是8,8就是16和40的最大公约数。找出最大公约数有助于将分数约简到最简形式。后面我们将介绍如何找最大公约数

最小公倍数(英语:Lowest Common Multiple,简写为LCM)是几个自然数公有公倍数中最小一个。 例如,5和6公倍数有:30、60、90、⋯⋯其中最小的是30,30就是5和6的最小公倍数。后面我们将介绍如何找最小公倍数

你可以用下面的计算器求出两或三个自然数的最大公约数和最小公倍数。

请输入两或三个正整数

若发现任何错误,请发送电子邮件到[email protected]。在此表示感谢!



如何求最大公约数

求最大公约数其实有很多方法,以下将介绍比较常见的三种:

例如,求24和60的最大公约数。


分解质因数法

该方法要先将两数分别分解质因数。怎样分解质因数,请见质因数分解页。

24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5

找出这两个数的公有质因数。

24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5

它们的公有质因数分别为2,2,3。24和60的最大公约数就是这几个公有质因数的乘积,也即2 × 2 × 3 = 12


短除法

首先用最小公约数去除这两个数。24和60的最小公约数是2

224 60
 12 30

继续使用这种方法对所得到的商进行分解,直到所得到的商互质为止

224 60
212 30
36  15
 2  5

将左边的数字连乘,所得到的乘积就是最大公约数。以上24和60的最大公约数就是2 × 2 × 3 = 12


辗转相除法(欧几里德算法)

该方法就是通过将要寻找最大公约数的两个数字进行重复除法,直到最后得到余数为0

下面我们就用辗转相除法来找出24和60的最大公约数:

下面我们再看一个例子:试找出40和64的最大公约数


如何求最小公倍数

下面介绍几种比较常用的方法:

例如,求24和60的最小公倍数。


质因数分解

使用该方法寻找最小公倍数,先将这几个数字分解质因数并写成幂的形式。怎样分解质因数,请见质因数分解页

24 = 23 × 3
60 = 22 × 3 × 5

各质因数的最高次幂的乘积就是所要求的最小公倍数。因此,示例中24和60的最小公倍数就是23 × 3 × 5 = 120


短除法

首先用最小公约数去除这两个数。24和60的最小公约数是2

224 60
 12 30

继续使用这种方法对所得到的商进行分解,直到所得到的商互质为止

224 60
212 30
36  15
 2  5

将所有的公约数及最后的商相乘,所得积就是最小公倍数。以上24和60的最小公倍数就是2 × 2 × 3 × 2 × 5 = 120


公式法

在已经算出整数ab的最大公约数的基础上,我们可以通过下面的公式来求出它们的最小公倍数:

LCM(a,b) =a × b
GCD(a,b)


回到刚才的例子,我们可以求得24和60的最小公倍数:

LCM(24,60) =24 × 60 = 120
12

当然,如果已经知道最小公倍数,你也可以运用这个方法算出最大公约数。

Jimmy Sie(著)
Amanda Huang(译)

返回页首

另见:质数