《孙子定理及其应用》由会员分享，可在线阅读，更多相关《孙子定理及其应用（8页珍藏版）》请在金锄头文库上搜索。
1、 学院学学 术术 论论 文文姓 名 所在学院 专业班级 学 号 指导教师 日 期 【摘摘 要要】 本文主要讲解孙子定理及在解非线性同余式中的应用。【关键词关键词】 孙子定理 同余方程组 剩余类 标准分解式Abstract:Abstract: this paper mainly explain grandson theorem and in solving nonlinear congruence type application.Keywords:Keywords: grandson theorem of congruence decomposition of the standard typ
2、e of surplus equations11 引言引言实际上，孙子定理由闵嗣鹤,严士健在文1中详细描述并证明了；王芳珍， 王宪清的“孙子定理的一种推广形式”3进一步阐述了其相关应用；杨迎球在 “中国剩余定理” 4 中提出了同余式组的一种较为简捷易懂的解法， , 其目的都是为了更好地将孙子定理推广及应用，下面我们来看定理定理 1 1 （孙子定理）（孙子定理）1 设， , 是 k 个两两互质的正整数， 1m2mkmm=，=，i=1，2，k，则同余式组（1）的解是12m mkmmiim M1122(mod)(mod). (mod)kkxbmxbmxbm ， （2） 11 1222xM M bM
3、M b(mod)kkkM M bm其中1，i=1，2，k iiM M (mod)im证证 由，即得，故知对每一，有一存在，使得(,)1ijm mij(,)1iiM miM iM.另一方面，因此，故1(mod)iiiM Mmiimm Mjim Mij即为（1）的解 .若，是适合（1）式的任意1(mod)kjjjiiiii jM M bM M bbm1x2x两个整数，则， =1，2，k，因，于是，12(mod)ixxmi(,)1ijm m12(mod)xxm故（1）的解只有（2）. 证完证完由上述我们知道，孙子定理的重要条件是模， , 两两互质，那如果两两不1m2mkm互质，我们怎么解决呢？ 22
4、 主要结论主要结论当， , 两两不互质时，我们有1m2mkm定理定理 2 22 设设， ,为正整数，其标准分解式分别为：1m2mnm，。取1112 112aampp1ta tp2122 212aampp2ta tp12 12nnaa nmppnta tp，i=1，2，t。12,Mm m,nm12 12kkp pik tp0ik 其中, ，, 。11121max,kaa1na12max,ittkaanta当同余式组 （1） 有解，则其解与同余式组 （2） 1122(mod)(mod). (mod)nnxcmxcmxcm 的解完全相同。121122(mod)(mod).(mod)ikkk ntxc
5、pxcpxcp 证证 因一定能整除某一个，不妨设12,Mm m,nm12 12kkp pik tp1 1kpim1 1kp，同理可假设，又因同余式组（1）有解，其解一定是以，1m2 22kpmik tipm1m， ,的最小公倍数为剩余类解，即。所以是满足同余式组2mnm0(mod)xxM0x（1）的一个整数。因而有， =1，2，n。0(mod)iixcmi因， =1,2，t(tn)。所以有ik tip c mi120110220(mod)(mod).(mod)ikkk ntxcpxcpxcp 即满足同余式组（2） ，又因，是两两互质的。又孙子定理知：同余式0x12 12,kkppik tp组（
6、2）的全部解为： ，由于=12 012(modkkxxp p)ik tp12,Mm m,nm12 12kkp p，ik tp所以同余式组（1）与同余式组（2）有完全相同的解。 证完证完例例1 1 今有数不知总，以五累减之无剩，以七百一十五累减之剩十，以二百四十七累减 之 剩一百四十，以三百九十一累减之剩二百四十五，以一百八十七累减之剩一百零九，问总 数若干?(黄宗宪：隶一术通解)。解解 依题意得： （1） 0(mod5) 10(mod715) 140(mod247) 245(mod391) 109(mod187)x x x x x 令=5，=715=51113，=247=1319，=319=1
7、723，=187=1117 1m2m3m4m5m故=51113171923=23094512345,Mm m m m m令=511=55，=1319，=1723，所以同余式组（1）与同余式组2n3n4n同解。因1319172310(mod5 11) 140(mod13 19) 245(mod17 23)x x x 1 11(mod11 5)M a 1a1(mod55)965771a1(mod55)52，取=18，1a1(mod55)1a2150516，取=139221(mod11 5)M a 2a1(mod247)2a1(mod247)2a13585291，取=43331(mod391)M a
8、 3a1(mod391)3a1(mod391)3a故=965771811+21505139140+13585432451 1 122233 3xM a cM a cM a c578989135 10020 。(mod230945)孙子定理在数论中是一个很重要的定理，在之前的剩余系中，有些内容在这里得以补充， 接下来我们证明定理定理 3 若，分别过模， , 的完全剩余系，则1b2bkb1m2mkm过模 m=的完全剩余系。 11 1222xM M bM M b(mod)kkkM M bm1m2mkm证证 令，则过个数。这 m 个数是两两不同余的。 0 1kiii ixM M b0x1m2mkm这因
9、为若11(mod)kkiiiiii iiM M bM M bm则 ，i=1，2，k， iiiM M b iiiM M b (mod)im即 i=1，2，k。但，是模的同一完全剩余系中的二数， ib ib (mod)im ib ibim故=，i=1，2，k。从而结论成立。 证完证完 ib ib由上述的定理我们知：任意的现行同余式组都可以用孙子定理来解，但非线性同余式 或非线性同余式组又如何用孙子定理呢？ 下面我们有定理定理 4 设为整系数多项式，且( )f x（1）( )f x0(mod)m其中， , 两两互质， =，则同余式（1）与同余式组1m2mkmm12m mkm（2） 12( )0(mo
10、d)( )0(mod). ( )0(mod)kf xmf xmf xm 等价。并且若用表示，i=1，2，k，对模的解数，T 表示（1）iT( )0(mod)if xmim对模 m 的解数，则。 （3） 1 2TTTkT证证 （i） 我们先证（1） ， （2）等价。设是适合（1）的整数，则 0x。0()0(mod)f xm由 = 即得m12m mkm，i=1，2，k 。0()0(mod)if xm反之，若适合（2） ，则0x，i=1，2，k 。 0()0(mod)if xm由 即得(,)1ijm m()ij， 0()0(modf x12m mkm )故（1） ， （2）等价。（ii） 设的个不同
11、解是( )0(mod)if xmiT，=1，2，(mod) iitixbmitiT则（2）的解即下列诸同余式组的解：， （4） 111(mod)txbm 222(mod)txbm(mod) kktkxbm其中=1，2，i=1，2，k 。由（i）知（1）的解与（4）的解相同。但由孙itiT子定理知（4）中每一同余式组对模 m 恰有一解，故（4）有对 m 的个解。又由1 2TTkT于此个解对模 m 两两不同余。故（1）对模 m 的解数是1 2TTkT。 证证1 2TTTkT完完 例例 2 2 解同余式， （1）( )0(mod35)f x 43( )289f xxxx解解 由（1）与同余式组 ，等
12、价，容易验证( )0(mod5)f x ( )0(mod7)f x 第一个同余式有两个解： 即，1,4(mod5)x 而第二个同余式有三个解： 即，3,5,6(mod7)x 故同余式（1）有 23=6 个解。即诸同余式组，=1，4，=3，5，6 的解。1(mod5)xb2(mod7)xb1b2b由孙子定理得 122115(mod35)xbb以，的值分别代入即得（1）的全部解：。1b2b31,26,6,24,19,34(mod35)x 33 结束语结束语 通过对孙子定理的理解，我们来看下韩信点兵的问题，有兵一队，若列成五行纵队， 则余一人，列成六行纵队，则余五人，列成七行纵队，则余四人，列成十一
13、行纵队，则余十人，求兵数。5 第一步 因五行纵队余一人，该对兵数或为 6，或为 11，或为 16，即由 1 或 1 逐 次累加 5 得到 累加的同时用 6 试除，求得第一个余数为 5 的数时，累加停止，得到同时满 足前两个条件的最小自然数，这里求得 11。 第二步 为保证前两个条件总能满足 11 或 11 逐次累加 5 或 6 的最小公倍数 30，得 到：11,41,71累加同时用 7 试除，求得第一个余数为 4 时，累加停止，得到同时满足前三 个条件的最小自然数，这里仍是 11，属特例，无须累加。 第三步 为保证前三个条件总能满足 11 或 11 逐次累加 5、6 和 7 的最小公倍数，累加的同时用 11 试除，求得第一个余数为 10 的数即为本题的解，这里求得在第 10 次累加试 除后得 2111 从而得到解参考文献参考文献1 闵嗣鹤,严士健初等数论(第三版) M1 北京:高等教育出 版社,20031.76-79. 2 晏能中. 孙子定理的推广和应用J. 达县师专学报, 1994, (02) . 3 王芳珍，王宪清. 孙子定理的一种推广形式J. 新疆师范大学学报(自然科学 版), 1994, (02) . 4 杨迎球. 中国剩余定理与同余式组
