貝祖等式

在數論中，裴蜀等式（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。