最小公倍数
| 公倍数 | |
|---|---|
| 术语名称 | 公倍数 |
| 英语名称 | common multiple |
| 最小公倍数 | |
|---|---|
| 术语名称 | 最小公倍数 |
| 英语名称 | least common multiple |
| 别名 | LCM, smallest common multiple |
公倍数(common multiple)指两个整数公共的倍数。
最小公倍数(least common multiple)指两个整数之间在整除意义上最小的正的公倍数。
定义
最小公倍数有两种不等价的定义，分别属于整除的两个定义体系。但形式上的区别仅在于整数是否非零。 前一种定义不允许出现 0 ，在数论教材中更常见；后一种定义基于整除关系的乘法定义，有更良好的性质，在抽象代数中更常见。本 wiki 中将按照后一种定义讨论。
不含 0 的定义
| 最小公倍数 | |
|---|---|
| 运算名称 | 最小公倍数 |
| 运算符号 | [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{ \min \{m\mid m\gt 0 \land a\mid m\land b\mid m \} }[/math] ，称为非零整数 [math]\displaystyle{ a, b }[/math] 的最小公倍数(least common multiple, LCM)，记作 [math]\displaystyle{ \operatorname{lcm}(a, b) }[/math] 或 [math]\displaystyle{ [a,b] }[/math] 。
特别地，对 [math]\displaystyle{ ab=0 }[/math] 的情况，认为最小公倍数没有定义。
含 0 的定义
| 最小公倍数 | |
|---|---|
| 运算名称 | 最小公倍数 |
| 运算符号 | [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{ M=\{m\mid m\geq 0 \land a\mid m\land b\mid m \} }[/math] ，存在整除关系下的最小元，即 [math]\displaystyle{ (\exists m \in M)(\forall m'\in M)(m|m') }[/math] ，称为整数 [math]\displaystyle{ a, b }[/math] 的最小公倍数(least common multiple, LCM)，记作 [math]\displaystyle{ \operatorname{lcm}(a, b) }[/math] 或 [math]\displaystyle{ [a,b] }[/math] 。
特别地，对 [math]\displaystyle{ ab=0 }[/math] 的情况，由于 [math]\displaystyle{ 0|x \rightarrow x=0 }[/math] ，一定有 [math]\displaystyle{ M=\{0\} }[/math] ，因此 [math]\displaystyle{ \operatorname{lcm}(a,b)=0 }[/math] 。
相关定义
虽然 [math]\displaystyle{ [a, b] }[/math] 比较简洁，但这个记号相当滥用了，本 wiki 主要用这个记号标记闭区间，一律用 [math]\displaystyle{ \operatorname{lcm}(a, b) }[/math] 表达最小公倍数。
一般地，对多个非零整数 [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{lcm}(a_1, a_2, \dots, a_n) }[/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) = 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]