最大公因数与最小公倍数

最大公因数与最小公倍数

在关于整除与带余除法的课中，研究了两个自然数之间的关系 $d \mid a$。同时考虑两个数时，我们关心它们共有的因数和共有的倍数。每一对自然数 $a$ 与 $b$ 至少有一个公因数，即 $1$，并且至多有有限个公因数，因为 $a$ 的任何因数都不超过 $a$；此外，它们有无穷多个公倍数，其中包括乘积 $ab$。若是如此，下面的定义就有意义。

定义（最大公因数与最小公倍数）。两个自然数 $a$ 与 $b$ 的最大公因数（记作 $\operatorname{gcd}(a, b)$）是同时整除二者的最大自然数。最小公倍数（记作 $\operatorname{lcm}(a, b)$）是同时为二者倍数的最小自然数。

后者是一个非空自然数集合的最小元，由良序原理它存在。前者是公因数集合的最大元，这个集合非空，并且以 $a$ 为上界；一个非空且有上界的自然数集合有最大元，这一点同样由良序原理得出：它的上界的集合非空，因而有最小元 $M$，而 $M$ 属于该集合，因为否则每个元素都小于 $M$，又因为 $M - 1$ 与 $M$ 之间没有自然数，每个元素都不大于 $M - 1$，这样它就是一个小于 $M$ 的上界（若 $M = 1$，则该集合为 $\{1\}$，它包含 $M$）。例如，$12$ 与 $18$ 的公因数是 $1$、$2$、$3$ 和 $6$，它们的公倍数是 $36$、$72$、$108$，依此类推：

由定义立即得到一些特殊情形：$\operatorname{gcd}(a, 1) = 1$ 且 $\operatorname{lcm}(a, 1) = a$；$\operatorname{gcd}(a, a) = \operatorname{lcm}(a, a) = a$；并且，若 $a$ 整除 $b$，则 $\operatorname{gcd}(a, b) = a$ 且 $\operatorname{lcm}(a, b) = b$。此外，这两种运算都是对称的：两个数的顺序不影响结果。

利用素因数分解计算

由算术基本定理，每个大于 $1$ 的自然数都能唯一地分解为素因数之积。宜把 $a$ 与 $b$ 用同样的素数 $p_1, \ldots, p_k$ 写出，对只在其中一个数中出现的素数允许指数为零：

自然数 $d$ 整除 $a$，当且仅当在它的分解式中除了 $a$ 的素因数外不出现其他素数，并且每个素数的指数都不大于它在 $a$ 中的指数。由此可知，$d$ 同时整除 $a$ 与 $b$，当且仅当每个素数在 $d$ 中的指数都不超过两个指数中的任何一个；因此，对每个素数取两个指数中较小的那个，就得到最大的公因数。同样，$m$ 是公倍数，当且仅当每个素数在 $m$ 中的指数都不小于这两个指数，而最小的公倍数对每个素数取两个指数中较大的那个。例如：

这种方法很清楚，但它依赖于会分解因数，而分解大数的代价极高：目前还不知道任何快速的分解方法。下一节的算法只用除法、不分解因数就能计算最大公因数。