裴蜀定理

定义

裴蜀定理，又称贝祖定理（Bézout’s lemma）、贝祖等式（Bézout’s identity）。是一个关于最大公约数的定理,在处理不定方程和线性丢番图方程时非常有用

内容：

对于任何整数$a$、$b$和它们的最大公约数$d$，

关于未知数x和y的线性丢番图方程$ax + by = m$有解当且仅当$m$是$d$的倍数。

这个定理的一个重要推论是：如果$a$和$b$互质（ 即它们的最大公约数为1），那么存在整数x和y使得$ax + by = 1$.

例如，考虑整数$a = 12，b = 42$：

计算最大公约数$d=\text{gcd}(12, 42) = 6$。

根据裴蜀定理，对于任何整数m，如果m是6的倍数，那么方程$12x + 42y = m$一定有整数解$x$和$y$。