數論中,裴蜀等式(英語:Bézout's identity)或貝祖定理Bézout's lemma)是一個關於最大公約數(或最大公約式)的定理。裴蜀定理得名於法國數學家艾蒂安·裴蜀,說明了對任何整數 ,關於未知數 線性丟番圖方程(稱為裴蜀等式):

有整數解時當且僅當 最大公約數 倍數。裴蜀等式有解時必然有無窮多個整數解,每組解 都稱為裴蜀數,可用擴展歐幾里得演算法求得。

例如,12 和 42 的最大公因數是 6,則方程 有解。事實上有 等。

特別來說,方程 有整數解當且僅當整數 互素

裴蜀等式也可以用來給最大公約數定義: 其實就是最小的可以寫成 形式的正整數。這個定義的本質是整環中「理想」的概念。因此對於多項式整環也有相應的裴蜀定理。

歷史

編輯

歷史上首先證明關於整數的裴蜀定理的並不是裴蜀,而是17世紀初的法國數學家克勞德-加斯帕·巴歇·德·梅齊里亞克法語Claude-Gaspard Bachet de Méziriac。他在於1624年發表的著作《有關整數的令人快樂與愜意的問題集》(Problèmes plaisants et délectables qui se font par les nombres)第二版中給出了問題的描述和證明[1]

然而,裴蜀推廣了梅齊里亞克的結論,特別是探討了多項式中的裴蜀等式,並給出了相應的定理和證明[2]

整數中的裴蜀定理

編輯

對任意兩個整數  ,設 是它們的最大公約數。那麼關於未知數  線性丟番圖方程(稱為裴蜀等式):

 

有整數解  當且僅當  的整數倍。裴蜀等式有解時必然有無窮多個解。

證明

如果    中有一個是0,比如 ,那麼它們兩個的最大公約數是 。這時裴蜀等式變成 ,它有整數解 當且僅當  的倍數,而且有解時必然有無窮多個解,因為 可以是任何整數。定理成立。

以下設  都不為0。

 ,下面證明 中的最小正元素是  的最大公約數。

首先,  不是空集(至少包含  ),因此由於自然數集合是良序的, 中存在最小正元素 。考慮 中任意一個正元素  )對 帶餘除法:設 ,其中 為正整數, 。但是

 

因此   。也就是說, 中任意一個正元素 都是   的倍數,特別地:  。因此    公約數

另一方面,對  的任意正公約數 ,設  ,那麼

 

因此 。所以   最大公約數

在方程 中,如果  ,那麼方程顯然有無窮多個解:

 

相反的,如果 有整數解,那麼 ,於是由前可知  (即  )。

 時,方程有解當且僅當  互質。方程有解時,解的集合是

 。其中 是方程 的一個解,可由輾轉相除法得到。

所有解中,恰有二解 滿足  ,等號只會在  其中一個是另一個的倍數時成立。輾轉相除法給出的解會是這兩解中的一個。

例子

編輯

丟番圖方程  沒有整數解,因為504和651的最大公約數是21。而方程 是有解的。為了求出通解,可以先約掉公約數21,這樣得到方程:

 

通過擴展歐幾里得算法可以得到一組特解  

特解 的求法
 
 
 
 
 
 
 為滿足 的解

 代回 ,解一元一次方程式得 
 代回 ,得 
 代回 ,得 
 為一組特解

於是通解為: ,即

 

多個整數間的裴蜀定理

編輯

  個整數, 是它們的最大公約數,那麼存在整數  使得  。特別來說,如果 互質(不是兩兩互質),那麼存在整數  使得  

多項式環裡的貝祖定理

編輯

 時,對於多項式環 裡的多項式,裴蜀定理也成立。設有一族 裡的多項式 。設 為它們的最大公約式(首項係數為1且次數最高者),那麼存在多項式 使得 。特別來說,如果 互質(不是兩兩互質),那麼存在多項式 使得 

對於兩個多項式的情況,與整數時一樣可以得到通解。

任意主理想環上的情況

編輯

裴蜀可以推廣到任意的主理想環上。設環 是主理想環,  為環中元素, 是它們的一個最大公約元,那麼存在環中元素  使得:

 

這是因為在主理想環中,  的最大公約元被定義為理想 生成元

參見

編輯

參考來源

編輯
  1. ^ 原版的网上版本(法文). [2008-08-26]. (原始內容存檔於2014-09-08). 
  2. ^ 证明的网上版本(法文). [2008-08-26]. (原始內容存檔於2019-12-01). 
  • 閔嗣鶴、嚴士健,初等數論,高等教育出版社,2003。
  • 唐忠明,抽象代數基礎,高等教育出版社,2006。

外部連結

編輯