最大公约数与最小公倍数

为什么是这样

两个整数共同的约数叫公约数（公約数），最大的那个叫最大公约数（最大公約数）$G$；共同的倍数叫公倍数（公倍数），最小的正公倍数叫最小公倍数（最小公倍数）$L$。最大公约数是 $1$ 的两个数叫互素（互いに素）。

看分解式：$84=2^2\cdot3\cdot7$，$126=2\cdot3^2\cdot7$。公约数要同时是两个数的约数，只能用两数都有的素因数，每种的个数不能超过任何一边，所以取较小的指数：$G=2\cdot3\cdot7=42$。公倍数要把两个数都装下，每种素因数取较大的指数：$L=2^2\cdot3^2\cdot7=252$。

由此还能看出：所有公约数都是 $G$ 的约数，所有公倍数都是 $L$ 的倍数。所以「$12$ 和 $18$ 的公倍数」就是「$36$ 的倍数」，开头的公交车 $7$ 点 $36$ 分再次同时发车；木板的正方形边长是 $42$ 厘米。

图里两圈的重合部分就是 $G$，左边剩下的 $a'=2$、右边剩下的 $b'=3$ 没有共同的素因数，所以互素。$L$ 是两圈合起来 $G\cdot a'\cdot b'$，而 $a\cdot b$ 把重合部分算了两次，等于 $G\cdot L$。

定量表达

由分解式求：$G$ 取每种素因数的较小指数（一边没有的素数，指数算 $0$，不进 $G$），$L$ 取较大指数。三个数也一样：$G$ 取最小指数，$L$ 取最大指数。

两个数之间的关系写成下面的公式块。注意 $ab=GL$ 只对两个数成立：$4,6,10$ 的 $G=2$、$L=60$，$GL=120$，而三数之积是 $240$。两数互素时 $G=1$，这时才有 $L=ab$。

互素有两条常用性质。$a$、$b$ 互素，且 $n$ 既是 $a$ 的倍数又是 $b$ 的倍数，则 $n$ 是 $ab$ 的倍数，上一节合并倍数判定法就靠它。$a$、$b$ 互素，且 $bc$ 是 $a$ 的倍数，则 $c$ 是 $a$ 的倍数。另外，相邻两个整数 $n$ 与 $n+1$ 一定互素：公约数也要整除两者之差 $1$。