进阶≈ 15 分钟未开始

最大公约数与最小公倍数

核心概念

最大公约数 $\gcd(a,b)$ :能同时整除 $a$ 和 $b$ 的最大正整数,记作 $(a,b)$ 。

最小公倍数 $\operatorname{lcm}(a,b)$ :能同时被 $a$ 和 $b$ 整除的最小正整数,记作 $[a,b]$ 。

互质:若 $\gcd(a,b) = 1$ ,称 $a,b$ 互质。

基本关系:对任意正整数 $a,b$ ,

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

辗转相除法(欧几里得算法):利用 $\gcd(a,b) = \gcd(b,\ a \bmod b)$ 反复取余,直到余数为 $0$ ,最后的非零除数就是 $\gcd$ 。

用质因数分解求:对每个质数取较低次幂之积得 $\gcd$ ,取较高次幂之积得 $\operatorname{lcm}$ 。

辗转相除法的核心是一个"缩小"恒等式: $\gcd(a,b)$ 不变地等于 $\gcd(b, a\bmod b)$ 。因为 $a$ 和 $b$ 的公约数,正好就是 $b$ 和余数 $a\bmod b$ 的公约数(由线性组合性质)。每取一次余,数就显著变小,几步之内必然算到底。

而那条 $\gcd \cdot \operatorname{lcm} = ab$ 的关系,从质因数分解看一目了然:对每个质数,"较低次幂 + 较高次幂的指数"恰好等于"两个指数之和",所以乘起来就还原成 $a\cdot b$ 。

辗转相除法

252 = 105 × 2 + 42

105 = 42 × 2 + 21

42 = 21 × 2 + 0

余数为 0，最后的除数即为答案：gcd = 21

a252

b105

每一步把「除数、余数」挪到下一行继续做除法。余数越来越小，几步内必然到 0。

例题 1辗转相除法

用辗转相除法求 $\gcd(252,105)$ 。

▸查看解答步骤

答: gcd(252,105)=21

例题 2已知 gcd 求 lcm

设 $a = 12,\ b = 28$ ,求 $\operatorname{lcm}(a,b)$ 。

▸查看解答步骤

答: lcm = 84

$\gcd(48, 18)$ 等于多少?

$48 = 2^4\cdot 3$ , $18 = 2\cdot 3^2$ ,取较低次幂: $2^1\cdot 3^1 = 6$ 。

$\operatorname{lcm}(12, 9)$ 等于多少?

$\gcd(12,9)=3$ , $\operatorname{lcm} = \dfrac{12\times 9}{3} = 36$ 。

若 $\gcd(a,b) = 1$ ,则 $\operatorname{lcm}(a,b)$ 等于?

ab

a + b

1

\max(a,b)

互质时 $\gcd = 1$ ,由 $\gcd\cdot\operatorname{lcm}=ab$ 得 $\operatorname{lcm} = ab$ 。

相邻两个正整数 $n$ 与 $n+1$ 一定互质。

它们的任何公约数 $d$ 必整除差 $(n+1)-n=1$ ,故 $d=1$ ,互质。

$\gcd(24, 36)$ 等于多少?

$24=2^3\cdot3,\ 36=2^2\cdot3^2$ ,取较低次幂 $2^2\cdot3 = 12$ 。

$\operatorname{lcm}(6, 8)$ 等于多少?

$\gcd(6,8)=2$ , $\operatorname{lcm}=\frac{6\times8}{2}=24$ 。

把 $\gcd$ 和 $\operatorname{lcm}$ 取反。 求 $\gcd$ 取较低次幂,求 $\operatorname{lcm}$ 取较高次幂。
盲目套 $\gcd\cdot\operatorname{lcm}=ab$ 到三个数。 该公式只对两个数成立,三个数时不能直接照搬。
辗转相除时把余数和商搞混。 每一步真正传下去的是余数,不是商。

前置知识点

接下来学习