初等数论基础-§3.1二元一次不定方程

本节讨论二元一次不定方程有整数解的判别条件及其求解方法.先给出二元一次不定方程的概念.为简单起见，本章以下用“有解”一词来表示不定方程有整数解.

定义3.1.1　设a，b，c∈Z且a，b均不为零，则称ax+by=c为二元一次不定方程.

首先给出二元一次不定方程有解的判别定理.

定理3.1.2　二元一次不定方程ax+by=c有解当且仅当（a，b）|c.

证明　若（x0，y0）是方程的解，则ax0+by0=c.注意到（a，b）|a且（a，b）|b，有（a，b）|ax0+by0=c.反之，若（a，b）|c，则可设c=（a，b）u.据推论1.2.7知存在s，t∈Z使得as+bt=（a，b）.于是asu+btu=（a，b）u=c.这表明（su，tu）就是ax+by=c的解.证毕.

定理3.1.3　设（x0，y0）是二元一次不定方程ax+by=c的一个解.则该不定方程的全部解为

证明　容易验证等式（3.1.1）所表达的（x，y）是不定方程ax+by=c的解.反之，若（u，v）是不定方程ax+by=c的解，则au+bv=c=ax0+by0，即

这表明　注意到有　故存在t∈Z使得将其带入（3.1.2）便可得证毕.

由定理3.1.3可知求二元一次不定方程的解只需求出其一个特解.下面说明在方程ax+by=c有解的情况下如何求其一个解.若ax+by=c有解，则（a，b）|c.于是，ax+by=c与

同解.注意到用定理1.2.6的方法可求出s，t∈Z使得

于是这表明是ax+by=c的一个解.

下面通过具体的例子来阐述二元一次不定方程的解法.

例3.1.4　求不定方程306x-360y=630的一切整数解.(www.xing528.com)

解　由（306，-360）=18|630知方程有解.原方程同解于17x-20y=35.先求17x+20y=1的特解.据定理1.2.6，作辗转相除法：

17=0×20+17，20=1×17+3，17=5×3+2，3=1×2+1，2=2×1+0.

故1=r4=17［（-1）4-1Q4］+20［（-1）4P4］，其中

故17×（-7）+20×6=1.这表明（-7，6）是17x+20y=1的一解，从而（-7，-6）是17x-20y=1的一解.于是（-7×35，-6×35）=（-245，-210）是17x-20y=35的一解，当然也是原方程的一解.故

就是原方程的一切整数解.解毕.

例3.1.5　求不定方程107x+37y=25的一切整数解.

解　由（107，37）=1|25知该方程有解.由原方程可得记则则u=4v+1.将u带入x的表达式得x=3+37v，进而得y=-8-107v.故

就是该方程的一切整数解.解毕.

注3.1.6　上例的解法是中学常用的解二元一次不定方程的方法.它的理论基础还是辗转相除法，只是表现形式有所不同.

例3.1.7　求不定方程258x+162y=-24的一切整数解.

解　由（258，162）=6|-24知方程有解.容易看出原方程同解于43x+27y=-4.先求43x+27y=1的特解.由43x+27y=1知记u=则记则5u-11v=1.容易看出（-2，-1）是5u-11v=1的一个解.逐步回代可得43x+27y=1的一解（-5，8）.于是（（-5）×（-4），8×（-4））是43x+27y=-4的一解，也就是原方程的一解.故就是原方程的一切整数解.解毕.

注3.1.8　在上例中，先用中学方法求得了特解，然后根据定理3.1.3写出了方程的全部解.