贝祖等式

在数论中，裴蜀等式（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世纪初的法国数学家克劳德-加斯帕·巴歇·德·梅齐里亚克。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》（Problèmes plaisants et délectables qui se font par les nombres）第二版中给出了问题的描述和证明。

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

## 整数中的裴蜀定理

对任意两个整数$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 \Z^2\}$，下面证明$A$中的最小正元素是$a$与$b$的最大公约数。

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

$$r = p-qd_0 =x_1a + y_1b - q ( x_0a + y_0b)=(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_0a + y_0b = ( x_0k + y_0l )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|\le|b/d|$及$|y|\le|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_iP_i$。特别来说，如果$\left(P_i\right)_{i\in I}$互质（不是两两互质），那么存在多项式$\left(A_i\right)_{i\in I}$使得$\textstyle \sum_{i\in I} A_iP_ = 1$。

对于两个多项式的情况，与整数时一样可以得到通解。

## 任意主理想环上的情况

裴蜀可以推广到任意的主理想环上。设环$A$是主理想环，$a$和$b$为环中元素，$d$是它们的一个最大公约元，那么存在环中元素$x$和$y$使得：

$ax + by = d$

这是因为在主理想环中，$a$和$b$的最大公约元被定义为理想$aA+bA$的生成元。

## 参考来源

- 闵嗣鹤、严士健，初等数论，高等教育出版社，2003。
- 唐忠明，抽象代数基础，高等教育出版社，2006。