畢業(yè)論文：孫子定理的探討與應(yīng)用

摘要本文主要討論了孫子定理的背景、由來(lái)、證明方法以及一些簡(jiǎn)單的應(yīng)用,文中闡述了孫子定理的由來(lái)，介紹了它的幾種解法，及其它在多項(xiàng)式，生活方面的應(yīng)用.孫子定理在高中有初步的基礎(chǔ)應(yīng)用，在大學(xué)中的初等數(shù)論中該定理得到了仔細(xì)的講解.孫子定理的思想方法和原則不僅有光輝的歷史意義，而且在近代數(shù)學(xué)中仍然有著重大影響和作用.關(guān)鍵詞：同余；一次同余式；同余式組；孫子定理ABSTRACTThispapermainlydiscussesthebackground,origin,methodtoprovetheChineseRemainderTheoremandsomesimpleapplications,thispaperexpoundstheoriginoftheChineseremaindertheorem,introducesseveralmethodsofit,andtheotherinpolynomial,applicationoflife.TheChineseremaindertheorembasedontheinitialapplicationinhighschool,ElementarynumbertheoryinUniversityinthistheoremarecarefullyexplained.ThoughtmethodandtheprincipleofChineseremaindertheoremnotonlyhastheglorioushistoricalsignificanceinmodernmathematics,andstillhaveimportantinfluenceandrole.Keywords:Congruence;linearcongruences;congruencegroup;Chineseremaindertheorem目錄TOC\o"1-5"\h\z\o"CurrentDocument"前言 I\o"CurrentDocument"第一章同余 1.\o"CurrentDocument"1.同余的概念及性質(zhì) 1.2.一次同余式的解法 3.\o"CurrentDocument"第二章孫子定理 7.1.孫子定理定理的由來(lái) 7.2.孫子定理的證明 7.3.孫子定理的解法 9.列方程組法 9.不定方程解法 1.0同余解法 1.13.4用孫子定理解答 11\o"CurrentDocument"第三章孫子定理的應(yīng)用 13在古典問(wèn)題中的應(yīng)用 13在數(shù)學(xué)奧林匹克中的應(yīng)用 14在初等數(shù)學(xué)中的應(yīng)用 144.在生活中的應(yīng)用 15\o"CurrentDocument"參考文獻(xiàn) 16\o"CurrentDocument"致謝 17前言孫子定理源于我國(guó)古代《孫子算經(jīng)》,其中有一題:“今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問(wèn)物幾何？”“答曰二十三”.對(duì)于答案的求法書(shū)中做出了如下的敘述：“術(shù)曰：三三數(shù)之剩二，置一百四十；五五數(shù)之剩三，置六十三；七七數(shù)之剩二，置三十，并之，得二百三十三；以二百一十減之即得.”上述問(wèn)題用同余式來(lái)表示，就是x三2(mod3)，x三3(mod5)x三2(mod7)《孫子算經(jīng)》中給出最小正整數(shù)解23,解法傳至今世.“孫子定理”又稱(chēng)“中國(guó)剩余定理”.它是初等數(shù)論中重要定理之一，在代數(shù)數(shù)學(xué)和計(jì)算機(jī)領(lǐng)域中也有重要應(yīng)用.本文主要討論孫子定理的背景以及證明.第一章同余第一章同余1.同余的概念及性質(zhì)定義1.1給定一個(gè)正整數(shù)m,m去除任意兩個(gè)整數(shù)a與b所得的余數(shù)相同，我們就說(shuō)a,b對(duì)于模m同余，記作a三b(modm).讀作a與b對(duì)于ma,b對(duì)于模m的余數(shù)不同，就說(shuō)a,b對(duì)于模m不同余，記作a尹b(modm),讀作：a與b對(duì)于m不同余. [4][4]定理1.1數(shù)a與b對(duì)于模m同余的充分必要條件是：m(a-b)，[4]即a三b(modm)?m|(a一b).證明“n"設(shè)a=mq+r，b=mq+r，0<r<m，0<r<m.112212若a三b(modm)，則r=r.因此，a一b=m(q一q)nm|(a—b).12121“u”m|(a—b)n(mq+r)一(mq+r)=m(q一q)+(r+r)111221212r2)艮卩|r一r=(a一b)一m(q一q)nr2)1121211一m<-r<02一m<r一r<mn|r—rI<m,121121即r一r=012故r=r,12即a€b(modm).定理1.2同余的三個(gè)基本性質(zhì)： [4](1)a三a(modm)(反身性);⑵若a三b(modm),貝Ub三a(modm)(對(duì)稱(chēng)性);[4]⑶若a三b(modm),b三c(modm),則a三c(modm)(傳遞性).[4]定理1.3若a三b(modm),a三b(modm)，貝U有:1122(1)a+a€b+b(modm)；1212a一a€b一b(modm)；1212⑶aa三bb(modm)；1212a⑷亠

aa⑷亠

a2i(modm)；b2[6]若a三b(modm),且a=ad,b=bd,(d,m)=1,1故mla—b,即a三b(modm)；TOC\o"1-5"\h\z1ii ii(i)若a三a(modm),k?0貝Uak三bk(modmk)；(ii)若a三b(modm),d是a,b及m的任一正公因數(shù)，則ab m三一(mod—)；

dd d若a三a(modm),i=1,2,?…,k,則ia€b(mod[m,m,€m]).1 2 k2.一次同余式的解法定義2.1如果a,b都是整數(shù)，m是一個(gè)正整數(shù)，那么當(dāng)a尹0(modm)時(shí)，我們把a(bǔ)x€b(modm)叫做模m的一元一次同余式(簡(jiǎn)稱(chēng)同余式). [5]如果有一個(gè)整數(shù)c，它能使ac€b(modm)成立,那么我們就把x三c(modm)叫做同余式ax€b(modm)的一個(gè)解(或一個(gè)根).這就是說(shuō)，同余式ax三b(modm)的一個(gè)解是指適合這個(gè)同余式而對(duì)模m同余的一切整數(shù)解，即x=c€mt(t為任意整數(shù)),這里的整數(shù)c使ac三b(modm)x三l(mod7)，即x二1€7t(t為任意整數(shù))，是同余式2x三2(mod7)的一個(gè)解.定理2.1—次同余式ax三b(modm)，a,0(modm? (1.1)有解的必要且充分條件是： [5](a—m)|b.設(shè)(a,m)二d，d|b則同余式(1.1)有d個(gè)解.證明設(shè)x是同余式(1.1)的一個(gè)解，則有0ax=b€ym?00這里的y是整數(shù)，因此x，y是不定方程ax—ym二b的一組解；反之，若000x二x，y二y是不定方程的一組解，則11ax—ym二b11艮卩 ax—b=ym，11所以 ax，b(modm)?1這就是說(shuō)，同余式(1.1)有解的必要與充分條件是不定方程ax—ym二b有解的必要且充分條件，也就是：(a—m)|b1.用輾轉(zhuǎn)相除法解同余式：例1解同余式7x三5(mod9).

解： (7,9)€1,1|5故只有一個(gè)解.7x-9y€1解得x=4,y=3代入得：7,4-9,3€1,因此 4,7三1(mod9).在原同余式兩邊同乘以4,得：4x7x三5x4三20(mod9)因此 x三20三2(mod9).即原同余式的解為x三2(mod9)2.用系數(shù)消去法解同余式：用系數(shù)消去法解同余式ax三b(modm)的一般步驟是：先同余式寫(xiě)成x三—(modm)a—注意：這里的“分?jǐn)?shù)”—僅僅是一種形式寫(xiě)法，而不是真正意義上的分?jǐn)?shù)；a然后用與m互質(zhì)的數(shù)陸續(xù)乘右邊的“分子”與“分母”，或者在“分子”,“分母”上減去模m的倍數(shù)；或者對(duì)“分子”，“分母”約去公有的且與模m互質(zhì)的約數(shù)，通過(guò)這樣變換，目的是使“分母”的絕對(duì)值變小，直到變?yōu)?為止.例2用系數(shù)消去法解下列同余式：(1)8x三1(mod15) (2)7x三11(mod15) (3)15x三6(mod21)解：(1)x三三 三三—(mod⑸.因此同余式的解為：8881x三2(mod15)2)11三11x2)11三11x27=7x222三22-1514=14-15三—L(mod15)；因此同余式的解為:x三-7(mod15)，x三8(mod15)保山學(xué)院本科畢業(yè)論文（設(shè)計(jì)）3）因?yàn)椋?5，21）€3，所以在原同余式兩邊約去3，得5x三2(mod7)x三一x三一30三6(mod7).5 1得到同余式的一個(gè)解為 x三6（mod7）即 x€6+7k（k為任意整數(shù)）當(dāng)k€0時(shí)x€6；k€1時(shí)x€13；k=2時(shí)x=13；k=2時(shí)x=20.x€6,13,20這三個(gè)數(shù)都是模21的最小非負(fù)剩余，所以原同余式的三個(gè)解為x三6（mod7）x三13(mod21)x三20(mod21)第二章孫子定理在我國(guó)古代勞動(dòng)人民中，長(zhǎng)期流傳著“隔墻算”、“剪管術(shù)”、“秦王暗點(diǎn)兵”等數(shù)學(xué)游戲.有一首“孫子歌”，甚至遠(yuǎn)渡重洋，傳入日本：“三人同行七十稀，五樹(shù)梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知”這些饒有趣味的數(shù)學(xué)游戲，以各種不同形式，介紹世界聞名的“孫子問(wèn)題”的解法，通俗地反映了中國(guó)古代數(shù)學(xué)一項(xiàng)卓越的成就.“孫子問(wèn)題”在現(xiàn)代數(shù)論中是一個(gè)一次同余問(wèn)題，它最早出現(xiàn)在我國(guó)公元四世紀(jì)的數(shù)學(xué)著作《孫子算經(jīng)》中《孫子算經(jīng)》是算經(jīng)十書(shū)之一，又作《孫子算術(shù)》.中國(guó)古代求解一次同余式組的方法.是數(shù)論中一個(gè)重要定理.為了比較清楚地了解“孫子定理”這一名稱(chēng)的由來(lái)，我們不妨先引進(jìn)同余定義：般地，若兩個(gè)整數(shù)a,b被同一個(gè)大于1的整數(shù)m除有相同的余數(shù)，那么稱(chēng)a,b對(duì)于模m同余.記作a三b(modm).應(yīng)用同余原理，我們把“物不知其數(shù)"問(wèn)題用整數(shù)的同余式符號(hào)表達(dá)出來(lái)是：設(shè)N三2(mod3)三3(mod5)三2(mod7),求最小的數(shù)N?答案是N二70,2?21,3?15,2-2,105二23. “物不知其數(shù)”開(kāi)創(chuàng)了一次同余式研究的先河，但真正從完整的計(jì)算程序和理論上解決這個(gè)問(wèn)題的是南宋時(shí)期的數(shù)學(xué)家秦九韶，秦九韶在他的《數(shù)書(shū)九章》中提出了一個(gè)數(shù)學(xué)方法"大衍求一術(shù)”.1876年,德國(guó)人馬蒂生首先指出這一解法與19世紀(jì)高斯《算術(shù)探究》中關(guān)于一次同余式組的解法完全一致.從此，中國(guó)古代數(shù)學(xué)這一創(chuàng)造受到世界學(xué)者矚目，并在西方數(shù)學(xué)史著中正式稱(chēng)為“中國(guó)剩余定理”?孫子定理：如果n…2,m,m，…,m是兩兩互質(zhì)的n個(gè)正整數(shù),1 2 n

保山學(xué)院本科畢業(yè)論文(設(shè)計(jì))令M€mmm...m=mM=mM=123n保山學(xué)院本科畢業(yè)論文(設(shè)計(jì))令M€mmm...m=mM=mM=123n1 1 2 2€mM則同余式組nn?x…b(modm)1 1x…b(modm)<2 2x…b(modm)nn有正整數(shù)解x€bM'M+bM'M+…+bM'M1 1 1 2 2 2 nnn(modM)；其中M'是滿(mǎn)足i的一個(gè)整數(shù).證明M'M三1(modm),(i=1,2，…,n)ii i[5]先證存在性：因?yàn)閙,m…,m1 2,n兩兩互質(zhì)，所以當(dāng)i豐j時(shí),(m,m)€1,又由于M€M，因此(M,m)=1所以有ij im iii(M,m)€(M,m)=…=(M,m)=1.1 1 2 2 nn由于(M,m)€1,根據(jù)裴蜀恒等式(如果兩個(gè)數(shù)a,b的最大公約數(shù)是d，那么存ii在兩個(gè)整數(shù)x,y使得等式ax+by=d成立)可知，一定存在整數(shù)M;與々，使得M'M+mk€1,1111也就是說(shuō)，一定能找到M'，使得1M'M…1(modm)111成立?用同樣的方法知道，對(duì)每一個(gè)M，一定存在有一個(gè)正整數(shù)M'，使得i1M'M三1(modm)(i=1,2,…，n),111又因?yàn)楫?dāng)i豐j時(shí)，由(m,m)€1與M=M可得mM，所以有ij im ijibM'M三0(modm)(i豐j)?jjj i因此若令R€bM'M+bM'M+…+bM'M，1 1 1 2 2 2 nnn

R€bM'M€b(modm),則有11111

R€bM'M€b(modm),則有22222TOC\o"1-5"\h\zR€bM'M€b(modm).

nnnn n由于m,m…,m兩兩互質(zhì)，所以1 2,n,m€,m=m,m €,m =M，1 2,n1 2,n這樣M」M,即M三0(modm).又根據(jù)上式，可矢口x=R?Mt€b(modm),11x=bM'M?bM'M?€?bM'M(modM)nnn11122nnn是同余式組的正整數(shù)解.面證明解的唯一性.設(shè)y也是同余式組的解，設(shè)y也是同余式組的解，設(shè)y也是同余式組的解，則x=…bM'M(modM)iiii=1是同余式組的解，可得x€y(modm)，1x€y(modm)，2x€y(modm).n也就是有mi也就是有mi|(x—y)(i=1,2,?…,n)的公倍數(shù)，而M是m€,m最小公倍數(shù)2,n所以得 M|(x—y),艮卩x三y(modM).所以x=bM'M?bM'M?…?bM'M(modM)是滿(mǎn)足同余式組的唯一1 1 1 2 2 2 nnn(4)(5)(6)(teZ)(4)(5)(6)(teZ)(7)1?W=3x+2 (1)<W=5y+3 (2)W=7z+2 (3)消去W，得到 3x+5y=1(W,x,y,zeN)(4)(5)(1)問(wèn)題的通解y、z則有:保山學(xué)院本科畢業(yè)論文(設(shè)計(jì))設(shè)被所得的整數(shù)商分別為依題意3x€2=5y€3=7z+2=N于是有PF=1⑵,5y-7z=-1 (3)?x=2+5t解方程⑵得通解?,y=1+3t(teZ)將⑸式代入⑶得7z-15t=6?t=-1一7t此不定方程的通解為?_iIz=3+15t1將(6)代入(4)，(5)同時(shí)考慮式(7)得原方程組的全部整數(shù)解為T(mén)OC\o"1-5"\h\zx=7+35t (8)<y=4+21t (9)1z=3+15t (teZ) (10)11上式三式(8)，(9)，(10)中任意一個(gè)代入(1)得“物不知其數(shù)N=23+105tN=23+1051，當(dāng)t=0時(shí)N=23是最小的正整數(shù)解111不定方程解法由(5)式得7zx=-3令z=3t(teN)，得z由(5)式得7zx=-3令z=3t(teN)，得z=3t111x=7t (6)1從而有y=21t-11 t-1再令-1 =t (teN)5 2 2則t二5t€1???x二351€7y二t€4z二151€3W三23(mod)105,這就是12222“物不知數(shù)”問(wèn)題的通解公趣然當(dāng)t二0時(shí)，有最小正整數(shù)解W=23.2同余解法物不知數(shù)”問(wèn)題用同余式組來(lái)表達(dá)，即W，2(mod3)(1)…W，3(mod5)(2)W，2(mod7)(3)解：由⑴得W二2€3k (4)1代入(2)式得2€3k三3(mod5)13k，1(mod5)13k三6(mod5)1k，2(mod5)1k三2€5k12將其代入⑷式有 W二8€3k (5)2由(5)、(3)得：8€15k三2(mod7)28€15k三9(mod7)215k，1(mod7)215k，15(mod7)2k，1(mod7)2k=1€7k23將k代入⑸式，得W二23€105k，即W三23(mod105)23???3、5、7兩兩互質(zhì)，所以W三23(mod105))是同余式組的解.3.4用孫子定理解答“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”“答曰二十三”.保山學(xué)院本科畢業(yè)論文（設(shè)計(jì)）???3、5、7兩兩互素貝Vm€3x5x7€105,M€5x7€35,M€3x7=21,M=3x5=151 2 3又???2x35三l(mod3),1x21三1(mod5),1x15三1(mod7),故W三2x35x2+1x21x3+1x15x2三233三23(mod105)???最小正整數(shù)為23.第三章孫子定理的應(yīng)用例1：“韓信點(diǎn)兵”的問(wèn)題：有兵一隊(duì)，若列成五行縱列則末行一人；成六行縱隊(duì)，則末行五人；成七行縱隊(duì)，則末行四人；成十一行縱隊(duì)，則末行十人，求兵數(shù).解：“韓信點(diǎn)兵”問(wèn)題轉(zhuǎn)化為數(shù)學(xué)語(yǔ)言即求解下列一次同余式組x?l(mod5)€€x?5(mod6),€x?4(mod7)x?lO(modll)由孫子定理知m=5,m=6,m…7,m…11兩兩互素，又

l234M…5x6x7x11…2310M…6x7x11…462€1，M…5x7x11…3852M…5x6x11…330€3M…5x6x7…2104又要求a.M三1(modm),i…1,2,3,4,得a=3,a=a=a=1,TOC\o"1-5"\h\zii i i 2 3 4又c…1,c…5,c…4,c…10,1 2 3 4于是 x三Mac+Mac+Mac+Mac(modM)111 222 333 444?462x3x1+385x1x5+330x1x4+210x1x10(mod2310)?1386+1925+1320+2100(mod2310)?6731(mod2310)?2111(mod2310)即韓信的兵有2111+2310k,k為非負(fù)整數(shù).保山學(xué)院本科畢業(yè)論文(設(shè)計(jì))定義沒(méi)有重復(fù)因子的數(shù)稱(chēng)為無(wú)乘方數(shù)；比如15二3€5是無(wú)乘方數(shù)，而12二22€3則不是.例2：是否存在21個(gè)連續(xù)的正整數(shù)，其中每一個(gè)數(shù)均至少可以被一個(gè)不小于2且不大于13的素?cái)?shù)整除？分析：如果n可以被210二2€3€5€7整除，那么對(duì)于21個(gè)連續(xù)整數(shù)n一10，n一9，n一8， ， n+9，n+10中除去n+1n一1這兩個(gè)數(shù)，當(dāng)n一1可被11整除，同時(shí)n+1可被13整除(或者反過(guò)來(lái))時(shí)，于是我們就得到所求的21個(gè)連續(xù)整數(shù)了.解：依上面的分析，只要n滿(mǎn)足'n三0(mod210)<n三1(mod11)n三—l(modl3)就得到所求的數(shù)列了，為完整起見(jiàn)，那么來(lái)求這一同余組的解.注意：n二210滿(mǎn)足前兩個(gè)同余式，于是對(duì)任意的k只要令n二210€11€k+210滿(mǎn)足最后一個(gè)同余式，選取k使得210€11€k=2310k三，211(mod13)此式化簡(jiǎn)為9k三—3(modl3)而k=4是顯然是解了，于是n二4€2310+210二9450是一個(gè)解(最小正解)例3： 求最小正整數(shù)x使得它被3、5、7除的余數(shù)分別是1、2、3解： 設(shè)x是所求整數(shù)，則它滿(mǎn)足方程組x三2(mod3)

，x三3(mod5)x三2(mod7)由于3、5、7兩兩互素，故由孫子定理知，此同余式恰有一解，Tm…3,m…5,m…7,m…3x5x7…105,TOC\o"1-5"\h\z1 2 3M…5x7…35,M…3x7…21,M…3x5…151 2 3令M-M'三1(modm)(i…1,2,3),可分別求得1i iM，…―1,M'…1,M'…1,于是1 2 3x?1x35x(―1)+2x21x1+3x15x1?52(mod105)因此，所求整數(shù)為x…52+105t,(t…0,±1,±2,?…),故所求最小正整數(shù)為52.在日常生活中我們所注意到的不是某些數(shù)，而是這些數(shù)去除某一固定的數(shù)所得到的余數(shù).例如，假定現(xiàn)在是早上10點(diǎn)，在兩個(gè)小時(shí)前是幾點(diǎn)？我們立刻可得到正確答案是早上8點(diǎn)那么過(guò)了13個(gè)小時(shí)后又是幾點(diǎn)呢？算式為10+13—12…11即晚上11點(diǎn)；在28個(gè)小時(shí)