貝祖定理
在數論中,裴蜀等式(英語:Bézout's identity)或貝祖定理(Bézout's lemma)是一個關於最大公約數(或最大公約式)的定理。裴蜀定理得名於法國數學家艾蒂安·裴蜀,說明了對任何整數 、 和 ,關於未知數 和 的線性丟番圖方程(稱為裴蜀等式):
有整數解時當且僅當 是 及 的最大公約數 的倍數。裴蜀等式有解時必然有無窮多個整數解,每組解 、 都稱為裴蜀數,可用擴展歐幾里得演算法求得。
例如,12 和 42 的最大公因數是 6,則方程 有解。事實上有 、等。
特別來說,方程 有整數解當且僅當整數 和 互素。
裴蜀等式也可以用來給最大公約數定義: 其實就是最小的可以寫成 形式的正整數。這個定義的本質是整環中「理想」的概念。因此對於多項式整環也有相應的裴蜀定理。
歷史
編輯歷史上首先證明關於整數的裴蜀定理的並不是裴蜀,而是17世紀初的法國數學家克勞德-加斯帕·巴歇·德·梅齊里亞克。他在於1624年發表的著作《有關整數的令人快樂與愜意的問題集》(Problèmes plaisants et délectables qui se font par les nombres)第二版中給出了問題的描述和證明[1]。
整數中的裴蜀定理
編輯對任意兩個整數 、 ,設 是它們的最大公約數。那麼關於未知數 和 的線性丟番圖方程(稱為裴蜀等式):
有整數解 當且僅當 是 的整數倍。裴蜀等式有解時必然有無窮多個解。
如果 和 中有一個是0,比如 ,那麼它們兩個的最大公約數是 。這時裴蜀等式變成 ,它有整數解 當且僅當 是 的倍數,而且有解時必然有無窮多個解,因為 可以是任何整數。定理成立。
以下設 和 都不為0。
設 ,下面證明 中的最小正元素是 與 的最大公約數。
首先, 不是空集(至少包含 和 ),因此由於自然數集合是良序的, 中存在最小正元素 。考慮 中任意一個正元素 ( )對 的帶餘除法:設 ,其中 為正整數, 。但是
因此 , 。也就是說, 中任意一個正元素 都是 的倍數,特別地: 、 。因此 是 和 的公約數。
另一方面,對 和 的任意正公約數 ,設 、 ,那麼
因此 。所以 是 和 的最大公約數。
在方程 中,如果 ,那麼方程顯然有無窮多個解:
- 。
相反的,如果 有整數解,那麼 ,於是由前可知 (即 )。
時,方程有解當且僅當 、 互質。方程有解時,解的集合是
- 。其中 是方程 的一個解,可由輾轉相除法得到。
所有解中,恰有二解 滿足 及 ,等號只會在 及 其中一個是另一個的倍數時成立。輾轉相除法給出的解會是這兩解中的一個。
例子
編輯丟番圖方程 沒有整數解,因為504和651的最大公約數是21。而方程 是有解的。為了求出通解,可以先約掉公約數21,這樣得到方程:
- 。
通過擴展歐幾里得算法可以得到一組特解 : 。
- 令
- 令
- 取 為滿足 的解
- 將 代回 ,解一元一次方程式得
- 將 代回 ,得
- 將 代回 ,得
- 故 為一組特解
於是通解為: ,即
- 。
多個整數間的裴蜀定理
編輯設 為 個整數, 是它們的最大公約數,那麼存在整數 使得 。特別來說,如果 互質(不是兩兩互質),那麼存在整數 使得 。
多項式環裡的貝祖定理
編輯為域時,對於多項式環 裡的多項式,裴蜀定理也成立。設有一族 裡的多項式 。設 為它們的最大公約式(首項係數為1且次數最高者),那麼存在多項式 使得 。特別來說,如果 互質(不是兩兩互質),那麼存在多項式 使得 。
對於兩個多項式的情況,與整數時一樣可以得到通解。
任意主理想環上的情況
編輯裴蜀可以推廣到任意的主理想環上。設環 是主理想環, 和 為環中元素, 是它們的一個最大公約元,那麼存在環中元素 和 使得:
這是因為在主理想環中, 和 的最大公約元被定義為理想 的生成元。
參見
編輯參考來源
編輯- ^ 原版的网上版本(法文). [2008-08-26]. (原始內容存檔於2014-09-08).
- ^ 证明的网上版本(法文). [2008-08-26]. (原始內容存檔於2019-12-01).
- 閔嗣鶴、嚴士健,初等數論,高等教育出版社,2003。
- 唐忠明,抽象代數基礎,高等教育出版社,2006。