裴蜀定理¶

又称贝祖定理（Bézout's lemma）、贝祖等式（Bézout's identity），是一个关于最大公约数的定理。

若 \(a,b \in \mathbb{Z}\) 不全为零，且 \(\gcd(a,b)=d\)，那么 \(\forall x,y \in \mathbb{Z}\)，\(ax+by\) 一定是 \(d\) 的倍数。特别地，一定 \(\exists x,y \in \mathbb{Z}\) 使 \(ax+by=d\) 成立。

这个定理可以推广到 \(n\) 个整数的情况。

重要推论¶

\(a,b\) 互质的充要条件是 \(\exists x,y \in \mathbb{Z}\) 使 \(ax+by=1\) 成立。

证明¶

设 \(\gcd(a,b)=d\)，则 \(d \mid a\) 且 \(d \mid b\)，由整除的性质，\(\forall x,y \in \mathbb{Z}\) 有

即 \(ax+by\) 一定是 \(d\) 的倍数。

令 \(s=ax_0+by_0\) 为 \(\{ax+by \mid (x,y) \in \mathbb{Z}^2\}\) 中的最小正值。设 \(a\) 除以 \(s\) 的欧几里得除法为 \(a=qs+r\) 则

因为 \(0 \le r < s\) 且 \(r\) 也满足 \(ax+by\) 的形式，而 \(s\) 是这类数的最小正值，所以 \(r=0\)。进而 \(s \mid a\)，同理也有 \(s \mid b\)，故 \(s\) 是 \(a,b\) 的公约数，所以

因为 \(s=ax_0+by_0\)，所以 \(d \mid s\)。又因为 \(s>0\)，所以

综合 \((1)(2)\) 可得 \(d=s\)，即一定 \(\exists x,y \in \mathbb{Z}\) 使 \(ax+by=d\) 成立。

逆定理¶

设 \(a,b \in \mathbb{Z}\) 不全为零，且 \(d>0\) 为 \(a,b\) 的公约数，如果 \(\exists x,y \in \mathbb{Z}\) 使 \(ax+by=d\) 成立，则 \(d=\gcd(a,b)\)。