初等数论教案

1、厦门大学教案学年度第院（系）数学科学学任课教师课程名称授课章节：第4.3节授课教材初等数论，北京大学出版社授课对象：数学类专业一年级本科生【教学要求】和公式，掌握求解一次同余方程组的计算步骤；方程组，再用孙子定理求解；理解一次同余方程组的意义，并能用孙子定理的方法解决一些实际应用问题。【教学重点】孙子定理的思想方法和计算步骤；如何应用孙子定理解决实际应用问题。【教学难点】理解孙子定理的思想方法。【教学内容】第三节一次同余方程组和孙子定理(又称中国剩余定理就是解决这类实际问题的有力工具。一、“物不知其数”问题及其解法问题的提出例 1：（“物不知其数”问题）二，问物几何？答曰：二十三”。问题的解法

2、及理由三人同行七十稀，五树梅花廿一枝。七子团圆正月半，除百零五便得知。22131522。解题步骤及理由如下：（1）先在 5 和 7 的公倍数中找除以 3 余 1 的数，进而找到除 3 余 2 的数。因为5,7311(3(，而(703(2)， 所以140符合条件。375153的数。因为3,754(1)(21512(3)，所以63 就是符合条件的数。357172的数。因为3,5，1572(1)74(2)，所以30就是符合条件的数。2213152。因为(140)5731(2)21(63)37的倍数， 51(3)15(3571(2)的数。所以233 是除以 3 余 2、除以 5 余 3 和除以 7 余

3、 2 的数。又因为75，325335，所以23 x 105k k )。注释1 的数，再求出余几的数，这种解法逐渐被总结成简定母定母m1m2mk衍母mmmm1 2k衍数M1 mmMm12 mM2k mmk乘率M11M21Mk1用数M M111M M221Mk Mk1剩数a1a2ak各总M M 1a111M M 1a222M M 1akkk所求率M MaM Ma11111222 M M1kkka所求总所求率被衍母除后的最小正剩余111357m5M 35 1523113M 1 2 1 1，M 1 1M M 12311322331211M M 1 5M M 1 7，用数分别为 M M 1 223312

4、113312M M 1 15a 23312 2 M M 1a 140M 1a2223，3M 1a 30 M M 1a M 1aM 1a 233 ，所以33111222333xM M 1a33111222333111M 1a22M M 1a33 70 2 21 3 15 2 23(mod105) 。二、一次同余方程组和孙子定理一次同余方程组x)2x 2我们本节要讨论的是形如xk dk )的一次同余方程组的解法。前面的“物不知其数问题”，其实就是一次同余方程组(1)x 2(mod 3)x5)。x 2(mod 7)它的解为 x 23(mod105) 。孙子定理1：设m2 mk a2 ,ak ，一次同

5、余x)x a m)方程组22xk dk )必定有解，其解为x M M 1a MM 1aM 1a(modm。这里mm m m M ，11222kkk1 2kjjjjM M 1 1(mod m ) ，1 j jj由于m2 mk 两两互素，所以m m2 ,mk mk 程组有解c2 ，则 c2 (mod m。因为m2 mk c2 (mod m j ，1 j k ，这就证明了同余方程若有解，则其解数为 1。下面证明11x M M 1111M22M 1MkkM(mod m) 确实是同余方程的解。显然jjjjj(m M 1M M 1 jjjjjjjjjjjjM M 1 m 及m |M j i就推出cMjjj

6、jjjjj注释：(1)从孙子定理的算法思想来看，整个计算的难点集中在求 M 1 上， 需要扩展的欧几里德算法来实现，当然在实际解题中我们通常采用拼凑法。j(2)孙子定理要求一次同余方程组的模m2 mk 两两互素，如果出现了某两个模不互素的情形，则应该将其转化为模互素的情形下的等价的一次同余方程组。x7(mod9)x 就是模 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) 的特殊情形，不是矛盾方程(否则无解)，故原方程

7、组等价于x 7(mod9)x，再应用孙子定理求解。三、孙子定理的应用非常广泛的，在数学计算、保密通讯、测距和日常生活中都通常会用到。例 2. 求相邻的四个整数，它们依次可被22 ， 32 ， 52 及72 整除。x22)x0(mod32)x52解：设这四个相邻整数是x1，x，x1x52234x 2(mod 72 )234 22 ， 32 ， 52 ， 72 两两互素，满11 0 12M1 325272 ，M 225272 ，332M 223272 ， M 223253321111由 M 1(mod 22 ) 知，1 M M 1 M 1 (mod 22 ) 11112222同理，由 M 4(mo

8、d 32 ) 知，1 M M 1 4M 1 (mod 32 ) ，因此可取 22223333由 M 11(mod 52 ) 知，1 M M 1 11M 1 (mod 52 ) ， 2 3333316 M 1 (mod 52 ) ，因此可取 M 1 34444由 M 18(mod 72 ) 知1 M M 1 18M 1 (mod 72 ) ， 3 4444430 M 1 (mod 72 ) ，因此可取 M 1 4mm212m2 32m235m4 72mmmmm1 2 3 422 32 52 72 44100M1 325272M22 5 72 2 2M32 3 72 2 2M42 3 52 2 2

9、M111M12 2M139M14 19M M11111025M M122 9800M M13315876M M14417100a 11a2 0a 13a 24M Ma111111025M M 1a222 0M M 1a33315876M M 1a444 34200M MaM MaM MaM Ma11111112223334442934929349x32 52 72 1122 52 72 (2022 32 72 9) 22 32 52 (19(2)(mod22325272，即x15876。tt， t t t 。最小的这样四个相邻正整数是：29348，29349，29350，29351。下面这个问

10、题是陈景润初等数论 I中的趣味数学题，可以应用孙子定理求解。3. 5000 24 8 时第三只轮船也到达了。假若每天第一只轮船走300 240 180 少公里，三只轮船各走了多长时间？x 18 小时走的距离是 18 24x 0(mod 300)8 小时走的距离是180 82460公里。按照题意有x 180(mod 240) 。x 60(mod180)因为(300,2406060，所以该一次同余方程组不能22352，240243522325x 4(mod 24 )一次同余方程组与x6(mod32有相同的解。此处 24 ，32， 52 ，x0(mod521231a 4 1 60M1 32 52 2

11、25 ，M 24 52 400 ，M 24 32 144 ，323m 24 32 52 3600 。32311由于225M 1 1(mod 24 ) ，即 M 1 1(mod 24 ) ，所以取 M 1 11222由400M 1 32 1 32M 1 2(mod32M 1 2。由144M31 52，19M31 52M31 4(mod52M31222将计算数据列表如下：mm1 24m2 32m3 52mmm m 2 3 5 36004221 2 3M1 3252 225M2 2452 400M3 2432 144M111M12 2M13 4M M11111 225M M22 800M M33 576a 41a2 6a 03M Ma1111 900M M 1a222 4800M M 1a333 0M MaM MaM Ma111122233