查看“︁最大公因数”︁的源代码

[[分类:整除理论]]
{{InfoBox
|name=公因数
|eng_name=common divisor
|aliases=公约数
}}
{{InfoBox
|name=最大公因数
|eng_name=greatest common divisor
|aliases=最大公约数,GCD
}}
'''公因数'''/'''公约数'''('''common divisor''')指两个整数公共的[[因数]]。

'''最大公因数'''/'''最大公约数'''('''greater common divisor''')指两个整数之间最大的公因数。

== 定义 ==

{{Operation
|name=最大公因数
|symbol=<math>\operatorname{gcd}(\bullet,\bullet)</math>,<math>(\bullet,\bullet)</math>
|latex=\operatorname{gcd}
|operand=整数
|result=自然数
|domain=<math>\mathbb{Z}\times\mathbb{Z}</math>
|codomain=<math>\mathbb{N}</math>
}}
对两个整数 <math>a, b</math> ，其公共的因数 <math>d</math> 满足 <math>d \mid a, d \mid b</math> ，则称其为整数 <math>a, b</math> 的'''公因数'''('''common divisor''')。
当 <math>a, b</math> 不全为零时，公因数一定存在（至少有 1 和 -1 两个）且有限，其中必然存在最大的整数，称为整数 <math>a, b</math> 的'''最大公因数'''('''greatest common divisor''', '''GCD''')，记作 <math>\operatorname{gcd}(a, b)</math> 或 <math>(a,b)</math> 。

注：这一定义也可以定义在[[自然数]]或[[正整数]]范围内。

注：虽然 <math>(a, b)</math> 比较简洁，但这个记号相当滥用了，本 wiki 主要用这个记号标记有序对和开区间。

一般地，对多个整数 <math>a_1, a_2, \dots, a_n</math> ，其公共的因数 <math>d</math> 满足 <math>d \mid a_1, d \mid a_2, \dots, d \mid a_n</math> ，则称其为整数 <math>a_1, a_2, \dots, a_n</math> 的'''公因数'''。
当 <math>a_1, a_2, \dots, a_n</math> 不全为零时，公因数一定存在（至少有 1 和 -1 两个）且有限，其中必然存在最大的整数，称为整数 <math>a_1, a_2, \dots, a_n</math> 的'''最大公因数'''，记作 <math>\operatorname{gcd}(a_1, a_2, \dots, a_n)</math> 。

特别地，对 <math>a_1=a_2=\dots=a_n=0</math> 的情况，最大公因数不是良定义的。

注：为了让不同的性质适用于 <math>\operatorname{gcd}(0, 0)</math> ，有时会补充定义 <math>\operatorname{gcd}(0, 0) = 0</math> ，有时会补充定义 <math>\operatorname{gcd}(0, 0) = \infty</math> 。

== 性质 ==

* 定义直接推论
** 对于一个元素的整数列 <math>a_1</math> ，最大公因数是 <math>\operatorname{gcd}(a_1) = |a_1|</math> ；
** 多元最大公因数是[[交换律|交换]]的： <math>\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>\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>a_1 | a_2</math> ，有 <math>\operatorname{gcd}(a_1,a_2,a_3,\dots,a_n) = \operatorname{gcd}(a_1,a_3,\dots,a_n)</math> ；
** 若这些数从一个数中加减另一个数的倍数，有 <math>\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>\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>a</math> ，有 <math>\operatorname{gcd}(a, 0) = \operatorname{gcd}(0, a) = |a|</math> 。
** 对正整数 <math>a</math> ，有 <math>\operatorname{gcd}(a, a) = a</math> ；对非零整数 <math>a</math> ，则是 <math>\operatorname{gcd}(a, a) = |a|</math> 。
* 对整数 <math>a, b</math> 和整数 <math>d</math> ，有 <math>d \mid a \land d \mid b \rightarrow d \mid \operatorname{gcd}(a, b)</math> 。
** 可推广到任意个数。这是最大公因数的本质，按整除的偏序关系，是所有“小于”这些数的数中的“最大”的，且取其中非负的。
*** 由于整除关系上 0 反而是“最大”的数，0 和 0 的最大公因数会被定义为 0 ；而考虑绝对值大小的则会定义为无穷。因此这里会看所需性质。
** 进一步地，有 <math>\operatorname{gcd}(a, b) = |d| \operatorname{gcd}(a/d, b/d)</math>
*** 特别地，有 <math>\operatorname{gcd}(a/\operatorname{gcd}(a, b), b/\operatorname{gcd}(a, b)) = 1</math>
* 完全分配格（要求定义 <math>\operatorname{gcd}(0, 0)=0</math>）
** 交换性： <math>\operatorname{gcd}(a, b) = \operatorname{gcd}(b, a)</math>
** 结合性： <math>\operatorname{gcd}(\operatorname{gcd}(a, b), c) = \operatorname{gcd}(a, \operatorname{gcd}(b, c))</math>
** 对偶运算： <math>\operatorname{lcm}(a, b)</math>
** 吸收率： <math>\operatorname{gcd}(a, \operatorname{lcm}(a, b)) = a</math>
** 分配性： <math>\operatorname{gcd}(a, \operatorname{lcm}(b, c)) = \operatorname{lcm}(\operatorname{gcd}(a, b), \operatorname{gcd}(a, c))</math>
* [[乘性函数（数论）|乘性]]：若 <math>a_1, a_2</math> [[互质]]，则 <math>\operatorname{gcd}(a_1 a_2, b) = \operatorname{gcd}(a_1, b) \operatorname{gcd}(a_2, b)</math>
* 与[[标准质因数分解]]的关系：
: <math>\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>\operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b) = |ab|</math>

== 求法 ==

每次约去两个数之间可确认公因数的短除法。

算法化的方法是[[辗转相除法]]。

=== 推论 ===

从求法可以推出一些特殊关系，如
* <math>2^\operatorname{gcd}(a,b) - 1 = \operatorname{gcd}(2^a-1, 2^b-1)</math>

{{整除与质数}}