一道基础习题的启发
Exercise 1.15.Prove that for all integers a, b, m, n, if am+bn=e for some e, then (a,b) divides e.
这个题当然只用到了整除的基本性质，但我认为将他与Bézout's Lemma联系是具有启发性的
他描述了a, b的线性组合与(a, b)的关系， 也有利于我们更深刻的理解Bézout's Lemma
由此可以得到一个比 Bézout 定理更强的一个表述。
对不全为零的整数 a,b，有
\boxed{
\gcd(a,b)=\min\{ax+by:\ x,y\in\mathbb Z,\ ax+by>0\}.
}
注意：“正”指组合的结果为正，系数 x,y 可以为负数或零。
证明很直接。记 d=\gcd(a,b)：
- 由上题可知：因为 d\mid a,\ d\mid b，所以 d\mid(ax+by)。因此，任何正的整数线性组合都至少是 d。
- Bézout 定理保证存在整数 x,y，使 ax+by=d。所以这个最小值确实能取到。
因此，最小正整数线性组合恰好就是最大公因数。
特别地，由这个更强的表述可以轻松推导出互素版本：
\boxed{
\gcd(a,b)=1
\iff
\exists\,x,y\in\mathbb Z,\quad ax+by=1.
}
对比其他方法
对于这个更强的表述，我曾在《初等数论及其应用》一书中看到过，以下是该书的证明：
这个证明虽然是正确的，但我认为它的技巧性、构造性掩盖了定理的本质；而我认为我的版本则更具启发性，更有利于抓住定理本质。