裴蜀定理
维基百科,自由的 encyclopedia
在数论中,裴蜀等式(英语:Bézout's identity)或贝祖定理(Bézout's lemma)是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何整数 、
和
,关于未知数
和
的线性丢番图方程(称为裴蜀等式):
有整数解时当且仅当 是
及
的最大公约数
的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解
、
都称为裴蜀数,可用扩展欧几里得演算法求得。
例如,12 和 42 的最大公因数是 6,则方程 有解。事实上有
、
等。
特别来说,方程 有整数解当且仅当整数
和
互素。
裴蜀等式也可以用来给最大公约数定义: 其实就是最小的可以写成
形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。