貝祖定理

在數論中，裴蜀等式（英語：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}$。

多項式環 K [ X ] {\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。

外部連結

• 線上計算器 （頁面存檔備份，存於網際網路檔案館）