book
归档: OI 
flag

定理内容

关于$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} $$

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

应用

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

题目

参考资料

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

navigate_before navigate_next