裴蜀定理¶
又称贝祖定理（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)\)。
相关文章