0 MathBasics
裴蜀定理
定义
裴蜀定理,又称贝祖定理(Bézout's lemma)、贝祖等式(Bézout's identity)。是一个关于最大公约数的定理。
其内容是:
设 是不全为零的整数,对任意整数 ,满足 ,且存在整数 , 使得 .
证明
对于第一点
由于
所以 ,其中 均为整数
因此
对于第二点
-
若任何一个等于 , 则 . 这时定理显然成立。
-
若 不等于 .
由于 ,
不妨设 都大于 ,.
对 , 两边同时除以 , 可得 , 其中 .
转证 .
我们先回顾一下辗转相除法是怎么做的,由 我们把模出来的数据叫做 于是,有
把辗转相除法中的运算展开,做成带余数的除法,得
不妨令辗转相除法在除到互质的时候退出则 所以有( 被换成了 ,为了符合最终形式)
即
由倒数第三个式子 代入上式,得
然后用同样的办法用它上面的等式逐个地消去 ,
可证得 . 这样等于是一般式中 的情况。
推广
逆定理
设 是不全为零的整数,若 是 的公因数,且存在整数 , 使得 ,则 。
特殊地,设 是不全为零的整数,若存在整数 , 使得 ,则 互质。
多个整数
裴蜀定理可以推广到 个整数的情形:设 是不全为零的整数,则存在整数 , 使得 。其逆定理也成立:设 是不全为零的整数, 是 的公因数,若存在整数 , 使得 ,则 。