初等数论-解二元一次不定方程

本节讨论二元一次不定方程有无整数解的判定和有解时的求法.

定义1 方程ax＋by=c（a，b，c∊Z，ab≠0)叫作二元一次不定方程，其中x，y是未知数.

对于二元一次不定方程而言，有时有整数解，而有时没有整数解.例如，3x-y=2显然有整数解，而2x＋4y=5就没有整数解.

关于二元一次不定方程满足什么条件时有整数解？如何判定其有无整数解？我们有下面的定理.

定理1 方程ax＋by=c（a，b，c∊Z，ab≠0)有整数解⇔（a，b)|c.

证明 必要性.

设ax＋by=c（a，b，c∊Z，ab≠0)有整数解（x0，y0)，则

∵（a，b)|a，（a，b)|b，∴（a，b)|c.

充分性.

∵（a，b)|c，∴c=（a，b)c′（c′∊Z).

由第一章欧拉算法可知，存在整数s，t，满足as＋bt=（a，b)，

∴asc′＋btc′=（a，b)c′=c，

故x0=sc′，y0=tc′是方程ax＋by=c（a，b，c∊Z，ab≠0)的一个整数解.

例1 判断下列方程是否有整数解：

（1)54x＋37y=1；（2)11x-17y=7；

（3)24x-56y=72；（4)4x＋2y-1=0.

解 （1)因为（54，37)=1|1，所以有解.

（2)因为（11，17)=1|7，所以有解.

（3)因为（24，56)=8|72，所以有解.

（4)因为（4，2)=2|/1，所以无解.

由例1（3)可见，当方程ax＋by=c（a，b，c∊Z，ab≠0)满足（a，b)|c时，方程等号两边可以同除以（a，b)，使得未知数的系数互质，而由例1（1)和（2)可见，当未知数的系数互质时，方程组一定有整数解.因此，我们可以得到定理的如下推论.

推论 当方程ax＋by=c（a，b，c∊Z，ab≠0)满足（a，b)=1时，必有整数解.

从定理充分性的证明不难看出，当方程有解时（本章中的解均指整数解，下同)，只要求出整数s，t，c′即可得到方程的一个解.其关键是求出s，t，而这并不困难，只要用第一章介绍的欧拉算法必能求出，甚至，简单的题目通过观察实验就可得到一个解.

方程的一个解叫作它的一个特解.

下面我们先举例说明求特解的观察实验法，而一般性方法如欧拉算法、分离整数法、解同余方程法等，稍后再加以介绍.

当方程的系数和常数比较小或具有某些特点时，可用观察实验法.

例2 求方程的特解：

（1)4x＋5y=0；（2)x-15y=19；

（3)7x-4y=1；（4)3x＋5y=1306.

解 （1)常数为0，未知数均取0即可，故特解为（0，0).

（2)当有一个未知数的系数绝对值为1时，则令另一个未知数取1即可，故令y=1，则x=19＋15=34.故一个特解为（x，y)=（34，1).

（3)两个系数与常数关系比较明显，直接取值即可.故一个特解为

（4)系数绝对值较小，而常数绝对值较大，则常数先取1.即先解

得其特解3×2＋5×（-1)=1，两边同乘常数1306，得

故原方程的一个特解为（x，y)=（2612，-1306).

求方程的一个或几个特解往往不能满足我们的要求，我们还应当关注当方程有整数解时有多少个？如何求出所有的整数解？如何求出满足某种特殊条件的整数解？对此，我们有如下结论.

定理2 设方程ax＋by=c（a，b，c∊Z，ab≠0)满足（a，b)=1，若方程有一个特解（x0，y0)，则其全部整数解可表示为

∵（x0，y0)是方程的一个特解，∴ax0＋by0=c.

设（x′0，y′0)是方程的任意一个整数解，则ax′0＋by′0=c.

∵ax0＋by0=c，∴a（x′0-x0)＋b（y′0-y0)=0.(www.xing528.com)

∴a（x′0-x0)=-b（y′0-y0)，∴b|a（x′0-x0).

∵（a，b)=1，∴b|（x′0-x0)，∴x′0-x0=bt（t∊Z).

∴x′0=x0＋bt.

∵a（x′0-x0)=-b（y′0-y0)，∴y′0=y0-at.

要注意通解公式中t的系数与方程未知数系数的关系特点.

值得注意的是，定理的关键性条件是方程中未知数的系数互质，这不仅保证了方程一定有解，而且保证了通解公式的正确性.

这就提醒我们，遇到未知数系数不互质而又有解的方程，求解时要先化简，再求解.

下面我们介绍方程的解法，其中包括求特解的几个一般性方法和写通解的注意事项.

例3 解方程119x-105y=217.

解 因为（119，105)=7|217，所以方程有整数解.化简得

方法1 用欧拉算法.

由第一章欧拉算法得1=17×（-7)-15×（-8).故故一个特解为（-217，-248)，故通解为

值得注意的是，在简化前后的两个通解式中，处于特解位置的两组值，相差x，y各自表达式中t的系数的相同的整数倍.即

方法2 分离整数法.

通过分离出整数、逐渐减小系数的方法求特解.

两个未知数系数的绝对值中的较小者是15，用15去除方程两边，分离出整数，方程变形为

观察可见，取x=8，则y=7，方程的一个特解为x=8，y=7.

请读者思考：为何用两个未知数系数的绝对值中的较小者去除方程两边？这是必须的吗？

方法3 解同余方程法.

把方程化为两个同余方程

选两者之一（如前者)解之得x≡8（mod15)，即x=8＋15t（t∊Z).

代入原方程解得：y=7＋17t.

请大家自己取另一个同余方程试解.

例4 一个自行车选手在相距950千米的甲、乙两地之间训练.去时从甲地出发，每90千米休息一次，到达乙地休息一天后沿原路返回，返回时每100千米休息一次，他发现恰有一个休息地点与去时相同，这个休息地点距甲地多少千米？

解 因为950=90×10＋50，所以该选手从甲地出发到乙地去时共休息10次，且各次休息地距离甲地90m千米（m=1，2，…，10)；同理，他从乙地返回甲地时休息9次，第9次距离甲地50千米，所以返回时各次休息地距离甲地100n＋50千米（n=1，2，…，9).而去、回同一休息地到甲地的距离是一个定值，故由题意可得方程：

观察可得一个特解：（m，n)=（5，4).故其所有整数解为

故（m，n)=（5，4)，即该休息地距离甲地90×5=450千米.

习题3.1

1.判断下列方程有无整数解：

（1)16x＋34y=7；（2)54x-48y=12；（3)2x＋y=8；（4)24x-56y=72.

2.用观察实验法求下列方程的一个特解：

（1)5x-6y=7；（2)7x-9y=193.

3.用欧拉算法解下列方程：

（1)15x＋37y=1；（2)24x-56y=72.

4.用分离整数法解下列方程：

（1)5x＋78y=7；（2)22x＋6y=368.

5.有大小两种装月饼的盒子，大盒可装7块，小盒可装4块，要把41块月饼装满盒子，需要大、小盒各几个？

7.某地水费不超过10吨时，每吨4.5元，超过10吨时超过部分每吨8元.庄家比李家多交水费33元，若两家用水量都是整吨数，问两家各交水费多少元？

8.某人发现自己去年（2017)的年龄恰好是出生年号4个数字之和，求其今年年龄？