貝祖等式

  此條目介紹的是数论中的贝祖等式。关于代数几何中的贝祖定理，请见「贝祖定理」。

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

${\displaystyle ax+by=m}$

有整数解时当且仅当 ${\displaystyle m}$ 是 ${\displaystyle a}$ 及 ${\displaystyle b}$ 的最大公约数 ${\displaystyle d}$ 的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 ${\displaystyle x}$、${\displaystyle y}$ 都稱為裴蜀數，可用擴展歐幾里得演算法求得。

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

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

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

历史

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

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

整数中的裴蜀定理

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

${\displaystyle \displaystyle ax+by=m}$ 

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

证明：

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

以下设${\displaystyle a}$ 和 ${\displaystyle b}$ 都不为0。

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

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

${\displaystyle 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}$ 

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

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

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

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

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

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

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

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

${\displaystyle \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\}}$ 。其中${\displaystyle (x_{0},y_{0})}$ 是方程${\displaystyle ax+by=d}$ 的一个解，可由辗转相除法得到。

所有解中，恰有二解${\displaystyle (x,y)}$ 满足${\displaystyle |x|\leq |b/d|}$ 及${\displaystyle |y|\leq |a/d|}$ ，等號只會在${\displaystyle a}$ 及${\displaystyle b}$ 其中一個是另一個的倍數時成立。輾轉相除法給出的解會是這兩解中的一個。

例子

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

${\displaystyle 24x+31y=1}$ 。

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

特解${\displaystyle (x,y)=(-9,7)}$ 的求法

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

${\displaystyle {\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}}}}$ 

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

${\displaystyle {\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}}}}$ 

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

${\displaystyle {\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}}}}$ 

取${\displaystyle b=1}$ 為滿足${\displaystyle 1-b\equiv 0{\pmod {3}}}$ 的解

---

將${\displaystyle b=1}$ 代回${\displaystyle 1-3a=7b}$ ，解一元一次方程式得${\displaystyle a=-2}$ 

將${\displaystyle a=-2}$ 代回${\displaystyle 1-7y=24a}$ ，得${\displaystyle y=7}$ 

將${\displaystyle y=7}$ 代回${\displaystyle 24x+31y=1}$ ，得${\displaystyle x=-9}$ 

故${\displaystyle (x,y)=(-9,7)}$ 為一組特解

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

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

多个整数间的裴蜀定理

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

多项式环${\displaystyle K[X]}$裡的貝祖定理

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

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

任意主理想环上的情况

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

${\displaystyle ax+by=d}$ 

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

参见

• 理想 (环论)
• 欧几里德整环
• 欧几里德引理
• 主理想环
• 整除

参考来源

1. 原版的网上版本（法文）. [2008-08-26]. （原始内容于2014-09-08）. 
2. 证明的网上版本（法文）. [2008-08-26]. （原始内容于2019-12-01）. 

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

外部連結

• 線上計算器 （页面存档备份，存于互联网档案馆）