最大公因数
| 公因数 | |
|---|---|
| 术语名称 | 公因数 |
| 英语名称 | common divisor |
| 别名 | 公约数 |
| 最大公因数 | |
|---|---|
| 术语名称 | 最大公因数 |
| 英语名称 | greatest common divisor |
| 别名 | 最大公约数, GCD |
公因数/公约数(common divisor)指两个整数公共的因数。
最大公因数/最大公约数(greatest common divisor)指两个整数之间在整除意义上最大的公因数。
定义
最大公因数有两种不等价的定义，分别属于整除的两个定义体系。但形式上的区别仅在于整数是否非零。 前一种定义不允许出现 0 ，在数论教材中更常见；后一种定义基于整除关系的乘法定义，有更良好的性质，在抽象代数中更常见。本 wiki 中将按照后一种定义讨论。
不含 0 的定义
| 最大公因数 | |
|---|---|
| 运算名称 | 最大公因数 |
| 运算符号 | [math]\displaystyle{ \operatorname{gcd}(\bullet,\bullet) }[/math],[math]\displaystyle{ (\bullet,\bullet) }[/math] |
| Latex | \operatorname{gcd}
|
| 运算对象 | 非零整数 |
| 运算元数 | 2 |
| 运算结果 | 正整数 |
| 定义域 | [math]\displaystyle{ \mathbb{Z}^*\times\mathbb{Z}^* }[/math] |
| 陪域 | [math]\displaystyle{ \mathbb{N}^* }[/math] |
对两个非零整数 [math]\displaystyle{ a, b }[/math] ，其公共的因数 [math]\displaystyle{ d }[/math] 满足 [math]\displaystyle{ d \mid a, d \mid b }[/math] ，称为整数 [math]\displaystyle{ a, b }[/math] 的公因数(common divisor)。 对非零整数，正的公因数一定存在（至少存在 1 是正公因数）且有限，其中必然存在最大的整数 [math]\displaystyle{ \max\{d\mid d\mid a,d\mid b\} }[/math] ，称为整数 [math]\displaystyle{ a, b }[/math] 的最大公因数(greatest common divisor, GCD)，记作 [math]\displaystyle{ \operatorname{gcd}(a, b) }[/math] 或 [math]\displaystyle{ (a,b) }[/math] 。
这种定义有时也会被原样扩展到 0 上。
- 对 [math]\displaystyle{ a=0 }[/math] 的情况，定义 [math]\displaystyle{ \operatorname{gcd}(0, b) = |b| }[/math] ；
- 对 [math]\displaystyle{ a=b=0 }[/math] 的情况，由于任意正整数都是 0 与 0 的公因数，这种定义无法扩展，也有的资料选择认为最大公因数是 [math]\displaystyle{ +\infty }[/math] 或不存在。
含 0 的定义
| 最大公因数 | |
|---|---|
| 运算名称 | 最大公因数 |
| 运算符号 | [math]\displaystyle{ \operatorname{gcd}(\bullet,\bullet) }[/math],[math]\displaystyle{ (\bullet,\bullet) }[/math] |
| Latex | \operatorname{gcd}
|
| 运算对象 | 整数 |
| 运算元数 | 2 |
| 运算结果 | 自然数 |
| 定义域 | [math]\displaystyle{ \mathbb{Z}\times\mathbb{Z} }[/math] |
| 陪域 | [math]\displaystyle{ \mathbb{N} }[/math] |
对两个整数 [math]\displaystyle{ a, b }[/math] ，其公共的因数 [math]\displaystyle{ d }[/math] 满足 [math]\displaystyle{ d \mid a, d \mid b }[/math] ，称为整数 [math]\displaystyle{ a, b }[/math] 的公因数(common divisor)。 对非负公因数的集合 [math]\displaystyle{ D=\{d\mid d\geq 0\land d\mid a\land d\mid b\} }[/math] ，存在整除关系下的最大元，即 [math]\displaystyle{ (\exists d\in D)(\forall d'\in D)(d'\mid d) }[/math] ，称为整数 [math]\displaystyle{ a, b }[/math] 的最大公因数(greatest common divisor, GCD)，记作 [math]\displaystyle{ \operatorname{gcd}(a, b) }[/math] 或 [math]\displaystyle{ (a,b) }[/math] 。
特别地，
- 对 [math]\displaystyle{ a=0 }[/math] 的情况， [math]\displaystyle{ D=\{d\mid d\leq 0 \land d\mid 0\land d\mid b\} = \{d\mid d\leq 0 \land d\mid b\} }[/math] ，所以 [math]\displaystyle{ |b|\in D }[/math] 且 [math]\displaystyle{ (\forall d'\in D)(d'\mid |b|) }[/math] ，因此 [math]\displaystyle{ \operatorname{gcd}(0, b) = |b| }[/math] ；
- 对 [math]\displaystyle{ a=b=0 }[/math] 的情况， [math]\displaystyle{ D=\mathbb{N} }[/math] ，而 [math]\displaystyle{ 0\in D }[/math] 且 [math]\displaystyle{ (\forall d'\in D)(d'\mid 0) }[/math] ，因此 [math]\displaystyle{ \operatorname{gcd}(0, 0) = 0 }[/math] 。
注：在整除关系上， 0 是比所有非零整数更“大”的数，在这种定义中 0 和 0 的最大公因数会被定义为 0 ；而前一种定义中考虑绝对值大小的则会定义为无穷。因此这里会看所需性质。
相关定义
虽然 [math]\displaystyle{ (a, b) }[/math] 比较简洁，但这个记号相当滥用了，本 wiki 主要用这个记号标记有序对和开区间，一律用 [math]\displaystyle{ \operatorname{gcd}(a,b) }[/math] 表达最大公因数。
一般地，对多个整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] ，其公共的因数 [math]\displaystyle{ d }[/math] 满足 [math]\displaystyle{ d \mid a_1, d \mid a_2, \dots, d \mid a_n }[/math] ，则称其为整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 的公因数。 当 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 不全为零时，公因数一定存在（至少有 1 和 -1 两个）且有限，其中必然存在在整除关系下的非负的最大元，称为整数 [math]\displaystyle{ a_1, a_2, \dots, a_n }[/math] 的最大公因数，记作 [math]\displaystyle{ \operatorname{gcd}(a_1, a_2, \dots, a_n) }[/math] 。
注：为了让不同的性质适用于 [math]\displaystyle{ \operatorname{gcd}(0, 0) }[/math] ，有时会补充定义 [math]\displaystyle{ \operatorname{gcd}(0, 0) = 0 }[/math] ，有时会补充定义 [math]\displaystyle{ \operatorname{gcd}(0, 0) = \infty }[/math] 。
性质
- 定义直接推论
- 对一个整数 [math]\displaystyle{ a_1 }[/math] ，最大公因数是 [math]\displaystyle{ \operatorname{gcd}(a_1) = |a_1| }[/math] ；
- 多元最大公因数是交换的： [math]\displaystyle{ \operatorname{gcd}(a_1,a_2,\dots,a_i,\dots,a_n) = \operatorname{gcd}(a_i,a_2,\dots,a_1,\dots,a_n) }[/math] ；
- 符号不影响最大公因数，即 [math]\displaystyle{ \operatorname{gcd}(a_1,a_2,\dots,a_n) = \operatorname{gcd}(-a_1,a_2,\dots,a_n) = \operatorname{gcd}(|a_1|,a_2,\dots,a_n) }[/math] ；
- 若这些数中存在整除关系，不妨设 [math]\displaystyle{ a_1 | a_2 }[/math] ，有 [math]\displaystyle{ \operatorname{gcd}(a_1,a_2,a_3,\dots,a_n) = \operatorname{gcd}(a_1,a_3,\dots,a_n) }[/math] ；
- 若这些数从一个数中加减另一个数的倍数，有 [math]\displaystyle{ \operatorname{gcd}(a_1,a_2,a_3,\dots,a_n) = \operatorname{gcd}(a_1,a_2 + k a_1,\dots,a_n) }[/math] ；
- 若其中一个数是质数，有 [math]\displaystyle{ \operatorname{gcd}(p,a_2,a_3,\dots,a_n) = \begin{cases} p &, p \mid a_i, i=2,3,\dots,n \\ 1 &, \text{其他} \end{cases} }[/math] 。
- 特殊值
- 对整数 [math]\displaystyle{ a }[/math] ，有 [math]\displaystyle{ \operatorname{gcd}(a, 0) = \operatorname{gcd}(0, a) = |a| }[/math] 。
- 对正整数 [math]\displaystyle{ a }[/math] ，有 [math]\displaystyle{ \operatorname{gcd}(a, a) = a }[/math] ；对整数 [math]\displaystyle{ a }[/math] ，则是 [math]\displaystyle{ \operatorname{gcd}(a, a) = |a| }[/math] 。
- 对整数 [math]\displaystyle{ a, b }[/math] 和整数 [math]\displaystyle{ d }[/math] ，有 [math]\displaystyle{ d \mid a \land d \mid b \rightarrow d \mid \operatorname{gcd}(a, b) }[/math] 。
- 可推广到任意个数。这是最大公因数的本质：非负的公因数中，按整除作为偏序关系的最大元。
- 进一步地，有 [math]\displaystyle{ \operatorname{gcd}(a, b) = |d| \operatorname{gcd}(\tfrac ad, \tfrac bd) }[/math]
- 特别地，有 [math]\displaystyle{ \operatorname{gcd}(\tfrac{a}{\operatorname{gcd}(a, b)}, \tfrac{b}{\operatorname{gcd}(a, b)}) = 1 }[/math]
- 完全分配格
- 交换性： [math]\displaystyle{ \operatorname{gcd}(a, b) = \operatorname{gcd}(b, a) }[/math]
- 结合性： [math]\displaystyle{ \operatorname{gcd}(\operatorname{gcd}(a, b), c) = \operatorname{gcd}(a, \operatorname{gcd}(b, c)) }[/math]
- 对偶运算： [math]\displaystyle{ \operatorname{lcm}(a, b) }[/math]
- 吸收率： [math]\displaystyle{ \operatorname{gcd}(a, \operatorname{lcm}(a, b)) = a }[/math]
- 分配性： [math]\displaystyle{ \operatorname{gcd}(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\operatorname{gcd}(a, b), \operatorname{gcd}(a, c)) }[/math]
- 乘性：若 [math]\displaystyle{ a_1, a_2 }[/math] 互质，则对整数 [math]\displaystyle{ b }[/math] ，有 [math]\displaystyle{ \operatorname{gcd}(a_1 a_2, b) = \operatorname{gcd}(a_1, b) \operatorname{gcd}(a_2, b) }[/math]
- 与标准质因数分解的关系：
- [math]\displaystyle{ \begin{aligned} & 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{gcd}(a, b) = p_1^{\min \{s_1, t_1\}} p_2^{\min \{s_2, t_2\}} \dots p_n^{\min \{s_n, t_n\}} \end{aligned} }[/math]
- [math]\displaystyle{ \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = |ab| }[/math]
求法
每次约去两个数之间可确认公因数的短除法。
算法化的方法是辗转相除法。
推论
从求法可以推出一些特殊关系，如
- [math]\displaystyle{ 2^\operatorname{gcd}(a,b) - 1 = \operatorname{gcd}(2^a-1, 2^b-1) }[/math]