贝祖等式

贝祖等式（Bézout's identity）说：若整数 $a,b$ 不同时为零，则存在整数 $x,y$ 使 $$ax+by=gcd(a,b).$$ 右侧不是任意找到的公约数，而是最大公约数。它让“互素”转化成一个可用于代入的等式：$gcd(a,b)=1$ 当且仅当存在整数 $x,y$ 使 $ax+by=1$。

从除法回代

对 $a=84,b=30$，欧几里得算法给出 $84=2\cdot 30+24$ 与 $30=24+6$。第二式改写成 $6=30-24$，再代入第一式的 $24=84-2\cdot 30$： $$6=30-(84-2\cdot 30)=-84+3\cdot 30.$$ 因而可取 $x=-1,y=3$。把结果代回 $84(-1)+30(3)=6$，既检查了算术，也说明系数允许为负数。

等式为何总能得到

连续除法最终到达最大公约数。最后的非零余数是前面两数的差或整数倍之差；逐步回代，便成为最初 $a,b$ 的整数线性组合。反过来，任何公约数都整除 $ax+by$；所以能写成 1 的条件确实等价于互素。扩展欧几里得算法把回代组织成同时更新余数与系数的计算过程。

如果要证明素数 $p$ 整除 $ab$ 且不整除 $a$ 时必须整除 $b$，因为 $gcd(p,a)=1$，贝祖等式给出 $px+ay=1$。乘以 $b$ 得 $pbx+aby=b$；左边两项都被 $p$ 整除，所以 $p\mid b$。这是算术基本定理唯一性证明所用的欧几里得引理。

参考资料

• MIT，Mathematics for Computer Science，Divisibility 章节。
• MIT 18.781，初等数论讲义。
• 继续阅读：最大公约数、模逆元、素数。