浅谈裴蜀定理

rxr2018360074 · 2026-01-31 09:54:33 · 算法·理论

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

内容

设 a,b 是不全为 0 的整数，对任意整数 x,y，满足 \gcd (a,b)∣ax+by，且存在整数 x,y，使得 ax+by= \gcd (a,b)。

证明

对于前半句，因为 \gcd (a,b) | a 且 \gcd (a,b) | b，所以 \gcd (a,b) | ax 且 \gcd (a,b) | by，故 \gcd (a,b)∣(ax+by)。

对于后半句，考虑由所有 ax+by(x,y \in \mathbb{Z}) 构成的整数集合 S，因为 a,b 不全为零，所以 S 中显然包含正整数。所以 S 的正整数部分（以下记为 S'）是正整数集的一个子集。由良序原理可得 S' 中必定存在最小值。将最小值记作

对 a 做带余除法：a=qd+r，其中 0\le r < d，将这个形式转换一下，得

因为 q,x_0,y_0\in \mathbb{Z}，所以 r\in S。

我们发现，如果 r>0，那么 r\in S'，此时因为 r<d，所以 r 才是 S' 中最小的正整数，这与我们原先的假设相悖。所以 r\le 0。

又因为 r\ge 0，所以 r=0，即 d | a。 同理可以证明 d|b，即 d 是 a 和 b 的公因数。

此时因为 d\in S，所以 \gcd (a,b)|d，即 d=k\times \gcd (a,b)(k\ge 1)，如果 k>1，那么我们找到了一个比 \gcd (a,b) 更大的 a 和 b 的公因数，与 \gcd (a,b) 的定义矛盾。所以 k=1，即 d= \gcd (a,b)。所以存在 x 和 y 使得 ax+by= \gcd (a,b)。后半句得证。

注：此定理可以扩展成多个整数的情况。

模版题

应用

那么它有什么用呢？

1. 不定方程

裴蜀定理可以用于判定不定方程是否有解。

即对于关于 x,y 的方程 ax+by=c 有解等价于 \gcd (a,b)|c。

例：二元一次不定方程

线性同余方程

2. 各种问题的建模

最经典的莫过于倒水问题。

例：倒水

由裴蜀定理能直接得出第一问的答案。

3. 证明

例：Stern-Brocot 树 题解（看最后一篇）

前置知识：\frac{a}{b} 为最简分数等价于存在 x,y 使得 ax+by=1。