定理内容

关于$x,y$的二元一次方程$ax+by=m$有解，当且仅当$m$是$d$的整数倍，其中，$d=\gcd(a,b)$

读完上面这句话，你一定会觉得这是什么辣鸡定理，感觉好没用的样子。

其实裴蜀定理还用后半部分。

对于一个二元一次的不定方程，如果我们想要求解，可以使用exgcd算法，可以求得$ax_0+by_0=d$这种方程的解，那么，怎么把这个方程的解变成$ax+by=m$的解呢？

$$ \left{\left( \frac{m}{d} x_0+\frac{kb}{d},\ \frac{m}{d} y_0-\frac{ka}{d} \right) \mid k \in \mathbb{Z} \right} $$

q (1).png

这便是方程$ax+by=m$的解集，看到这一坨，心里一定有一万个mmp要讲，其实就是把原方程的解$x_0$减去一个数，$y_0$加上一个数，使得等式依然成立。

证明

首先考虑能用exgcd求解的方程，显然我们可以用exgcd求出一组解（字母的定义与上面相同）：

$$ ax_0+by_0=d $$

我们在两边同时乘上$\frac{m}{d}$：

$$ a\frac{mx_0}{d}+b\frac{y_0m}{d}=m $$

然后我们得到要求的方程的一组解

$$ x=\frac{mx_0}{d},y=\frac{my_0}{d} $$

接着我们考虑如何求出要求的方程的所有解，撕烤一波，对原方程进行一波变换。

比如这样：

$$ ax-c+by+c=m\
a(x-\frac{c}{a})+b(x+\frac{c}{b})=m
$$

然后我们注意到当$c$是$\text{lcm}(a,b)$的$k,k\in Z$倍时，才能得到该方程的整数解。不妨设$c=k\cdot\text{lcm}(a,b)$。

由于

$$ \because \text{lcm}(a,b)\cdot\gcd(a,b)=ab\
\therefore \frac{c}{a}=k\frac{d}{b},\frac{c}{b}=k\frac{d}{a} $$

然后原方程的解就变成上一节的解集了。

读到这里，你应该已经可以知道裴蜀定理的作用了：求二元一次方程的整数解集。

最后偏一波题，这几天学数学的过程中，发现维基百科不知道比百度高到哪里去了，强烈推荐