貝祖定理

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