最小公倍数
| 公倍数 | |
|---|---|
| 术语名称 | 公倍数 |
| 英语名称 | common multiple |
| 最小公倍数 | |
|---|---|
| 术语名称 | 最小公倍数 |
| 英语名称 | least common multiple |
| 别名 | LCM, smallest common multiple |
公倍数(common multiple)指两个整数公共的倍数。
最小公倍数(least common divisor)指两个整数之间最小的正的公因数。
定义
| 最小公倍数 | |
|---|---|
| 运算名称 | 最小公倍数 |
| 运算符号 | [math]\displaystyle{ \operatorname{lcm}(\bullet,\bullet) }[/math],[math]\displaystyle{ [\bullet,\bullet] }[/math] |
| Latex | \operatorname{lcm}
|
| 运算对象 | 非零整数 |
| 运算元数 | 2 |
| 运算结果 | 自然数 |
| 定义域 | [math]\displaystyle{ \mathbb{Z}^*\times\mathbb{Z}^* }[/math] |
| 陪域 | [math]\displaystyle{ \mathbb{N}^* }[/math] |
对两个非零整数 [math]\displaystyle{ a, b }[/math] ，其公共的倍数 [math]\displaystyle{ m }[/math] 满足 [math]\displaystyle{ a \mid m, b \mid m }[/math] 称为整数 [math]\displaystyle{ a, b }[/math] 的公倍数(common multiple)。 正的公倍数一定存在，因此其中必然存在最小的正整数，称为整数 [math]\displaystyle{ a, b }[/math] 的最小公倍数(least common multiple, LCM)，记作 [math]\displaystyle{ \operatorname{lcm}(a, b) }[/math] 或 [math]\displaystyle{ [a,b] }[/math] 。
注：虽然 [math]\displaystyle{ [a, b] }[/math] 比较简洁，但这个记号相当滥用了，本 wiki 主要用这个记号标记闭区间。
一般地，对多个非零整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] ，其公共的倍数 [math]\displaystyle{ m }[/math] 满足 [math]\displaystyle{ a_1 \mid m, a_2 \mid m, \dots, a_n \mid m }[/math] ，则称其为整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 的公倍数。 正的公倍数一定存在，因此其中必然存在最小的正整数，称为整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 的最大公因数，记作 [math]\displaystyle{ \operatorname{gcd}(a_1, a_2, \dots, a_n) }[/math] 。
特别地，对 [math]\displaystyle{ ab=0 }[/math] 的情况，最小公倍数没有定义。
性质
- 定义直接推论
- 对于一个元素的整数列 [math]\displaystyle{ a_1 }[/math] ，最小公倍数是 [math]\displaystyle{ \operatorname{lcm}(a_1) = |a_1| }[/math] ；
- 多元最小公倍数是交换的： [math]\displaystyle{ \operatorname{lcm}(a_1,a_2,\dots,a_i,\dots,a_n) = \operatorname{lcm}(a_i,a_2,\dots,a_1,\dots,a_n) }[/math] ；
- 符号不影响最小公倍数，即 [math]\displaystyle{ \operatorname{lcm}(a_1,a_2,\dots,a_n) = \operatorname{lcm}(-a_1,a_2,\dots,a_n) = \operatorname{lcm}(|a_1|,a_2,\dots,a_n) }[/math] ；
- 若这些数中存在整除关系，由交换性不妨设 [math]\displaystyle{ a_1 | a_2 }[/math] ，有 [math]\displaystyle{ \operatorname{lcm}(a_1,a_2,a_3,\dots,a_n) = \operatorname{lcm}(a_2,a_3,\dots,a_n) }[/math] 。
- 特殊值
- 对正整数 [math]\displaystyle{ a }[/math] ，有 [math]\displaystyle{ \operatorname{lcm}(a, a) = a }[/math] ；对非零整数 [math]\displaystyle{ a }[/math] ，则是 [math]\displaystyle{ \operatorname{lcm}(a, a) = |a| }[/math] 。
- 对整数 [math]\displaystyle{ a, b }[/math] 和整数 [math]\displaystyle{ m }[/math] ，有 [math]\displaystyle{ a \mid m \land b \mid m \rightarrow \operatorname{lcm}(a, b) \mid m }[/math] 。
- 可推广到任意个数。这是最小公倍数的本质，按整除的偏序关系，是所有“大于”这些数的数中的“最小”的，且取其中正的那个。
- [math]\displaystyle{ \operatorname{lcm}(ma, mb) = |m| \operatorname{lcm}(a, b) }[/math]
- 完全分配格
- 交换性： [math]\displaystyle{ \operatorname{lcm}(a, b) = \operatorname{lcm}(b, a) }[/math]
- 结合性： [math]\displaystyle{ \operatorname{lcm}(\operatorname{lcm}(a, b), c) = \operatorname{lcm}(a, \operatorname{lcm}(b, c)) }[/math]
- 对偶运算： [math]\displaystyle{ \operatorname{gcd}(a, b) }[/math]
- 吸收率： [math]\displaystyle{ \operatorname{lcm}(a, \operatorname{gcd}(a, b)) = a }[/math]
- 分配性： [math]\displaystyle{ \operatorname{lcm}(a, \operatorname{gcd}(b, c)) = \operatorname{gcd}(\operatorname{lcm}(a, b), \operatorname{lcm}(a, c)) }[/math]
- 与标准质因数分解的关系： [math]\displaystyle{ a = p_1^{s_1} p_2^{s_2} \dots p_n^{s_n}, b = p_1^{t_1} p_2^{t_2} \dots p_n^{t_n} \rightarrow \operatorname{lcm}(a, b) = a_1 = p_1^{\max \{s_1, t_1\}} p_2^{\max \{s_2, t_2\}} \dots p_n^{\max \{s_n, t_n\}} }[/math]
- [math]\displaystyle{ \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = |ab| }[/math]
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |