『算法-ACM 竞赛-数学-数论』贝祖定理（裴蜀定理）

数学–数论–贝祖定理（裴蜀定理）

定理：

裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 a、b 和它们的最大公约数 d，关于未知数 x 和 y 的线性不定方程（称为裴蜀等式）：若 a,b 是整数,且 GCD(a,b)=d，那么对于任意的整数 x,y,ax+by 都一定是 d 的倍数，特别地，一定存在整数 x,y，使 ax+by=d 成立。

推论：

它的一个重要推论是：a,b 互质的充要条件是存在整数 x,y 使 ax+by=1.

推论证明：参考文库