初等数论教案4new

1、第八节 一次不定方程设a1, a2, L, an是非零整数，b是整数，称关于未知数x1, x2, L, xn的方程()a1x1 + a2x2 + L + anxn = b (1)是n元一次不定方程.若存在整数x10, x20, L, xn0满足方程(1)，则称(x10, x20, L, xn0)是方程(1)的解，或说x1 = x10，x2 = x20，L，xn = xn0是方程(1)的解.1、定理1 方程(1)有解的充要条件是(a1, a2, L, an)b. (2)证明：记d = (a1, a2, L, an).若方程(1)有解，设为(x1, x2, L, xn).则由dai（1 i n）及

2、整除的性质容易知道式(2)成立. 必要性得证.另一方面，存在整数y1, y2, L, yn使得a1y1 + a2y2 + L + anyn = (a1, a2, L, an) = d.因此，若式(2)成立，则就是方程(1)的解，充分性得证. 证毕2、定理2 设a，b，c是整数，方程ax + by = c (3)若有解(x0, y0)，则它的一切解具有， tZ (4)的形式，其中.证明：容易验证，由式(4)确定的x与y满足方程(3). 下面证明，方程(3)的解都可写成式(4)中的形式.设(x, y)是方程(3)的解，则由ax0 + by0 = ax + by = c得到a(x - x0) = -

3、b(y - y0)，.由此，以及得到x - x0，因此存在整数t，使得.证毕定理1和定理2说明了解方程(3)的步骤：() 判断方程是否有解，即(a, b)c是否成立；() 利用辗转相除法求出x0，y0，使得ax0 + by0 = (a, b)；() 写出方程(3)的解3、定理3 设a1, a2, L, an, b是整数，再设 (a1, a2, L, an - 1) = dn - 1，(a1, a2, L, an) = dn，则(x1, x2, L, xn)是方程(1)的解的充分必要条件是存在整数t，使得(x1, x2, L, xn, t)是方程组 (5)的解.证明：若有整数t，使得(x1, x

4、2, L, xn, t)是方程组(5)的解，则显然(x1, x2, L, xn)满足方程(1).设(x1, x2, L, xn)是方程(1)的解，则a1x1 + a2x2 + L + an - 1xn - 1 + anxn = b. (6)令a1x1 + a2x2 + L + an - 1xn - 1 = b，则 dn - 1 = (a1, a2, L, an - 1)b.因此，存在tZ，使得a1x1 + a2x2 + L + an - 1xn - 1 = dn - 1t， (7)再由式(6)，得到dn - 1t + anxn = b，即(x1, x2, L, xn, t)满足方程组(5).

5、证毕定理3说明了求解n元一次不定方程的方法：先解方程组(5)中的第二个方程，再解方程组(5)中的第一个方程，于是，解n元一次不定方程就化为解n - 1元一次不定方程.重复这个过程，最终归结为求解二元一次不定方程. 记(a1, a2) = d2，(d2, a3) = d3，L，(dn - 2, an - 1) = dn - 1，(dn - 1，an) = dn，逐个地解方程dn - 1tn - 1 + anxn = b，dn - 2tn - 2 + an - 1xn - 1 = dn - 1tn - 1， L L d2t2 + a3x3 = d3t3，a1x1 + a2x2 = d2t2，并且消

6、去中间变量t2, t3, L, tn - 1，就可以得到方程(1)的解.例1 求不定方程3x + 6y = 15的解.解 (3, 6) = 315，所以方程有解.由辗转相除法（或直接观察），可知x = -1，y = 1是3x + 6y = 3的解，所以x0 = -5，y0 = 5是原方程的一个解.由定理2，所求方程的解是， tZ.例2 求不定方程3x + 6y + 12z = 15的解.解 原方程等价于x + 2y + 4z = 5. (8)由定理3，依次解方程t + 4z = 5，x + 2y = t，分别得到 ， uZ， (9)， vZ. (10)将式(9)与式(10)中的t消去，得到，

7、u, vZ.注：本例在解方程时，首先将原方程化为等价方程(8)，这使问题简化. 例1也可以如此处理.例3 设a与b是正整数，(a, b) = 1，则任何大于ab - a - b的整数n都可以表示成n = ax + by的形式，其中x与y是非负整数，但是n = ab - a - b不能表示成这种形式.解 () 由定理2，方程ax + by = n (11)的解具有， tZ (12)的形式，其中x0与y0满足方程(11).由假设条件n ab - a - b及式(11)与式(12)，有ax = n - by = n - b(y0 - at) ab - a - b - b(y0 - at). (13)

8、取整数t，使得0 y = y0 - at a - 1，则由式(13)得到ax ab - a - b - b(a - 1) = -a，x -1，x 0，即n = ax + by，x 0，y 0.() 设有x 0，y 0，使得ax + by = ab - a - b， (14)则a(x + 1) + b(y + 1) = ab. (15)所以ab(y + 1).但是(a, b) = 1，于是必有ay + 1，y + 1 a.同理可以证明x + 1 b，从而a(x + 1) + b(y + 1) 2ab，这与式(15)矛盾，所以 (14) 式是不可能的.例4 设a，b，c是整数，(a, b) = 1

9、，则在直线ax + by = c上，任何一个长度大于的线段上至少有一个点的坐标都是整数.解 由定理2，直线ax + by = c上的坐标都是整数的点(xt, yt)的坐标是， tZ，其中(x0, y0)是直线ax + by = c上的坐标都是整数的点，由定理1，这样的点是存在的.对于任意的tZ，记Pt是以(xt, yt)为坐标的点，则Pt + 1与Pt 之间的距离.这说明，两个“相邻的”坐标是整数的点的距离是，从而得出所求之结论.例5 将写成三个分数之和，它们的分母分别是2，3和5.解 设，则15x + 10y + 6z = 19.依次解方程5t + 6z = 19，15x + 10y = 5

10、t，得到， uZ， (16)， vZ. (17)从式(16)与式(17)中消去t，得到， u, vZ.取u = 0，v = 0，得到x = -1，y = 1，z = 4，因此.例6 甲物每斤5元，乙物每斤3元，丙物每三斤1元，现在用100元买这三样东西共100斤，问各买几斤?解 设买甲物x斤，乙物y斤，丙物z斤，则5x + 3y +z = 100，x + y + z = 100.消去z，得到7x + 4y = 100. (18)显然x = 0，y = 25是方程(18)的解，因此，方程(18)的一般解是 ， tZ因为x 0，y 0，所以0 t 3.即t可以取值t1 = 0，t2 = 1，t3

11、= 2，t4 = 3. 相应的x，y，z的值是(x, y, z) = (0, 25, 75)，(4, 18, 78)，(8, 11, 81)，(12, 4, 84).例7 求不定方程x + 2y + 3z = 7的所有正整数解.解 依次解方程 t + 3z = 7，x + 2y = t，得到 ， uZ， vZ.从上式中消去t，得到， u, vZ. (19)要使x 1，y 1，z 1，则应有3u + 2v 0，-v 1，1 - u 0. (20)所以3u -2v 2，u 1 u 1，即 u = 1.由此及式(20)，有3 + 2v 0，-v 1 - v -1，所以v = -1.将u = 1，v

12、= -1代入式(19)，得到原方程的唯一的一组正整数解x = 2，y = 1，z = 1.二、小结三、作业 1. 将写成三个既约分数之和，它们的分母分别是3，5和7.2. 求方程x1 + 2x2 + 3x3 = 41的所有正整数解.3. 求解不定方程组：.4. 甲班有学生7人，乙班有学生11人，现有100支铅笔分给这两个班，要使甲班的学生分到相同数量的铅笔，乙班学生也分到相同数量的铅笔，问应怎样分法？5. 证明：二元一次不定方程ax + by = n，a 0，b 0，(a, b) = 1的非负整数解的个数为+ 1.6. 设a与b是正整数，(a, b) = 1，证明：1, 2, L, ab -

13、a - b中恰有个整数可以表示成ax + by（x 0，y 0）的形式.1. 设，即35x + 21y + 15z = 17，因(35, 21) = 7，(7, 15) = 1，117，故有解.分别解5x + 3y = t，7t + 15z = 17得x = -t + 3u，y = 2t - 5u，uZ，t = 11 + 15v，z = -4 - 7v，vZ， 消去t得x = -11 - 15v + 3u，y = 22 + 30v - 5u，z = -4 - 7v，u，vZ.对于任意的确定的u和v的值，都给出一种表示法.2. 分别解x1 + 2x2 = t，t + 3x3 = 41得x1 =

14、t - 2u，x2 = u，uZ，t = 41 - 3v，x3 = v，vZ，消去t得x1 = 41 - 3v - 2u，x2 = u，x3 = v，u，vZ.由此得原方程的全部正整数解为(x1, x2, x3) = (41 - 3v - 2u, u, v)，u 0，v 0，41 - 3v - 2u 0.3. 消去x1得9x2 - 14x3 = 3，解得x2 = -9 + 14t，x3 = -6 + 9t，tZ，从而得不定方程组的解为x1 = 43 - 55t，x2 = -9 + 14t，x3 = -6 + 9t，tZ，4. 设甲、乙班的学生每人分别得x，y支铅笔，则7x + 11y = 100，解这个不定方程得x = 8，y = 4.5. 二元一次不定方程ax + by = n的一切整数解为，tZ，于是由x 0，y 0得，但区间的长度是，故此区间内的整数个数为+ 1.6. 因为0, 1, 2, L, ab - a - b中共有(a - 1)(b - 1)个数，故只须证明n与g - n（g = ab - a - b）有且只有一个能表示成ax + by（x 0，y 0）的形式.如果n与g - n都能表示成ax + by（x 0，y 0）