《初等数论教案》word版.doc

第六节 孙子定理及其应用举例教学目的：1、熟练掌握孙子定理内容及证明；2、会用孙子定理求解一次同余方程式组.教学重点：用孙子定理求解一次同余方程式组.教学课时：4课时教学过程在我国古代孙子算经中有：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问：物有几何？对于“物不知其数”问题，程大位在直指算法统宗(算法统宗1593年)一书中给出了如下的求解歌诀： 三人同行七十稀， 五树梅花卄一枝， 七子团圆正半月， 除百零五便得知.如果我们设所求的物为个，则“物不知其数”等价于求解下面的同余式组 .将上面的同余式组推广，我们可得 (1)本节主要讨论同余方程组(1)的解问题.定理1(孙子定理) 设m1, m2, L, mk是正整数，(mi, mj) = 1，1 i, j k，i j. (2)记m = m1m2Lmk ，Mi =，1 i k，则存在整数Mi（1 i k），使得MiMi 1 (mod mi)， (3)MiMi 0 (mod mj)，1 j k，i j， (4)并且(mod m) (5)是同余方程组(1)对模m的唯一解，即若有任意的x使方程组(1)成立，则x x0 (mod m). (6)继孙子算经之后，南宋大数学家秦九韶则进一步开创了对一次同余式理论的研究工作，推广“物不知数”的问题. 德国数学家高斯K.F. Gauss.公元1777-1855年于公元1801年出版的算术探究中明确地写出了上述定理. 公元1852年，英国基督教士伟烈亚士Alexander Wylie公元1815-1887年将孙子算经“物不知数”问题的解法传到欧洲，公元1874年马蒂生L.Mathiesen指出孙子的解法符合高斯的定理，从而在西方的数学史里将这一个定理也称为“中国的剩余定理”Chinese remainder theorem.证明 由式(2)，有(Mi, mi) = 1，因此利用辗转相除法可以求出Mi与yi ，使得MiMi + yimi = 1，即Mi满足式(3)和式(4). 由式(3)与式(4)，对于1 i k，有x0 aiMiMi ai (mod mi)，1 i k.若x也使式(1)成立，则x x0 (mod mi)，1 i k，因此x x0 (mod m1, m2, L, mk).但是，由式(2)可知m1, m2, L, mk = m，这就证明了式(6).证毕.定理2 在定理1的条件下，若式(1)中的a1, a2, L, ak分别通过模m1, m2, L, mk的完全剩余系，则式(5)中的x0通过模m1m2Lmk的完全剩余系.证明 略.定理3 同余方程组(1)有解的充要条件是ai aj (mod (mi, mj)，1 i, j n. (7)证明 必要性是显然的.下面证明充分性.当n = 2时，由前一节例8可知充分性成立.假设充分性当n = k时成立.假设式(7)当n = k + 1时成立.我们来考虑同余方程组x ai (mod mi)，1 i k + 1.由前一节例8，存在bk，使得x bk (mod mk，mk +1)满足同余方程组x ak (mod mk)，x ak + 1 (mod mk + 1).在同余方程组中，由式(7)有ai aj (mod (mi, mj)，1 i, j k - 1，因此，若能证明ai bk (mod (mi, mk, mk +1)，1 i k - 1. (8)则由归纳假设就可以证明充分性.由bk的定义，有ak bk (mod mk)，ak + 1 bk (mod mk + 1) (9)而且，由于假设式(7)当n = k + 1时成立，所以，对于1 i k - 1有ai ak (mod (mi, mk)，ai ak + 1 (mod (mi, mk + 1)，由此及式(9)得到，对于1 i k - 1，有ai bk (mod (mi, mk)，ai bk (mod (mi, mk + 1).因此ai bk (mod (mi, mk), (mi, mk + 1).由上式及第一章的例题，就得到式(8). 证毕.定理4 设m = m1m2Lmk ，其中m1, m2, L, mk 是两两互素的正整数，f(x)是整系数多项式，以T与Ti（1 i k）分别表示同余方程f(x) 0 (mod m) (10)与f(x) 0 (mod mi) (11)的解的个数，则T = T1T2Tk .证明 因为同余方程(10)等价于同余方程组f(x) 0 (mod mi)，1 i k. (12)对于每i（1 i k），设同余方程(11)的全部解是(mod mi)， (13)则同余方程组(12)等价于下面的T1T2Tk个方程组：， (14)其中通过式(13)中的数值，即通过同余方程(11)的全部解.由孙子定理，对于选定的每一组，同余方程组(14)对模m有唯一解，而且，由定理2，当每个通过(13)式中的值时，所得到的T1T2Tk个同余方程组(14)的解对于模m都是两两不同余的.证毕.由定理4及算术基本定理，我们知道，解一般模的同余方程可以转化为解模为素数幂的同余方程.例1 求整数n，它被3，5，7除的余数分别是1，2，3.解 n是同余方程组n 1 (mod 3)，n 2 (mod 5)，n 3 (mod 7)的解.在孙子定理中，取m1 = 3，m2 = 5，m3 = 7，m = 357 = 105，M1 = 35，M2 = 21，M3 = 15，M1 = -1，M2 = 1，M3 = 1，则n 135(-1) + 2211 + 3151 52 (mod 105)，因此所求的整数n = 52 + 105t，tZ. 例2 解同余式组 .练习：解同余式组 .例3 解同余式组 .练习：判别同余式组 是否有解？若有解，求出其解.例4 解同余式. 例5 解同余式组 .例6 解同余方程5x2 + 6x + 49 0 (mod 60). (15)解 因为60 = 345，所以，同余方程(15)等价于同余方程组5x2 + 6x + 49 0 (mod 3) (16)5x2 + 6x + 49 0 (mod 4) (17)5x2 + 6x + 49 0 (mod 5). (18)分别解同余方程(16)，(17)，(18)得到解x1(1) 1，x2(1) -1 (mod 3)，x1(2) 1，x2(2) -1 (mod 4)，x1(3) 1 (mod 5)，这样，同余方程(15)的解x可由下面的方程组决定：x a1 (mod 3)，x a2 (mod 4)，x a3 (mod 5)，其中a1 = 1或 -1，a2 = 1或 -1，a3 = 1.利用孙子定理，取m1 = 3，m2 = 4，m3 = 5，m = 60，M1 = 20，M2 = 15，M3 = 12，M1 = 2，M2 = -1，M3 = 3，则x 40a1 - 15a2 + 36a3 (mod 60).将a1，a2，a3所有可能的取值代入上式，得到方程(15)的全部解是x