最大公因数与最小公倍数

这一招在做什么

整数 $a$ 、 $b$ 共同的因数里最大的那个，叫最大公因数，记作 $(a, b)$ ；共同的正倍数里最小的那个，叫最小公倍数，记作 $[a, b]$ 。 $(a, b) = 1$ 时说 $a$ 、 $b$ 互素。

数大了以后，一个个列因数太慢。辗转相除法只靠一条事实：

a = q b + r ⟹ (a, b) = (b, r)

因为能同时整除 $a$ 、 $b$ 的数，也整除 $r = a - q b$ ；能同时整除 $b$ 、 $r$ 的数，也整除 $a = q b + r$ 。两对数的公因数完全一样，最大的那个当然也一样。

操作台上的长方形在做同一件事：切下 $q$ 个边长为 $b$ 的正方形，剩下 $b \times r$ 的小长方形，再切。

先猜后证

用同样大小的正方形地砖（边长是整数），正好铺满一块 $48 \times 18$ 的长方形地面。地砖的边长最大是多少？

先选定答案，才能看到结论。

第 1 / 5 步

最后一步不是偶然，对任何两个数都做得到：

裴蜀等式 对任意不全为零的整数 $a$ 、 $b$ ，存在整数 $x$ 、 $y$ 使得 $a x + b y = (a, b)$ 。特别地， $a$ 、 $b$ 互素 $⟺$ 存在整数 $x$ 、 $y$ 使 $a x + b y = 1$ 。

它马上修好了上一站那个坏掉的结论：

如果 $a ∣ b c$ 且 $(a, b) = 1$ ，那么 $a ∣ c$ 。

取 $a x + b y = 1$ ，两边乘 $c$ ： $c = a (c x) + (b c) y$ 。右边两项都被 $a$ 整除，所以 $a ∣ c$ 。

每铺满一次，操作台还报出了 $[a, b]$ 。它和 $(a, b)$ 之间有一条固定的关系：

(a, b) \cdot [a, b] = a \cdot b

所以求最小公倍数不用另起炉灶：先辗转相除求出 $(a, b)$ ，再用 $ab$ 去除以它。为什么这条关系成立，下一站用“指数柱”一眼就能看出来。

Break it

结论： $a ∣ n$ 且 $b ∣ n$ 时，一定有 $ab ∣ n$

$a = 9$ ， $b = 4$ 。切到底，最大公因数是 $1$ ，最小公倍数就是 $9 \times 4 = 36$ 。所以同时是 $9$ 和 $4$ 的倍数的数，一定是 $36$ 的倍数。

练习 1基础

用辗转相除法求 $(221, 91)$ 。

练习 2基础

求 $[84, 90]$ 。

练习 3提高

求最小的正整数 $x$ ，使得存在整数 $y$ 满足 $37 x + 13 y = 1$ 。

练习 4挑战

证明：对任何正整数 $n$ ，分数 $\frac{5 n + 3}{3 n + 2}$ 都是既约分数。