初等数论教案

《初等数论教案》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

厦门大学教案学年度第学期院（系）数学科学学院任课教师课程名称授课章节：第4.3节一次同余方程组和孙子定理授课教材：《初等数论》，北京大学出版社授课对象：数学类专业一年级本科生【教学要求】1.了解孙子定理的历史背景和起源出处，理解用孙子定理求解一次同余方程组的思想方法和公式，掌握求解一次同余方程组的计算步骤；2.掌握一次同余方程组的模两两不互素时，应当如何转化成模两两互素时的等价一次同余方程组，再用孙子定理求解；3.理解一次同余方程组的意义，并能用孙子定理的方法解决一些实际应用问题。【教学重点】1.孙子定理的思想方法和计算步骤；2.如何应用孙子定理解决实际应用问题。【教学难点】理解孙子定理的思想方法。【教学内容】第三节一次同余方程组和孙子定理本节主要讨论一次同余方程组的解法。为了解决这类同余方程组，我们需要弄清楚剩余系的结构。孙子定理(又称中国剩余定理)就是解决这类实际问题的有力工具。一、“物不知其数”问题及其解法1.1问题的提出

1例1：（“物不知其数”问题）大约在公元四世纪，我国南北朝时期有一部著名的算术著作《孙子算经》，其中就有一个“物不知其数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三”。1.1问题的解法及理由明朝程大位编著的《算法统宗》里记载了此题的解法，他是用一首歌谣叙述出来的：三人同行七十稀，五树梅花廿一枝。七子团圆正月半，除百零五便得知。这首诗翻译成数学算式就是：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)，所以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余2、除以5余3和除以7余2的数。又因为[3，5，7]=105，233-2´105=23也是它的解，而且23<105，所以23是最小解，其所有解为x=105k+23(k=0,1,2,×××)。

21.1注释“物不知其数”问题及其解答，是我国古代研究一次同余方程组并取得辉煌成果的经典例证。上面的解法中，总是先求出余1的数，再求出余几的数，这种解法逐渐被总结成简洁实用的“求一术”。“物不知其数”又名“鬼谷算”，“秦王暗点兵”，“剪管术”，“隔墙算”，“神奇妙算”，“大衍求一术”等等。方法总结如下：定母m1m···2mk衍母mmmm=12k×××衍数M1=mmMm···12=mM2k=mmk乘率M1-1M2-1···Mk-1用数MM11-1MM22-1···MkMk-1剩数a1a···2ak各总MM-1a111MM-1a···222MM-1akkk所求率MMaMMa-1-1111222++×××+MM-1kkka所求总所求率被衍母除后的最小正剩余1例1中，m=3，m=5，m=7均为定母，m=105为衍母，M1=35，M2=21，M3=152311123为衍数，乘率M-1=2，M-1=1，M-1=1分别满足“求一术”中的MM-1º1(mod3)，22331221111MM-1º1(mod5)，MM-1º1(mod7)，用数分别为MM-1=70，MM-1=21，33123MM-1=15，剩数为a=2，a=3，a=2，各总分别为MM-1a=140，MM-1a2223º63，MM-1a=30，所求率为MM-1a+MM-1a+MM-1a=233，所以33111222333º+xMM-1aM111M-1a222MM-1a+333=70´2+21´3+15´2º23(mod105)。

3二、一次同余方程组和孙子定理2.1一次同余方程组ìxºa1(modm1)í××××××××××××ï22ïxºa(modm)我们本节要讨论的是形如ïïîxºak(modmk)的一次同余方程组的解法。前面的“物不知其数问题”，其实就是一次同余方程组(1)ìxº2(mod3)íïxº3(mod5)。(2)îïxº2(mod7)它的解为xº23(mod105)。2.2孙子定理定理1：设m1,m2,×××,mk是两两互素的正整数，那么对于任意整数a1,a2,×××,ak，一次同余ìxºa1(modm1)ïxºa(modm)方程组ï22ïí××××××××××××ïîxºak(modmk)必定有解，其解为xºMM-1a+MM-1a+×××+MM-1a(modm)。这里m=mm×××m=mM，111222kkk12kjjjjjMM-1º1(modm)，1£j£k。证明：由于m1,m2,×××,mk两两互素，所以m=[m1,m2,×××,mk]=m1m2×××mk。若一次同余方程组有解c1,c2，则c1ºc2(modm)。因为m1,m2,×××,mk两两互素，c1ºc2(modmj)，1£j£k，这就证明了同余方程若有解，则其解数为1。下面证明111xºMM-1a+M-1Ma222+×××+M-1Makkk(modm)确实是同余方程的解。显然

4jjjjjj(m,M)=1，根据扩展的欧几里德算法，满足MM-1º1(modm)的M-1必存在。由jjijjjjjjjMM-1º1(modm)及m|M(j¹i)就推出cºMM-1aºa(modm)，即c是解。j注释：(1)从孙子定理的算法思想来看，整个计算的难点集中在求M-1上，需要扩展的欧几里德算法来实现，当然在实际解题中我们通常采用拼凑法。(2)孙子定理要求一次同余方程组的模m1,m2,×××,mk两两互素，如果出现了某两个模不互素的情形，则应该将其转化为模互素的情形下的等价的一次同余方程组。ìxº7(mod9)î例如：一次同余方程组íxº1(mod15)就是模9和15不互素的一次同余方程组。我们将9ìxº7(mod9)í和15完全素因子分解为9=32，15=3´5，则原方程组等价于ïxº1(mod3)，显然îïxº1(mod5)xº7(mod9)是xº1(mod3)的特殊情形，不是矛盾方程(否则无解)，故原方程组等价于ìxº7(mod9)îíxº1(mod5)，再应用孙子定理求解。三、孙子定理的应用孙子定理是数论中最重要的基本定理之一，它实质上刻画了剩余系的结构。它的应用是非常广泛的，在数学计算、保密通讯、测距和日常生活中都通常会用到。例2.求相邻的四个整数，它们依次可被22，32，52及72整除。ìxº1(mod22)ïïxº0(mod32)íxº-1(mod52)解：设这四个相邻整数是x-1，x，x+1，x+2，按要求应满足。ïî234ïxº-2(mod72)所以，这是一个解同余方程组问题，m1=22，m=32，m=52，m=72两两互素，满

51足孙子定理的条件。这里a=1，a2=0，a=-1，a4=-2。M1=325272，M=225272，3342M=223272，M=223252。11111由Mº1(mod22)知，1ºMM-1ºM-1(mod22)，因此可取M-1=1。22222同理，由Mº4(mod32)知，1ºMM-1º4M-1(mod32)，因此可取M-1=-2。33333由Mº-11(mod52)知，1ºMM-1º-11M-1(mod52)，2º3M-1(mod52)，3316º-M-1(mod52)，因此可取M-1=9。44444由Mº18(mod72)知1ºMM-1º18M-1(mod72)，3º5M-1(mod72)，4430ºM-1(mod72)，因此可取M-1=-19。我们将计算数据列表如下：m21=2m2=32m23=5m4=72m=mmmm1234=22×32×52×72=44100M1=325272M2=257222M3=237222M4=235222M-11=1M-12=-2M-13=9M-14=-19MM-111=11025MM-122=-9800MM-133=15876MM-144=-17100a=11a2=0a=-13a=-24MMa-1111=11025MM-1a222=0MM-1a333=-15876MM-1a444=34200MMaMMaMMaMMa-1+-1+-1+-1111222333444=29349所求率被衍母除后的最小正剩余为29349由孙子定理得xº32×52×72×1×1+22×52×72×(-2)×0+22×32×72×9×(-1)+22×32×52×(-19)×(-2)(mod22×32×52×72)，即xº11025-15876+34200º29349(mod44100)。

6所以满足要求的四个相邻整数有无穷多组，它们是：29348+44100t，29349+44100t，29350+44100t，29351+44100t，t=0,±1,±2,×××。最小的这样四个相邻正整数是：29348，29349，29350，29351。下面这个问题是陈景润《初等数论I》中的趣味数学题，可以应用孙子定理求解。例3.甲、乙两港的距离不超过5000公里，今有三只轮船于某天零时同时从甲港开往乙港。假定三只轮船每天24小时都是匀速航行，若干天后的零时第一只轮船首先到达，几天后的18时第二只轮船也到达，再过几天后的8时第三只轮船也到达了。假若每天第一只轮船走300公里，第二只轮船走240公里，第三只轮船走180公里，问甲、乙两港实际距离是多少公里，三只轮船各走了多长时间？解：设甲、乙两港距离x公里。第二只轮船18小时走的距离是240´18=180公里，第三24íìxº0(mod300)只轮船8小时走的距离是180´824=60公里。按照题意有ïxº180(mod240)。îï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(mod24)一次同余方程组与ïxº6(mod32)有相同的解。此处m=24，m=32，m=52，íîïxº0(mod52)1231a=4，a2=6，a=0。M1=32´52=225，M=24´52=400，M=24´32=144，323m=24´32´52=3600。111由于225M-1º1(mod24)，即M-1º1(mod24)，所以取M-1=1。2222由400M-1º1(mod32)，4M-1º1(mod32)，得M-1º-2(mod32)，所以取M-1=-2。由144M3-1º1(mod52)，19M3-1º1(mod52)，得M3-1º4(mod52)，所以取M3-1=4。

7将计算数据列表如下：m1=24m2=32m3=52mmmm==2×3×5=3600422123M1=3252=225M2=2452=400M3=2432=144M-11=1M-12=-2M-13=4MM-1-1-111=225MM22=-800MM33=576a=41a2=6a=03MMa-1111=900MM-1a222=-4800MM-1a333=0MMaMMaMMa-1111222333+-1+-1=-3900所求率被衍母除后的最小正剩余为3300由孙子定理，得xº225´1´4+400´(-2)´6+144´4´0º-3900º3300(mod3600)。由于甲、乙两港距离不超过5000公里，所以实际距离为3300公里。又3300=11，3300=133，3300=181。30024041803答：甲、乙两港相距3300公里。第一只轮船走11天，第二只轮船走13天18小时，第三只轮船走18天8小时。课后作业：1、作业：P174-P1751.(i)(vi)3.4.2、预习一般同余方程的求解