最大公约数与最小公倍数
时间: 2024-12-02 16:46:55
最大公约数(Greatest Common Divisor,GCD)和最小公倍数(Least Common Multiple,LCM)是数学中两个重要的概念,通常用于整除和倍数的运算。以下是它们的定义和计算方法:
1. 最大公约数 (GCD)
- 定义:最大公约数是能够同时整除给定一组整数的最大的正整数。
- 计算方法:
- 枚举法:列出所有数的约数,找出共同的约数中最大的一个。
- 辗转相除法:使用欧几里得算法,通过反复取余的方法来计算。
辗转相除法的步骤:
- 设有两个数 $a$ 和 $b$($a > b$),则 $GCD(a, b) = GCD(b, a \mod b)$。
- 直到 $b = 0$ 时,此时的 $a$ 即为 $GCD(a, b)$。
例子:
计算 48 和 18 的最大公约数:
- 48 的约数:1, 2, 3, 4, 6, 8, 12, 16, 24, 48
- 18 的约数:1, 2, 3, 6, 9, 18
- 共同约数是:1, 2, 3, 6
- 所以,最大公约数 $GCD(48, 18) = 6$。
2. 最小公倍数 (LCM)
- 定义:最小公倍数是能够被给定一组整数整除的最小的正整数。
- 计算方法:
- 枚举法:列出所有数的倍数,找出共同的倍数中最小的一个。
- 与 GCD 的关系:可以通过最大公约数计算最小公倍数:
$ LCM(a, b) = \frac{a \times b}{GCD(a, b)} $
例子:
计算 12 和 15 的最小公倍数:
- 12 的倍数:12, 24, 36, 48, 60, 72, ...
- 15 的倍数:15, 30, 45, 60, 75, ...
- 共同倍数是:60, 120, ...
- 所以,最小公倍数 $LCM(12, 15) = 60$。
也可以用 GCD 计算:
- 首先计算 $GCD(12, 15) = 3$。
- 然后用公式:
$ LCM(12, 15) = \frac{12 \times 15}{GCD(12, 15)} = \frac{180}{3} = 60 $
总结
- 最大公约数:找出同时整除给定数的最大数。
- 最小公倍数:找出能被给定数整除的最小数。
- 使用 GCD 计算 LCM 也是一个很高效的方式。