手推贝祖定理 Bézout’s lemma

[mathjax]

贝祖定理 Bézout’s lemma

贝祖定理

定理

1. 对任意整数$a,b,m$，[[pkg/线性丢番图方程]] $ax+by=m$ 存在整数解$x,y$的充要条件是$m$是最大公约数 $d$ 的整倍数
2. 当 $ax+by=m$ 存在整数解的时候，有无穷多个解。

证明定理一

充分性证明

$x,y$存在整数解时，$m$是$a$和$b$的最大公约数$d$的整倍数

给定 $a，b$，让我们定义集合 $M$是使上述丢番图方程$ax+by=m$成立的所有解$x,y$对应的$m$的集合，则可把定义写为 \(M = {ax+by, x,y \in \mathbb{Z}, ax+by>0 }\)。

首先根据定义$M$集合必然为自然数集的子集。

假定M中的最小数为$d_0$，对应$x_0,y_0$，那么$ax_0+by_0 = d_0$ 现在用 $a$对$d_0$做带余数除法 $a = qd_0+r$,

必然满足

$0<= r < d$

然而又有

\[\begin{eqnarray} a &=& (ax_0+by_{0}+r)r \nonumber \\ &=& a-qd_{0} \nonumber \\ &=& a-q(ax_{0}+by_{0}) \nonumber \\ &=& a(1-q)x_{0}+ qby_{0} \nonumber \\ \end{eqnarray}\]

可以定义 $x_1=(1-q)x_{0,}y_1=qy_0$ 满足M的定义，故而$r \in M \cup {0}$ 。用两个等式相交

\[r \in M \cup {0} \wedge 0<=r<d\]

因此$r=0$，从而证明了 $d_0$是$a$的整约数，同理$d_0$是$b$的整约数，因此$d_0$是$a$和$b$公共整约数。

现在证明 $d_0$是$a$和$b$的最大公约数。

假定$a$和$b$存在$d_0$之外的另外一个公约数$d_1$，从而存在整数$p,q$满足 $pd_1= a,qd_1= b$

那么必然存在

$d_0= ax_0+ by_0= pd_1x_0+ qd_1y_0= d_1(px_0+qy_0)$

从而 $d_1$是$d_0$的一个约数，考虑到$d_0>0$，则$d_1<=d_0$，证明了$d_0$是$a,b$的最大公约数

必要性证明

$m$是$a$和$b$的最大公约数$d$的整倍数时，$x,y$存在整数解时

反过来，当$m$是$a,b$的最大公约数$d_0$的整倍数时候，也就是存在正整数q使得$m = qd_0$的时候$m = qd_0 = q(ax_0+by_0)$，从而$x_0,y_0$是使得上述方程成立的一对解

证明定理二

现在证明当 $ax+by=m$ 存在整数解的时候，有无穷多个解。

我们上面已经证明定理一：$m$必须是$a,b$的最大公约数$d_0$的整数倍。

从这个前提出发，假定$m=d_0$, $d_0 = ax_0 + y_0$对应的${x_0,y_0}$是其中一对解 由于 $ax_0 + by_0 = ax+by => x = (ax_0+by_0 -by)/a = x_0 + (y_0-y)b/a$ 满足所有条件的$x，y$都是解。因为$x_0$是整数、$y_0$也是整数，只要满足$(y_0-y)$能整除$a$就可以了，从而证明有无数多个解。

推论

$ax+by=1$有整数解，当前仅当 $a,b$ 互质