裴蜀定理

imported

notes

Published

May 21, 2012

对任意两个整数 $a$ 、 $b$ ，设 $d$ 是它们的最大公约数。那么关于未知数 $x$ 和 $y$ 的线性丢番图方程（称为裴蜀等式 ）：

![displaystyle ax+by=m](http://upload.wikimedia.org/wikipedia/zh/math/8/5/a/85a5f5d0f5ec25a70f28f539be85a695.png)

有整数解(x ,y) 当且仅当 m 是 d 的倍数。裴蜀等式有解时必然有无穷多个解。证明：如果 $a$ 和 $b$ 中有一个是0，比如 $a=0$ ，那么它们两个的最大公约数是 $b$ 。这时裴蜀等式变成 $displaystyle by=m$ ，它有整数解(x ,y) 当且仅当 m 是 d 的倍数，而且有解时必然有无穷多个解，因为 $x$ 可以是任何整数。定理成立。以下设 $a$ 和 $b$ 都不为0。设 $A = {xa+yb; (x;y) in Z^2}$ ，下面证明 $A$ 中的最小正元素是 $a$ 与 $b$ 的最大公约数。这个证明复杂且怪异，个人推荐算导上的证明，详情请见：http://localhost:8080/?p=581 在方程 $ax+by=m$ 中，如果 $m= m_0 d_0$ ，那么方程显然有无穷多个解：

这里附上通解公式：$(x_0-bt,y_0+at )$(t∈$\mathbb{Z}$) 
关于通解公式推导请见：[http://localhost:8080/?p=622](http://localhost:8080/?p=622)


个人认为这里的“显然”太简略，无穷性可根据通解公式得出。









参考资料：[http://zh.wikipedia.org/wiki/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86](http://zh.wikipedia.org/wiki/%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86) 并加以修改