裴蜀定理

在数论中，裴蜀等式（英语：Bézout's identity）或裴蜀定理（Bézout's lemma）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 $a$ 、 $b$ 和 $m$ ，关于未知数 $x$ 和 $y$ 的线性丢番图方程（称为裴蜀等式）：

ax+by=m

有整数解时当且仅当 $m$ 是 $a$ 及 $b$ 的最大公约数 $d$ 的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 $x$ 、 $y$ 都称为裴蜀数，可用扩展欧几里得算法求得。

例如，12 和 42 的最大公约数是 6，则方程 $12x+42y=6$ 有解。事实上有 $(-3)\times 12+1\times 42=6$ 、 $4\times 12+(-1)\times 42=6$ 等。

特别来说，方程 $ax+by=1$ 有整数解当且仅当整数 $a$ 和 $b$ 互素。

裴蜀等式也可以用来给最大公约数定义： $d$ 其实就是最小的可以写成 $ax+by$ 形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。

历史

历史上首先证明关于整数的裴蜀定理的并不是裴蜀，而是17世纪初的法国数学家克劳德-加斯帕·巴歇·德·梅齐里亚克（法语：Claude-Gaspard Bachet de Méziriac）。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》（Problèmes plaisants et délectables qui se font par les nombres）第二版中给出了问题的描述和证明^[1]。

然而，裴蜀推广了梅齐里亚克的结论，特别是探讨了多项式中的裴蜀等式，并给出了相应的定理和证明^[2]。

整数中的裴蜀定理

对任意两个整数 $a$ 、 $b$ ，设 $d$ 是它们的最大公约数。那么关于未知数 $x$ 和 $y$ 的线性丢番图方程（称为裴蜀等式）：

\displaystyle ax+by=m

有整数解 $(x,y)$ 当且仅当 $m$ 是 $d$ 的整数倍。裴蜀等式有解时必然有无穷多个解。

证明：

如果 $a$ 和 $b$ 中有一个是0，比如 $a=0$ ，那么它们两个的最大公约数是 $b$ 。这时裴蜀等式变成 $\displaystyle by=m$ ，它有整数解 $(x,y)$ 当且仅当 $m$ 是 $b$ 的倍数，而且有解时必然有无穷多个解，因为 $x$ 可以是任何整数。定理成立。

以下设 $a$ 和 $b$ 都不为0。

设 $A=\{xa+yb;(x;y)\in \mathbb {Z} ^{2}\}$ ，下面证明 $A$ 中的最小正元素是 $a$ 与 $b$ 的最大公约数。

首先， $A\cap \mathbb {N} ^{*}$ 不是空集（至少包含 $|a|$ 和 $|b|$ ），因此由于自然数集合是良序的， $A$ 中存在最小正元素 $d_{0}=x_{0}a+y_{0}b$ 。考虑 $A$ 中任意一个正元素 $p$ （ $=x_{1}a+y_{1}b$ ）对 $d_{0}$ 的带余除法：设 $p=qd_{0}+r$ ，其中 $q$ 为正整数， $0\leq r<d_{0}$ 。但是

r=p-qd_{0}=x_{1}a+y_{1}b-q(x_{0}a+y_{0}b)=(x_{1}-qx_{0})a+(y_{1}-qy_{0})b\in A

因此 $r=0$ ， $d_{0}\ |\ p$ 。也就是说， $A$ 中任意一个正元素 $p$ 都是 $d_{0}$ 的倍数，特别地： $d_{0}\ |\ a$ 、 $d_{0}\ |\ b$ 。因此 $d_{0}$ 是 $a$ 和 $b$ 的公约数。

另一方面，对 $a$ 和 $b$ 的任意正公约数 $d$ ，设 $a=kd$ 、 $b=ld$ ，那么

d_{0}=x_{0}a+y_{0}b=(x_{0}k+y_{0}l)d

因此 $d\ |\ d_{0}$ 。所以 $d_{0}$ 是 $a$ 和 $b$ 的最大公约数。

在方程 $ax+by=m$ 中，如果 $m=m_{0}d_{0}$ ，那么方程显然有无穷多个解：

\left\{\left(m_{0}x_{0}+{\frac {kb}{d}},\ m_{0}y_{0}-{\frac {ka}{d}}\right)\mid k\in \mathbb {Z} \right\}

。

相反的，如果 $ax+by=m$ 有整数解，那么 $|m|\in A$ ，于是由前可知 $d_{0}\ |\ |m|$ （即 $d_{0}\ |\ m$ ）。

$m=1$ 时，方程有解当且仅当 $a$ 、 $b$ 互质。方程有解时，解的集合是

\left\{\left({\frac {m}{d}}x_{0}+{\frac {kb}{d}},\ {\frac {m}{d}}y_{0}-{\frac {ka}{d}}\right)\mid k\in \mathbb {Z} \right\}

。其中

(x_{0},y_{0})

是方程

ax+by=d

的一个解，可由辗转相除法得到。

所有解中，恰有二解 $(x,y)$ 满足 $|x|\leq |b/d|$ 及 $|y|\leq |a/d|$ ，等号只会在 $a$ 及 $b$ 其中一个是另一个的倍数时成立。辗转相除法给出的解会是这两解中的一个。

例子

丢番图方程 $504x+651y=14$ 没有整数解，因为504和651的最大公约数是21。而方程 $504x+651y=21$ 是有解的。为了求出通解，可以先约掉公约数21，这样得到方程：

24x+31y=1

。

通过扩展欧几里得算法可以得到一组特解 $(x,y)=(-9,7)$ ： $24\cdot (-9)+31\cdot 7=-216+217=1$ 。

特解

(x,y)=(-9,7)

的求法

{\color {Blue}24x+31y=1\rightarrow 1-31y=24x}

{\color {Blue}\rightarrow 1-31y\equiv 0{\pmod {24}}\rightarrow 1-(31-24)y\equiv 0{\pmod {24}}\rightarrow 1-7y\equiv 0{\pmod {24}}}

令

{\color {Red}1-7y=24a\rightarrow 1-24a=7y}

{\color {Red}\rightarrow 1-24a\equiv 0{\pmod {7}}\rightarrow 1-(24-7\times 3)a\equiv 0{\pmod {7}}\rightarrow 1-3a\equiv 0{\pmod {7}}}

令

{\color {Green}1-3a=7b\rightarrow 1-7b=3a}

{\color {Green}\rightarrow 1-7b\equiv 0{\pmod {3}}\rightarrow 1-(7-3\times 2)b\equiv 0{\pmod {3}}\rightarrow 1-b\equiv 0{\pmod {3}}}

取

b=1

为满足

1-b\equiv 0{\pmod {3}}

的解

将

b=1

代回

1-3a=7b

，解一元一次方程式得

a=-2

将

a=-2

代回

1-7y=24a

，得

y=7

将

y=7

代回

24x+31y=1

，得

x=-9

故

(x,y)=(-9,7)

为一组特解

于是通解为： $\left\{\left(1\cdot -9+31k,1\cdot 7-24k\right)|k\in \mathbb {Z} \right\}$ ，即

\left\{\left(-9+31k,7-24k\right)|k\in \mathbb {Z} \right\}

。

多个整数间的裴蜀定理

设 $a_{1},\cdots a_{n}$ 为 $n$ 个整数， $d$ 是它们的最大公约数，那么存在整数 $x_{1},\cdots x_{n}$ 使得 $x_{1}\cdot a_{1}+\cdots x_{n}\cdot a_{n}=d$ 。特别来说，如果 $a_{1},\cdots a_{n}$ 互质（不是两两互质），那么存在整数 $x_{1},\cdots x_{n}$ 使得 $x_{1}\cdot a_{1}+\cdots x_{n}\cdot a_{n}=1$ 。

多项式环 $K[X]$ 里的裴蜀定理

$K$ 为域时，对于多项式环 $K[X]$ 里的多项式，裴蜀定理也成立。设有一族 $\mathbb {K} [X]$ 里的多项式 $\left(P_{i}\right)_{i\in I}$ 。设 $\Delta$ 为它们的最大公约式（首项系数为1且次数最高者），那么存在多项式 $\left(A_{i}\right)_{i\in I}$ 使得 $\textstyle \Delta =\sum _{i\in I}A_{i}P_{i}$ 。特别来说，如果 $\left(P_{i}\right)_{i\in I}$ 互质（不是两两互质），那么存在多项式 $\left(A_{i}\right)_{i\in I}$ 使得 $\textstyle \sum _{i\in I}A_{i}P_{=}1$ 。