二元一次不定方程的通解证明

JustPureH2O · 2023-12-21 16:05:15 · 个人记录

实际应用中，我们会被要求判断方程是否有整数解、或求出x或y的最大/最小正整数值、判断是否有正整数解、以及正整数解的组数等。首先对于有无整数解，与B\acute ezout定理证明相同，即(a,b)\mid c时有整数解。

正整数解存在性：对于根的大小，由于ax+by=c，a、b、c都是常数，因此x增大时y将减小。当x取最小正整数值时y将是最大整数值（y不一定是正数，反之亦然）。此时如果x\cdot y>0，即两者同号（x>0），有正整数解；如果x\cdot y\leq0则表明无正整数解。

方程通解及最值问题：我们需要构造方程的通解来解决这个问题。

首先根据exgcd求出的整数解x_0和y_0，有ax_0+by_0=(a,b)

根据B\acute ezout定理，(a,b)=m\cdot c,m\in\mathbb Z。两边同除以m得a\frac{x_0}{m}+b\frac{y_0}{m}=c，因为m=\frac{(a,b)}{c}，所以a\frac{c\cdot x_0}{(a,b)}+b\frac{c\cdot y_0}{(a,b)}=c。以上又是一组特解，记作x_1和y_1，则：

这个式子同样也满足上面这个形式：a(x_1+db)+b(y_1-da)=c（拆括号消去即可），那么d_x=db,d_y=da。

要想它变成一组通解，它必须得满足x和y是整数的条件。将新解写出来就是：x_1=\frac{c-by_1}{a}=\frac{c-by_1+dab}{a}。

因为x_1=\frac{c-by_1}{a}，因此c-by_1必定是a的倍数，如果要满足x_1也是一个整数，那么dab也必须是a的整数倍。同理dab也得是b的整数倍。

很显然，a是a的倍数、b是b的倍数，那么a\mid dab和b\mid dab可以转化成a\mid db与b\mid da的存在性问题。

当d=\frac{1}{(a,b)}时d_x,d_y最小。通解就可以表示成：

可以看出：s增大，x增大，y减小，当s最大时x最大，y最小，反之亦然。题目中要求x>0,y>0，则有如下不等式组：