孙子定理及其应用

《孙子定理及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学术论文孙子定理及其应擢姓名所在学院专业班级学号指导教师曰期【关键词】孙子定理同余方程组剩余类标准分解式Abstract:thispapermainlyexplaingrandsontheoremandinsolvingnonlinearcongruencetypeapplication.Keywords:grandsontheoremofcongruencedecompositionofthestandardtypeofsurplusequations§1引言实际上，孙子定理由闵嗣鹤，严士健在文［1］屮详细描述并证明了；王芳珍，王宪清的“孙子定理的一种推广形式”［

2、3］进一步阐述了其相关应用；杨迎球在“中W剩余定理”［4］中提出了同余式组的一种较为简捷易懂的解法，……，其目的都是为了更好地将孙子定理推广及应用，下面我们来看定理1（孙子定理）［1］设m,,m2，…，.是k个两两互质的正整数，m=mlfn2…mk,i=l，2,…，k，则同余式组＜（1）的解是(2)x=b}(mod)x=b2(modm2)x=bk(modmk)x=MyMxb{+M2M2b2+…+A/A,MA(modm),其屮•三1（modm,），i=l，2，…，k.证由（m,.，mp=l,/弇j•即得（Wz，m,.）=l,故知对每一A/,，有一存在，使得Mi=1（m

3、odz??z）.另一方面m=,因此m.Mj,Z矣j•，故klo.=MiMibi=bi（mod）即为（1）的解.若，又2是适合（］）式的任意y=i两个整数，则&三又2（mod%）,，•=】，2，…，k，因于是$三又2（mod，打），故（1）的解只有（2）.证完由上述我们知道，孙子定理的重要条件是模％,m2，…，m/两两互质，那如果两两不互质，我们怎么解决呢？§2主要结论x=cn(modmn)当m"，n2，…，m/两两不互质时，我们有定理2[2]设叫，z/z2，…，m„为正整数，其标准分解式分别为：/?i]=p^p^2-,m2=pc]p?2-p?，…，mn=p»2…/

4、/fo取M=[州,，m2,…，m"]=…/’，，>0,i=l，2，…，t。其中勾=max{“H,«21，…，anX},…，<=max{〜，“2/，…，ant}.当同余式组(1)x=c,(modm,)x=c2(modm2)有解，则其解与同余式组(2)x=c(modp^})x=c2(mod)x=cn(mod^)的解完全相同。证因=[%，//^，…，mj=l々…p〉1p》、一定能整除某一个mz，不妨设,同理可假设pp

5、m2，…，pktl

6、mz.,又因同余式组(1)有解，其解一定是以州2，…：/'的最小公倍数为剩余类解，即XEXQ(modAZ)。所以x0是满足同余式组(1

7、)的一个整数。因而有x()三c/modm'.)，/=1,2,…，n。因/^,/=1,2，…，t(t

8、解》)。x三0(mod5)x=10(mod715)解依题意得：(1)Jx=140(mod247)x=245(mod391)x=109(modl87)令州,=5,m2=715=5*11*13,=247=13-19,z??4=319=17-23,z??5=187=11*17故M=[m,，/n2，/n3，m4，m5]=5•11•13•17•19•23=230945x=10(mod5*l1)令/?2=5.11=55,n3=13.19,久=17.23,所以同余式组(1)与同余式组三140(mod13M9)x=245(mod17*23)同解。因AZ!%三l(modll*5)=>

9、13•19•17•23%=l(mod55)=>96577a}=l(mod55)=>526/,=l(mod55),取“,=18，M三l(modl1*5)=>21505(7,三l(mod247)16tz7=l(mod247),取％=139M3a3=l(mod391)=>13585a3=l(mod391)^>291a3=l(mod391)3,取％=43故;c=A/wq+W2“2c2+A13“3(;3=96577•18•11+21505•139•140+13585•43•245=578989135=10020(mod230945)。孙子定理在数论中是一个很重要的定理，在