不定方程非负整数解

1 第4讲 不定方程的整数解

不定方程(组)是指未知数的个数多于方程的个数的方程(组)，其特点是解往往有无穷多个，不能惟一确定．

对于不定方程(组)，我们往往限定只求整数解，甚至只求正整数解，加上条件限制后，解就可确定．

二元一次不定方程是最简单的不定方程，一些复杂的不定方程(组)常常转化为二元一次不定方程问题加以解决，与之相关的性质有：

设dcba、、、为整数，则不定方程cbyax有如下两个重要命题：

(1)若(a，b)=d，且d卜c，则不定方程cbyax没有整数解；

(2)若00yx，是方程cbyax且(a，b)=1的一组整数解(称特解)，则为整数）tatyybtxx(00是方程的全部整数解(称通解)．

解不定方程(组)，没有现成的模式、固定的方法可循，需要依据方程(组)的特点进行恰当的变形，并灵活运用以下知识与方法；奇数偶数，整数的整除性、分离整系数、因数分解。配方利用非负数性质、穷举，乘法公式，不等式分析等．

【例题】

例1、求方程5x－9y=18整数解的通解. 例2、求方程90226yx非负整数解.

例3、求方程213197yx的所有正整数解. 例4、求方程2510737yx的整数解。

例5、求方程 162852100zyx的整数解.

2

例6、某校举行数学竞赛，优胜者分一、二、三等奖三种，奖品为数学课外读物。如果一等奖每人奖5本，二等奖每人奖3本，三等奖每人奖2本，就共奖了34本。如果一等奖每人奖6本，二等奖每人奖4本，三等奖每人奖1本，就共奖了28本，求获得各奖的人数.

【练习】

1、下列方程中没有整数解的是哪几个？答： （填编号）

① 4x＋2y=11, ②10x-5y=70, ③9x+3y=111,

④18x-9y=98, ⑤91x-13y=169, ⑥120x+121y=324.

形如３　＋２ｙ：１５或　＋３），＋７ｚ：１００之类的方程，　其解是无数的，并且就是连非负整数解也有多种可能，　因此求解起来较难，下面本人介绍两种求不定方程非负　整数的解法．　弓Ｉ例求２８ａ＋３０ｂ＋３１ｃ＝３６５的非负整数解．　方法一：放缩法　分析通过放大和缩小方程左边，从而得到。＋ｂ＋　ｃ的一个取值范围而完成解题．　解：由２８（口＋ｂ＋ｃ）≤２８Ⅱ＋３０ｂ＋３１ｃ＝３６５，　得ｎ＋ｂ＋ｃ≤　＜１３．０４，所以ｎ＋ｂ＋ｃ≤ｌ３．　由３１（８＋ｂ＋ｃ）≥２８８＋３０ｂ＋３１ｃ＝３６５，得　８＋ｂ＋ｃ≥　＞１１．７，所以ｎ＋ｂ＋ｃ≥１２，于是有ｎ　ｊｌ　＋ｂ＋ｃ＝１２或ｌ３．　①当０＋ｂ＋ｃ：１３时，２８ａ＋３０ｂ＋３１ｃ＝３６５：２８×　１３＋１＝２８　Ｘ（ｎ＋ｂ＋ｃ）＋１＝２８ａ＋２８ｂ＋２８ｃ＋１　）　又２８ａ＋３０ｂ＋３１ｃ＝２８（口＋ｂ＋ｃ）＋２６＋３ｃ（　比较①和②得２６＋３ｃ＝１，因为ｂ、ｃ均为非负整数，　因此，此方程２６＋３ｃ＝１无解，即ａ＋ｂ＋ｃ≠１３．　当口＋ｂ＋Ｃ＝１２时，有３０×１２＋５＝３６５，所以２８ａ＋　３０ｂ＋３１ｃ＝３６５＝３０×１２＋５＝３０（口＋ｂ＋ｃ）＋５，（　而２８ａ＋３０ｂ＋３１ｃ：３ｏ（口＋ｂ＋ｃ）＋ｃ一２ａ（　比较③、④有ｃ一２ａ＝　，再结合口＋ｂ＋ｃ＝１２，可知，　５≤ｃ≤１２且ｃ必为奇数，即ｃ可能的取值为５，７，９，１１，　因此可相应有　合条件的解只有三组：　ｃ＝１１　口＝３　显然符　．ｂ：一２．　口＝２　ｂ＝１．　ｃ＝９　思维创新　…．婆量焦煎墨三　…　《查生　方法二：奇偶法　解：由口、ｂ、ｃ为非负整数，知２８ａ＋３０ｂ为偶数，ｃ为　奇数．　令ｃ＝２ｎ＋１（，ｌ为非负整数），于是有　２８ａ＋３０ｂ＋３１（２ｎ＋１）＝３６５，化简得　１４ａ＋１５ｂ＋３１ｎ：１６７①　由于１４ａ为偶，故ｂ，ｎ必一奇一偶．　（一）ｂ偶ｎ奇，令ｂ＝２ｋ，，ｌ＝２９＋１（ｋ，ｑ为非负整　数），由①得１４ａ＋３０ｋ＋６２ｑ＋３１＝１６７，即　７口＋１５ｋ＋３１ｑ＝６８（　由（　知０≤ｑ≤２，　（１）ｑ：０时，由②得７ｎ＋１５ｋ＝６８，易知０≤ｋ≤４经　检验当ｋ＝Ｏ，１，２，３，４时，口均不是非负整数．　（２）当ｑ＝１时由②得７口＋１５ｋ＝３７，易知０≤ｋ≤２　经检验ｋ＝２，ｏ＝１为其非整数解．从而ｂ＝４，ｃ＝７．　（３）当ｑ＝２时，由②得７口＋１５ｋ＝６无非负整数解．　（二）若ｂ奇　偶，令ｂ＝２ｐ＋１，ｎ＝２ｑ（ｐ，ｑ为非负　整数）由①得７口＋１５ｐ＋３１ｑ＝７６③易知Ｏ≤ｇ≤２．　（１）当ｑ＝０时，由③得７ｎ＋１５ｐ＝７６，０≤ｐ≤５，经检　验无非负整数解．　（２）当ｑ＝１时，由③得７口＋１５ｐ＝４５，求得ａ＝０，　Ｐ＝３，从而ｂ＝７，ｃ＝５．　（３）当ｑ＝２时，由③得７。＋１５ｐ＝１４，求得０＝２，　ｐ＝０，从而ｂ＝１，ｃ＝９．　综合（一）、（二）得到方程２８ａ＋３０ｂ＋３１ｃ＝３６５的　非负整数解为　ｎ＝２　ｂ＝ｌ共三组．　Ｃ：９　Ｏ　＝　８　，，１　ＩＩ　Ⅱ，●５　０＝　．。．。．．。．．。＋。＋。．．．。．。＋。．。。．．．．．＋．．．　Ａｖ致掌大世ＩＩ｝　０＿　．１　◆．＋。．。．。．；．。．。．。＋。．。．。．。．

- 1 - 7．不定方程

A卷

1．若00yyxx是二元一次不定方程ax + by = c（其中（a、b）=1）的一组整数解，则ax +

by = c的所有整数解为____________。

2．方程 6x + 22y = 90的非负整数解为___________。

3．方程 9x + 24y – 5z = 1000的整数解为___________。

4．方程组)2(100533)1(100zyxzyx的非负整数解为______________。

5．方程(x – a )(x – 8 ) – 1 = 0有两个整数根，则a的值是___________。

6．方程0652xyx的整数解为___________。

7．方程xy – 10 (x + y ) = 1的整数解为_____________。

8．满足x > y > 0 且xyyx7733的整数x = __________，整数y = _____________。

9．不定方程 8822yx的整数解是____________。

10．

（1）方程zxy1的质数解是__________；

（2）方程azyx111（其中a是整数x、y、z互不相等）的正整数解是___________；

（3）方程2009yx的整数解是____________。

（4）方程625.202222dcba的整数解是____________。

B卷

1．不定方程22222bacba的所有整数解是____________。

2．对于正整数a和b，方程babayxyx的所有正整数解是_____________。

3．方程22225)36(6ncba的所有整数解是____________。

4．方程组1979206222zyxzyx的所有正整数解是____________。

关于⼆元⼀次不定⽅程的整数解相关结论的推导

整数解的通解公式推导

⼆元⼀次不定⽅程的⼀般形式为：ax + by = c ①

这⾥，a、b和c都是正整数，且满⾜(a,b) = 1

由(a,b) = 1知，存在⼀对整数u和v，满⾜ au + bv = 1。

取m = cu，n = cv，则m, n这⼀对整数是⽅程①的⼀组特解，即有am + bn = c ②

由①②，有a(x-m) = -b(y-n)(x-m)/b = -(y-n)/a := t

x = m + bt, y = n - at ③

由(a,b) = 1知，b | x-m，a | y-n，即⽅程①的任意⼀组整数解都有唯⼀对应的整数t，于是③便是①的所有整数解的通解公式，t可为任意整数。易知这些整数解在平⾯直⾓坐标系中处在同⼀条直线（斜率为 -a/b）上。

实际上，通解公式③只要求a、b、c为整数且满⾜(a,b)=1即可。

⾮负整数解的相关结论推导

考虑①的⾮负整数解，则③⾥的 t 需要满⾜：m + bt ≥ 0 和 n - at ≥ 0，即t ≥ -m/b = -[m/b] - {m/b} ④

t ≤ n/a = [n/a] + {n/a} ⑤

由于t为整数，⑤等价于 t ≤ [n/a]；④等价于 -t ≤ m/b = [m/b] + {m/b}，即等价于 -t ≤ [m/b]，即 t ≥ -[m/b]于是有-[m/b] ≤ t ≤ [n/a] ⑥

只要[n/a] ≥ -[m/b]，⽅程①就⼀定存在⾮负整数解。事实上，①的⾮负整数的解数为M := [n/a] + [m/b] + 1 ⑦

例如就8x + 15y = 2⽽⾔，x = 4, y = -2是其⼀组特解，代⼊⑦，有M = [-2/8] + [4/15] + 1 = -1 + 0 + 1 = 0

即8x + 15y = 2没有⾮负整数解。

⑦给出的⽅程①的⾮负整数解数M的判别式需要借助⼀组特解，以下试图只⽤常数a、b和c来表⽰M：