最大公约数与最小公倍数
时间: 2024-11-13 14:08:20
最大公约数（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 也是一个很高效的方式。
