貝祖等式
在数论中,裴蜀等式(英語: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。