最大公约数 · aiwiki.page

两个不全为零的整数 $a$ 和 $b$ 的最大公约数，是能够同时整除这两个数的最大正整数，通常记作 $\gcd(a,b)$ 。例如， $\gcd(18,24)=6$ ，因为 6 能整除这两个数，而没有更大的正整数能同时整除它们。这一概念是数论的基础，将整除关系、分数的约分与整数方程的求解联系起来。(math.libretexts.org)

定义与约定

如果存在整数 $k$ ，使得 $a=ck$ ，就称整数 $c$ 整除整数 $a$ ，记作 $c\mid a$ 。因此，对于不全为零的 $a$ 和 $b$ ，其最大公约数是满足下列条件的正整数 $d$ ：

$d\mid a$ 且 $d\mid b$ ；
$a$ 和 $b$ 的每一个公约数都整除 $d$ 。

对于整数而言，这一刻画等价于“最大的正公约数”。它不仅比较公约数的大小，还描述了最大公约数与其他所有公约数之间的整除关系。(math.libretexts.org)

正负号不影响结果：

\gcd(a,b)=\gcd(|a|,|b|).

由于每个非零整数都整除零，

\gcd(a,0)=|a|\qquad(a\ne0).

“最大正公约数”的定义不适用于数对 $(0,0)$ ：每个正整数都能整除这两个数，因此不存在最大的正公约数。一种扩展约定规定 $\gcd(0,0)=0$ ，从而使最大公约数始终为非负数。(math.libretexts.org)

这一定义可以推广到任意一组不全为零的有限个整数，其中至少有一个整数。它们的最大公约数可以逐次计算：

\gcd(a,b,c)=\gcd(\gcd(a,b),c).

因此， $\gcd(12,18,30)=6$ 。(aleph0.clarku.edu)

素因数分解与基本性质

算术基本定理给出了基于因数分解的描述。将正整数写成素数的乘积，并将未出现在分解中的素数的指数记为零：

a=\prod_p p^{\alpha_p}, \qquad b=\prod_p p^{\beta_p}.

则有

\gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}.

每个素数在最大公约数中的指数，取它在两个数的分解中对应指数的较小值。例如，

72=2^3 3^2,\qquad 120=2^3 3\,5,

所以 $\gcd(72,120)=2^3 3=24$ 。(uregina.ca)

最大公约数为 1 的两个整数称为互素，也称互质。这两个整数都不必是素数：例如，8 和 15 互素。对于两个以上的整数，最大公约数为 1 的条件弱于两两互素。例如， $\gcd(6,10,15)=1$ ，但其中每一对数都有大于 1 的公约数。(math.libretexts.org)

最小公倍数则取每个素数对应指数的较大值。因此，对于正整数，有

\gcd(a,b)\operatorname{lcm}(a,b)=ab.

最大公约数具有对称性，并满足结合律；将两个数都乘以正整数 $k$ ，则有

\gcd(ka,kb)=k\gcd(a,b).

这些性质都可以直接由上述素数指数的描述推出。(uregina.ca)

最大公约数的计算

主要的计算方法是欧几里得算法，它无需进行素因数分解。其关键步骤是

\gcd(a,b)=\gcd(b,r), \qquad a=qb+r.

能整除 $a$ 和 $b$ 的数，也能整除 $r=a-qb$ ；反之，能整除 $b$ 和 $r$ 的数，也能整除 $a=qb+r$ 。因此，这两对数的公约数完全相同。(math.libretexts.org)

对于非负的输入值，且 $b>0$ 时，取满足 $0\le r<b$ 的余数，将 $(a,b)$ 替换为 $(b,r)$ ，重复这一过程，直到第二个数为零。正余数逐步减小，保证了算法会终止。最后一个非零余数就是最大公约数。例如，

\begin{aligned} 252&=1\cdot198+54,\\ 198&=3\cdot54+36,\\ 54&=1\cdot36+18,\\ 36&=2\cdot18+0. \end{aligned}

因此， $\gcd(252,198)=18$ 。(math.libretexts.org)

二进制最大公约数算法则采用减法、比较和去除因子 2 的操作。对于非常大的整数，实际实现还会采用莱默算法和次二次时间的最大公约数算法等方法。这些算法体现了最大公约数计算在计算机科学中的意义：数学上等价的计算过程，会因输入规模和机器的算术运算方式而具有不同的计算成本。(gmplib.org)

裴蜀等式

裴蜀等式指出，对于不全为零的整数 $a,b$ ，存在整数 $x,y$ ，使得

ax+by=\gcd(a,b).

扩展欧几里得算法可以在计算最大公约数的同时求出这些系数，也可以通过对余数等式逐步回代得到它们。对于前面的例子，

\begin{aligned} 18&=54-36\\ &=54-(198-3\cdot54)\\ &=4(252-198)-198\\ &=4\cdot252-5\cdot198. \end{aligned}

因此， $x=4$ ， $y=-5$ 。(math.libretexts.org)

每个整系数线性组合 $ax+by$ 都能被最大公约数整除。反过来，裴蜀等式说明，最大公约数的每个整数倍都可以表示为这样的组合。因此，最大公约数也是能够表示为 $ax+by$ 的最小正整数。(math.libretexts.org)

应用

分数约分。 如果 $b\ne0$ ，且 $d=\gcd(a,b)$ ，则

\frac ab=\frac{a/d}{b/d}.

所得的分子和分母互素，因此该分数为最简分数。例如， $18/24=3/4$ 。再将分母取为正数，就得到了有理数的一种标准表示。(uregina.ca)

整数方程。 当 $a,b$ 不全为零时，线性丢番图方程

ax+by=c

有整数解，当且仅当 $\gcd(a,b)\mid c$ 。必要性来自最大公约数能整除每个组合 $ax+by$ ；充分性则可通过将裴蜀等式两边乘以 $c/\gcd(a,b)$ 得到。(math.uwaterloo.ca)

模逆元。 在模算术中，整数 $a$ 在模 $m>1$ 下存在乘法逆元，当且仅当 $\gcd(a,m)=1$ 。如果 $ax+my=1$ ，则 $ax\equiv1\pmod m$ ，所以 $x$ 就是一个逆元。例如， $3\cdot5-7\cdot2=1$ ，因此 5 是 3 在模 7 下的逆元。(ocw.mit.edu)

推广到多项式

多项式也有相应的概念。在一个域（数学）上，两个非零多项式的最大公约式能整除这两个多项式，并且它们的每个公约式都能整除该最大公约式。将最大公约式乘以非零常数不会改变这些性质，因此通常将结果规范化为首一多项式，即最高次项系数为 1 的多项式。(doc.sagemath.org)

多项式的带余除法给出了一种欧几里得算法，其中逐步减小的是多项式的次数，而非整数的大小。例如，在有理数域上，

\gcd(x^2-1,x^2-3x+2)=x-1,

因为这两个多项式分别分解为 $(x-1)(x+1)$ 和 $(x-1)(x-2)$ 。最大公约式的计算还可以推广到多元多项式，但需要采用超出这种简单一元带余除法范围的方法。(doc.sagemath.org)

历史背景

欧几里得在《几何原本》第七卷中讨论了“最大公度量”。命题 VII.2 给出了求两个不互素的数的最大公度量的步骤，命题 VII.3 则将这一构造推广到三个数。该方法采用连续相减，对应于今天称为欧几里得算法的基于余数的方法。“公度量”这一术语反映了这样一种理解：一个整数数量可以恰好量尽另一个数量，即后者是前者的整数倍。(aleph0.clarku.edu)

参考来源

2: Greatest common divisor and least common multiplemath.libretexts.org
6: The Euclidean Algorithmmath.libretexts.org
2: Euclidean algorithm and Bézout's algorithmmath.libretexts.org
Miscellaneous arithmetic functions — SageMathdoc.sagemath.org
Math 101 Course Notesuregina.ca
Greatest Common Divisor Algorithms — GNU MPgmplib.org
MATH 145 Algebra, Lecture Notesmath.uwaterloo.ca
Principles of Discrete Applied Mathematics, Modular Arithmetic and Elementary Algebra Notesocw.mit.edu
Univariate polynomials over number fields — SageMathdoc.sagemath.org
Univariate polynomial base class — SageMathdoc.sagemath.org
Polynomials — SageMath Constructionsdoc.sagemath.org