最大公约数和最小公倍数
基本定义
最大公约数
最大公约数的英文为：\(\text{Greatest Common Divisor}\)，我们通常简写为 \(\gcd\)。
对于两个整数 \(a,b\)，他们的最大公约数 \(\gcd(a,b)\) 定义为：
- 同时整除 \(a,b\) 的正整数中最大的那一个。
形式化一点说，\(d = \gcd(a,b)\) 当且仅当：
- \(d \mid a\) 且 \(d \mid b\)
- 如果 \(c \mid a\) 且 \(c \mid b\)，那么 \(c \mid d\)
通常我们约定 \(\gcd(a,0) = |a|\)， 而对于 \(\gcd(0,0)\) 是没有定义的， 是一个 \(\text{typically not defined}\) 的问题， 在大多数情况下不会出现。 具体我会单独写一篇文章进行总结（坑）。
在记号方面，我们通常有如下写法：
最小公倍数
对于两个非零整数 \(a,b\)，它们的最小公倍数 \(\operatorname{lcm}(a,b)\) 定义为：
- 同时被 \(a,b\) 整除的正整数中最小的那个。
形式化地说，\(m = \operatorname{lcm}(a,b)\) 当且仅当：
- \(a\mid m\) 且 \(b\mid m\)；
- 如果 \(a\mid n\) 且 \(b\mid n\)，那么 \(m\mid n\)。
在记号方面，我们通常有如下写法：
多个数的 gcd 和 lcm
多个数的情况，通常以二元为基础，用结合律递归定义：
这种定义依赖于结合律，同时也体现出 \(\gcd\) 和 \(\operatorname{lcm}\) 是一种运算， 而并非单纯的函数值。
gcd / lcm 是「整除」的交集与并集
要更深入一步去理解 \(\gcd\) 和 \(\operatorname{lcm}\)， 一个非常重要的视角是：将「整除关系」视为一个偏序关系。
对正整数集合 \(\mathbb{N}^+\)，定义关系 \(a\preceq b \iff a\mid b\)。
可以验证三个性质：
- 自反性：\(a\mid a\)；
- 反对称：\(a\mid b\) 且 \(b\mid a \Rightarrow a=b\)；
- 传递性：\(a\mid b\) 且 \(b\mid c \Rightarrow a\mid c\)。
因此，\(\mid\) 在正整数集合上是一个偏序关系。
在这个偏序中，我们可以重新解读定义：
-
\(\gcd(a,b)\) 是这样的一个元素 \(d\)：
-
- \(d\preceq a\)、\(d\preceq b\)（是 \(a,b\) 的下界）；
-
- 并且所有 \(a,b\) 的下界中，\(d\) 是最大的（最大下界）。
-
\(\operatorname{lcm}(a,b)\) 是这样的一个元素 \(m\)：
-
- \(a\preceq m\)、\(b\preceq m\)（是 \(a,b\) 的上界）；
-
- 并且所有 \(a,b\) 的上界中，\(m\) 是最小的（最小上界）。
于是我们可以把 \(\gcd\) / \(\operatorname{lcm}\) 当作在整除偏序下的两种逻辑操作：
\(\gcd\) 像是「交」：取共同的那一部分「因子」；
\(\operatorname{lcm}\) 像是「并」：把两者的「因子需求」统一起来。
这一点在质因数分解视角里会变得更为直观。
偏序视角产生的代数规律
在任意「有最大下界与最小上界」的偏序结构中，以「取最大下界」和「取最小上界」作为二元运算，都必然满足：
- 交换律；
- 结合律；
- 幂等律（\(x\land x = x\)、\(x\lor x = x\)）；
- 吸收律（\(x\land(x\lor y)=x\)、\(x\lor(x\land y)=x\)）。
将其套用到 \(\gcd\) / \(\operatorname{lcm}\) 上， 就是一些非常显然的公式：
- 交换律：
- 结合律：
- 幂等律：
- 吸收率：
日志
本页面创建于 2025/12/10 15:31
后续内容待更新。