8.2 最大公约数、欧几里得算法与贝祖等式

第 8.1 节用素因数描述每个正整数。如果两个数已经完成分解，共同的素因数就能揭示它们的公因数。不过，因数分解往往比我们真正需要的工作多得多。

本节将建立一种递归方法：不断把一对数替换为规模更小的余数对，同时保持全部公因数不变。

公因数与最大公约数

设整数 $a,b$ 不同时为零。如果整数 $d$ 满足

就称 $d$ 为 $a$ 与 $b$ 的公因数。

$a$ 与 $b$ 的最大公约数记作

它是同时整除两个数的最大正整数。

例如，$84$ 的正因数为

$30$ 的正因数为

两者的正公因数是 $1,2,3,6$，所以

交换输入顺序不会改变结果：

当 $a\ne0$ 时，

因为 $a$ 的每个因数都整除 $0$，而 $a$ 的最大正因数是 $|a|$。

从素数指数读取最大公约数

假设

以及

公因数只能使用两边都出现的素数，并且每个共同素数最多使用两边较小的指数。因此

这种方法有助于理解，但前提是先分解两个输入。欧几里得算法不需要这个前提。

带余除法产生商和余数

设 $a\in\mathbb Z$，$b$ 为正整数。带余除法定理说明，存在唯一的整数 $q,r$，使得

其中：

• $q$ 是商；

• $r$ 是余数；

• 条件 $0\le r<b$ 保证余数具有唯一性。

例如，

因此 $252$ 除以 $105$ 的商为 $q=2$，余数为 $r=42$。

余数可记作

这里的“mod”表示取余运算。第 8.3 节会用同一思想定义同余类。

欧几里得算法的关键不变量

若

则

为什么公因数没有变化？

先假设 $d$ 同时整除 $a$ 与 $b$。由

以及第 8.1 节的整数线性组合规则，可得 $d\mid r$。所以 $a,b$ 的每个公因数也是 $b,r$ 的公因数。

反过来，假设 $d$ 同时整除 $b$ 与 $r$。因为

所以 $d\mid a$。因此 $b,r$ 的每个公因数也是 $a,b$ 的公因数。

两对数拥有完全相同的公因数，所以最大正公因数也相同。

这条等式是一个不变量：数对不断变化，但它的最大公约数保持不变。

逐步执行欧几里得算法

要计算正整数 $a\ge b$ 的 $\gcd(a,b)$：

1. 用 $b$ 除 $a$，得到 $a=bq+r$；

2. 把数对 $(a,b)$ 替换为 $(b,r)$；

3. 重复以上过程，直到余数为 $0$；

4. 返回最后一个非零余数。

例子：$\gcd(252,105)$

对应的不变量链为

因此

算法为什么一定终止

每个非零余数都满足

所以数对的第二个分量会形成严格递减的非负整数序列。它不可能永远递减，最终必定产生余数 $0$。

这正是第 7 章学习过的良基递归推理。

算法可以递归地写成

第一行是基础情况，第二行是缩小问题的递归步骤。

让两股整数水流经过余数瀑布。每道闸门先按商分组，再把余数倒入下一条水道，同时携带一组不变的公因数令牌。你可以逐步操作或播放动画，直到最后一条非零水道揭示最大公约数。

贝祖等式把最大公约数写成线性组合

对不同时为零的整数 $a,b$，贝祖等式说明存在整数 $x,y$，使得

$x,y$ 叫作贝祖系数，它们通常并不唯一。

普通欧几里得算法求出最大公约数；扩展欧几里得算法再沿余数等式反向回代，找出这些系数。

反向代入示例

正向计算得到的等式是

以及

先用第二条等式表示最后一个非零余数：

再用第一条等式表示 $42$：

把 $42$ 的表达式代回：

所以一组贝祖系数是

直接检查：

系数向量始终保留原始输入

还可以把每个余数都表示成原始数对的线性组合。

等式

对应系数向量 $(1,0)$；等式

对应 $(0,1)$。

当余数通过

产生时，系数向量也执行同一种减法：

在当前例子中，

接着

最终向量直接给出了贝祖系数。

哪些整数线性组合能够实现

最大公约数整除 $a$ 与 $b$，所以它也整除每个整数线性组合 $ax+by$。贝祖等式又说明最大公约数本身就是这样的组合。

因此方程

有整数解，当且仅当

例如，

有整数解，因为 $21\mid42$。把贝祖等式乘以 $2$ 就得到一组解：

但 $252x+105y=10$ 没有整数解，因为 $21\nmid10$。

沿系数向量换轨场反向穿过欧几里得轨迹。每个路口都要选择按商加权的正确减法，才能重建上一个余数；错误代入会让最终恒等式断裂，正确路线则会产出可直接检查的贝祖系数。

本节衔接

贝祖系数不仅能求解线性方程。当 $\gcd(a,n)=1$ 时，等式 $ax+ny=1$ 中的一个系数会成为 $a$ 在模 $n$ 下的乘法逆元。第 8.3 节将建立这个模运算视角，再用中国剩余定理合并多条余数条件。