最大公因数
| 公因数 | |
|---|---|
| 术语名称 | 公因数 |
| 英语名称 | common divisor |
| 别名 | 公约数 |
| 最大公因数 | |
|---|---|
| 术语名称 | 最大公因数 |
| 英语名称 | greatest common divisor |
| 别名 | 最大公约数, GCD |
公因数/公约数(common divisor)指两个整数公共的因数。
最大公因数/最大公约数(greater common divisor)指两个整数之间最大的公因数。
定义
| 最大公因数 | |
|---|---|
| 运算名称 | 最大公因数 |
| 运算符号 | [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{ a, b }[/math] 不全为零时，公因数一定存在（至少有 1 和 -1 两个）且有限，其中必然存在最大的整数，称为整数 [math]\displaystyle{ a, b }[/math] 的最大公因数(greatest common divisor, GCD)，记作 [math]\displaystyle{ \operatorname{gcd}(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{ 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{ a_1=a_2=\dots=a_n=0 }[/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] 。
- 可推广到任意个数。这是最大公因数的本质，按整除的偏序关系，是所有“小于”这些数的数中的“最大”的，且取其中非负的。
- 由于整除关系上 0 反而是“最大”的数，0 和 0 的最大公因数会被定义为 0 ；而考虑绝对值大小的则会定义为无穷。因此这里会看所需性质。
- 进一步地，有 [math]\displaystyle{ \operatorname{gcd}(a, b) = |d| \operatorname{gcd}(a/d, b/d) }[/math]
- 特别地，有 [math]\displaystyle{ \operatorname{gcd}(a/\operatorname{gcd}(a, b), b/\operatorname{gcd}(a, b)) = 1 }[/math]
- 可推广到任意个数。这是最大公因数的本质，按整除的偏序关系，是所有“小于”这些数的数中的“最大”的，且取其中非负的。
- 完全分配格（要求定义 [math]\displaystyle{ \operatorname{gcd}(0, 0)=0 }[/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{ \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) = a_1 = 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]
| 整除理论 | ||
|---|---|---|
| 整除关系 | 整除、倍数、因数 | 带余除法 |
| 正整数的分类 | 1、质数、合数 | |
| 质数测试 | 试除法、埃氏筛、线性筛 | |
| 最大公约数理论 | 公倍数、最小公倍数 [math]\displaystyle{ \operatorname{lcm} }[/math]、公因数、最大公因数 [math]\displaystyle{ \operatorname{gcd} }[/math] | 辗转相除法 |
| 互质 | ||
| 算术基本定理 | 算术基本定理 | 标准质因数分解 |