初等数论教案.docx

《初等数论教案.docx》由会员分享，可在线阅读，更多相关《初等数论教案.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、厦门大学教案学年度第学期院（系） 数学科学学院任课教师课程名称授课章节：第 4.3 节一次同余方程组和孙子定理授课教材：初等数论，北京大学出版社授课对象：数学类专业一年级本科生【教学要求】1. 了解孙子定理的历史背景和起源出处，理解用孙子定理求解一次同余方程组的思想方法和公式，掌握求解一次同余方程组的计算步骤；2. 掌握一次同余方程组的模两两不互素时，应当如何转化成模两两互素时的等价一次同余方程组，再用孙子定理求解；3. 理解一次同余方程组的意义，并能用孙子定理的方法解决一些实际应用问题。【教学重点】1. 孙子定理的思想方法和计算步骤；2. 如何应用孙子定理解决实际应用问题。【教学难点】理解孙

2、子定理的思想方法。【教学内容】第三节一次同余方程组和孙子定理本节主要讨论一次同余方程组的解法。为了解决这类同余方程组，我们需要弄清楚剩余系的结构。孙子定理(又称中国剩余定理)就是解决这类实际问题的有力工具。一、“物不知其数”问题及其解法1.1 问题的提出例 1：（“物不知其数”问题）大约在公元四世纪，我国南北朝时期有一部著名的算术著作孙子算经，其中就有一个“物不知其数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三”。1.2 问题的解法及理由明朝程大位编著的算法统宗里记载了此题的解法，他是用一首歌谣叙述出来的： 三人同行七十稀，五树梅花廿一枝。七子团

3、圆正月半，除百零五便得知。这首诗翻译成数学算式就是： 70 2 + 21 3 +15 2 = 233 ， 233 -105 2 = 23 。解题步骤及理由如下：（1）先在 5 和 7 的公倍数中找除以 3 余 1 的数，进而找到除 3 余 2 的数。因为5,7 = 35 ，35 3 = 11(余 2)，(35 2) 3 = 23 (余 1)，而(70 2) 3 = 46 (余 2)， 所以140 符合条件。（2） 在 3 和 7 的公倍数中找除以 5 余 1 的数，进而找到除 5 余 3 的数。因为3,7 = 21 ， 21 5 = 4 (余 1)， (21 3) 5 = 12 (余 3)，所

4、以63 就是符合条件的数。（3） 在 3 和 5 的公倍数中找除以 7 余 1 的数，进而找到除 7 余 2 的数。因为3,5 = 15 ，15 7 = 2 (余 1)， (15 2) 7 = 4 (余 2)，所以30 就是符合条件的数。（4） 将上面得到的分别符合上面三个条件的三个数相加： 70 2 + 21 3 +15 2 = 233 。因为70 (或 140)是 5 和 7 的倍数，而 3 除余 1(或余 2)的数。21(或 63)是 3 和 7 的倍数， 而 5 除余 1(或余 3)的数。15(或 30)是 3 和 5 的倍数，而 7 除余 1(或余 2)的数。所以233 是除以 3

5、余 2、除以 5 余 3 和除以 7 余 2 的数。又因为3，5，7 = 105 ， 233 - 2 105 = 23 也是它的解，而且 23 105 ，所以23 是最小解，其所有解为 x = 105k + 23 ( k = 0,1,2, )。1.3 注释“物不知其数”问题及其解答，是我国古代研究一次同余方程组并取得辉煌成果的经典例证。上面的解法中，总是先求出余 1 的数，再求出余几的数，这种解法逐渐被总结成简洁实用的“求一术”。“物不知其数”又名“鬼谷算”，“秦王暗点兵”，“剪管术”，“隔墙算”，“神奇妙算”，“大衍求一术”等等。方法总结如下：定母m1m 2mk衍母mm mm=1 2k衍数M

6、1 = mmMm 12 = mM2k = mmk乘率M1-1M2-1 Mk-1用数M M11-1M M22-1 Mk Mk-1剩数a1a 2ak各总M M -1a111M M -1a 222M M -1akkk所求率M MaM Ma-1-1111222+ +M M-1kkka所求总所求率被衍母除后的最小正剩余1例 1 中，m= 3 ，m= 5 ，m= 7 均为定母，m =105 为衍母，M1= 35 ，M 2= 21，M 3= 152311123为衍数，乘率 M -1 = 2 ，M -1 = 1，M -1 = 1 分别满足“求一术”中的 M M -1 1(mod 3) ，22331221111

7、M M -1 1(mod 5) ， M M -1 1(mod 7) ，用数分别为 M M -1 = 70 ， M M -1 = 21 ，33123M M -1 = 15 ，剩数为a = 2 ，a = 3 ，a= 2 ，各总分别为 M M -1a= 140 ，MM -1a2223 63 ， MM -1a= 30 ，所求率为 M M -1a + MM -1a+ M M-1a= 233 ，所以33111222333+xM M -1aM111M -1a222M M -1a+333= 70 2 + 21 3 + 15 2 23(mod105) 。二、一次同余方程组和孙子定理2.1 一次同余方程组x a1

8、 (mod m1 )22x a (mod m )我们本节要讨论的是形如x ak (mod mk )的一次同余方程组的解法。前面的“物不知其数问题”，其实就是一次同余方程组(1)x 2(mod 3)x 3(mod 5) 。(2)x 2(mod 7)它的解为 x 23(mod105) 。2.2 孙子定理定理 1：设m1 , m2 , , mk 是两两互素的正整数，那么对于任意整数 a1 , a2 , ak ，一次同余x a1 (mod m1 )x a (mod m )方程组22x ak (mod mk )必定有解，其解为x M M -1a + MM -1a+ + MM -1a(mod m) 。这里

9、m = m m m= m M ，111222kkk1 2kjjjjjM M -1 1(mod m ) ，1 j k 。证明：由于m1 , m2 , , mk 两两互素，所以m = m1 , m2 , mk = m1m2 mk 。若一次同余方程组有解c1 , c2 ，则c1 c2 (mod m) 。因为m1 , m2 , , mk 两两互素， c1 c2 (mod m j ) ，1 j k ，这就证明了同余方程若有解，则其解数为 1。下面证明111x M M -1a + M-1Ma222+ + M-1Makkk(mod m) 确实是同余方程的解。显然jjjjjj(m , M ) = 1 ，根据扩

10、展的欧几里德算法，满足 M M -1 1(mod m ) 的 M -1 必存在。由jjijjjjjjjM M -1 1(mod m ) 及m | M ( j i) 就推出c M M -1a a (mod m ) ，即c 是解。j注释：(1)从孙子定理的算法思想来看，整个计算的难点集中在求 M -1 上， 需要扩展的欧几里德算法来实现，当然在实际解题中我们通常采用拼凑法。(2)孙子定理要求一次同余方程组的模m1 , m2 , , mk 两两互素，如果出现了某两个模不互素的情形，则应该将其转化为模互素的情形下的等价的一次同余方程组。x 7(mod9)例如：一次同余方程组x 1(mod15)就是模

11、9 和 15 不互素的一次同余方程组。我们将 9x 7(mod 9)和 15 完全素因子分解为9 = 32 ，15 = 3 5 ，则原方程组等价于x 1(mod 3) ，显然x 1(mod 5)x 7(mod9) 是x 1(mod3) 的特殊情形，不是矛盾方程(否则无解)，故原方程组等价于x 7(mod9)x 1(mod5)，再应用孙子定理求解。三、孙子定理的应用孙子定理是数论中最重要的基本定理之一，它实质上刻画了剩余系的结构。它的应用是非常广泛的，在数学计算、保密通讯、测距和日常生活中都通常会用到。例 2. 求相邻的四个整数，它们依次可被22 ， 32 ， 52 及72 整除。x 1(mod

12、 22 )x 0(mod 32 )x -1(mod 52 )解：设这四个相邻整数是 x -1， x ， x +1， x + 2 ，按要求应满足。234x -2(mod 72 )所以，这是一个解同余方程组问题， m1= 22 ， m= 32 ， m= 52 ， m= 72 两两互素，满1足孙子定理的条件。这里a= 1，a2= 0 ，a= -1 ，a4= -2 。M1= 325272 ，M= 225272 ，3342M = 223272 ， M = 223252 。11111由 M 1(mod 22 ) 知，1 M M -1 M -1 (mod 22 ) ，因此可取 M -1 = 1 。22222

13、同理，由 M 4(mod 32 ) 知，1 M M -1 4M -1 (mod 32 ) ，因此可取 M -1 = -2 。33333由 M -11(mod 52 ) 知，1 M M -1 -11M -1 (mod 52 ) ， 2 3M -1 (mod 52 ) ，3316 -M -1 (mod 52 ) ，因此可取 M -1 = 9 。44444由 M 18(mod 72 ) 知1 M M -1 18M -1 (mod 72 ) ， 3 5M -1 (mod 72 ) ，4430 M -1 (mod 72 ) ，因此可取 M -1 = -19 。我们将计算数据列表如下：m21=2m2= 3

14、2m23=5m4= 72m = m m m m1 2 3 4= 22 32 52 72 = 44100M1= 325272M2=2 5 72 2 2M3=2 3 72 2 2M4=2 3 52 2 2M-11=1M-12= -2M-13=9M-14= -19M M-111=11025M M-122= -9800M M-133=15876M M-144= -17100a = 11a2= 0a = -13a = -24M Ma-1111=11025M M -1a222= 0M M -1a333= -15876M M -1a444= 34200M MaM MaM MaM Ma-1+-1+-1+-11

15、11222333444= 29349所求率被衍母除后的最小正剩余为 29349由孙子定理得 x 32 52 72 11+ 22 52 72 (-2) 0 + 22 32 72 9 (-1) +22 32 52 (-19) (-2)(mod 22 32 52 72 ) ，即x 11025 -15876 + 34200 29349(mod 44100) 。所以满足要求的四个相邻整数有无穷多组，它们是： 29348 + 44100 t ， 29349 + 44100 t ，29350 + 44100 t ， 29351 + 44100 t ， t = 0, 1, 2, 。最小的这样四个相邻正整数是：

16、29348，29349，29350，29351。下面这个问题是陈景润初等数论 I中的趣味数学题，可以应用孙子定理求解。例 3. 甲、乙两港的距离不超过 5000 公里，今有三只轮船于某天零时同时从甲港开往乙港。假定三只轮船每天 24 小时都是匀速航行，若干天后的零时第一只轮船首先到达，几天后的18 时第二只轮船也到达，再过几天后的 8 时第三只轮船也到达了。假若每天第一只轮船走300 公里，第二只轮船走 240 公里，第三只轮船走 180 公里，问甲、乙两港实际距离是多少公里，三只轮船各走了多长时间？解：设甲、乙两港距离 x 公里。第二只轮船 18 小时走的距离是240 18 = 180 公里

17、，第三24x 0(mod 300)只轮船 8 小时走的距离是180 824= 60 公里。按照题意有x 180(mod 240) 。x 60(mod180)因为(300,240) = 60 ， (300,180) = 60 ， (240,180) = 60 ，所以该一次同余方程组不能直接用孙子定理求解。由于300 = 22 3 52 ，240 = 24 3 5 ，180 = 22 32 5 ，所以原x 4(mod 24 )一次同余方程组与x 6(mod 32 ) 有相同的解。此处m= 24 ， m= 32 ， m= 52 ，x 0(mod 52 )1231a = 4 ，a2= 6 ，a= 0

18、。M1= 32 52 = 225 ，M= 24 52 = 400 ，M= 24 32 = 144 ，323m = 24 32 52 = 3600 。111由于225M -1 1(mod 24 ) ，即 M -1 1(mod 24 ) ，所以取 M -1 = 1 。2222由400M -1 1(mod 32 ) ，4M -1 1(mod 32 ) ，得 M -1 -2(mod 32 ) ，所以取 M -1 = -2 。由144M 3-1 1(mod 52 ) ，19M 3-1 1(mod 52 ) ，得 M 3-1 4(mod 52 ) ，所以取 M 3-1 = 4 。将计算数据列表如下：m1=

19、 24m2= 32m3= 52mm m m= 2 3 5 = 36004221 2 3M1= 3252 = 225M2= 2452 = 400M3= 2432 = 144M-11= 1M-12= -2M-13= 4M M-1-1-111= 225M M22= -800M M33= 576a = 41a2= 6a = 03M Ma-1111= 900M M -1a222= -4800M M -1a333= 0M MaM MaM Ma-1111222333+-1+-1= -3900所求率被衍母除后的最小正剩余为 3300由孙子定理，得 x 225 1 4 + 400 (-2) 6 +144 4 0 -3900 3300(mod3600) 。由于甲、乙两港距离不超过 5000 公里，所以实际距离为 3300 公里。又3300 = 11， 3300 = 13 3 ， 3300 = 18 1 。30024041803答：甲、乙两港相距 3300 公里。第一只轮船走 11 天，第二只轮船走 13 天 18 小时，第三只轮船走 18 天 8 小时。课后作业：1、作业：P174-P1751.(i)(vi)3.4.2、预习一般同余方程的求解