初等数论教案.doc

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

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

2、理的思想方法和计算步骤；2.如何应用孙子定理解决实际应用问题。【教学难点】理解孙子定理的思想方法。【教学内容】第三节一次同余方程组和孙子定理本节主要讨论一次同余方程组的解法。为了解决这类同余方程组，我们需要弄清楚剩余系的结构。孙子定理(又称中国剩余定理)就是解决这类实际问题的有力工具。一、“物不知其数”问题及其解法1.1问题的提出例1：（“物不知其数”问题）大约在公元四世纪，我国南北朝时期有一部著名的算术著作《孙子算经》，其中就有一个“物不知其数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问

3、物几何？答曰：二十三”。1.2问题的解法及理由明朝程大位编著的《算法统宗》里记载了此题的解法，他是用一首歌谣叙述出来的：三人同行七十稀，五树梅花廿一枝。七子团圆正月半，除百零五便得知。这首诗翻译成数学算式就是：，。解题步骤及理由如下：（1）先在5和7的公倍数中找除以3余1的数，进而找到除3余2的数。因为，(余2)，(余1)，而(余2)，所以符合条件。（2）在3和7的公倍数中找除以5余1的数，进而找到除5余3的数。因为，(余1)，(余3)，所以就是符合条件的数。（3）在3和5的公倍数中找除以7余1的数，进而找到除7余2

4、的数。因为，(余1)，(余2)，所以就是符合条件的数。（4）将上面得到的分别符合上面三个条件的三个数相加：。因为(或140)是5和7的倍数，而3除余1(或余2)的数。21(或63)是3和7的倍数，而5除余1(或余3)的数。15(或30)是3和5的倍数，而7除余1(或余2)的数。所以是除以3余2、除以5余3和除以7余2的数。又因为，也是它的解，而且，所以是最小解，其所有解为()。1.3注释“物不知其数”问题及其解答，是我国古代研究一次同余方程组并取得辉煌成果的经典例证。上面的解法中，总是先求出余1的数，再求出余几的数，

5、这种解法逐渐被总结成简洁实用的“求一术”。“物不知其数”又名“鬼谷算”，“秦王暗点兵”，“剪管术”，“隔墙算”，“神奇妙算”，“大衍求一术”等等。方法总结如下：定母衍母衍数乘率用数剩数各总所求率所求总所求率被衍母除后的最小正剩余例1中，，，均为定母，为衍母，，，为衍数，乘率，，分别满足“求一术”中的，，，用数分别为，，，剩数为，，，各总分别为，，，所求率为，所以。二、一次同余方程组和孙子定理2.1一次同余方程组我们本节要讨论的是形如(1)的一次同余方程组的解法。前面的“物不知其数问题”，其实就是一次同余方程组。(2)

6、它的解为。2.2孙子定理定理1：设是两两互素的正整数，那么对于任意整数，一次同余方程组必定有解，其解为。这里，，。证明：由于两两互素，所以。若一次同余方程组有解，则。因为两两互素，，，这就证明了同余方程若有解，则其解数为1。下面证明确实是同余方程的解。显然，根据扩展的欧几里德算法，满足的必存在。由及就推出，即是解。注释：(1)从孙子定理的算法思想来看，整个计算的难点集中在求上，需要扩展的欧几里德算法来实现，当然在实际解题中我们通常采用拼凑法。(2)孙子定理要求一次同余方程组的模两两互素，如果出现了某两个模不互素的情形

7、，则应该将其转化为模互素的情形下的等价的一次同余方程组。例如：一次同余方程组就是模9和15不互素的一次同余方程组。我们将9和15完全素因子分解为，，则原方程组等价于，显然是的特殊情形，不是矛盾方程(否则无解)，故原方程组等价于，再应用孙子定理求解。三、孙子定理的应用孙子定理是数论中最重要的基本定理之一，它实质上刻画了剩余系的结构。它的应用是非常广泛的，在数学计算、保密通讯、测距和日常生活中都通常会用到。例2.求相邻的四个整数，它们依次可被，，及整除。解：设这四个相邻整数是，，，，按要求应满足。所以，这是一个解同余方程

8、组问题，，，，两两互素，满足孙子定理的条件。这里，，，。，，，。由知，，因此可取。同理，由知，，因此可取。由知，，，，因此可取。由知，，，因此可取。我们将计算数据列表如下：所求率被衍母除后的最小正剩余为29349由孙子定理得，即。所以满足要求的四个相邻整数有无穷多组，它们是：，，，，。最小的这样四个相邻正整数是：29348，29349，2935