初等數(shù)論第四章同余式

第四章同余式§1基本概念及一次同余式初等數(shù)論中的一個基本課題是研究同余式(同余方程)的求解問題。定義1設meZ+,f(x)=a其中aeZ,貝I」nn-10if(x)三0(modm)稱為模m的同余式。若a豐0(modm),貝骯稱為次數(shù)。n定義2若a是使f(a)三0(modm)成立的一個整數(shù)，則x三a(modm)叫做f(x)三0(modm)的一個解。定義2的合理性：若f(a)三0(modm)，則剩余類K中的任意整數(shù)a，都能使af(a')三0(modm)成立，故把K中的一切數(shù)，即x三a(modm)作為一個解。a定理設(a,m)=d則一次同余式ax三b(modm)有解的充分必要條件是dIb。當此條件成立時，同余式共有d個解，它們是x三x三x+k-m(modm)，0dk=0,1,…,d—1,其中x是同余式ax三b(modm)的任一個解。0證明⑴同余式ax三b(modm)有解o不定方程ax+my=b有解odIb。⑵因為不定方程ax+my=b的一切整數(shù)解為x=x+mt，teZ,所以,同余式解數(shù)為d。同余式解數(shù)為d。ax三b(modm)的解為x三x+k—(modm),k=0,1,…,d—1,

0d注當(a,m)=1時，一次同余式有唯一解x三a車?)-ib(modm)。同余式的解法1、代入法(適用于模較小時)例1解同余式3x三1(mod17)解因為(3,17)=1,所以同余式有唯一解，以17的完全剩余系逐一代入，得x三6(modl7)。2、公式法(適用于模較小時)例2解同余式8x三9(mod11)解因為(8,11)=1，所以同余式有唯一解，從而，x三8車11)-1?9三810-1?9三(-3)9-(一2)三(-2)4-6三5-6三8(mod11)。3、變換系數(shù)法例3解下列同余式4x三1(mod15)；14x三27(mod31)；103x三57(mod211)。解⑴因為(4,⑸=1,所以同余式有唯一解，而4x三1三16(mod15)，故x三4(mod15)。(2)因為(14,31)=1,所以同余式有唯一解，而14x三27三58(mod31)，7x三29三60三91(mod31)，故x三13(mod31)。⑶因為(103,211)=1,所以同余式有唯一解，由103x三57(mod211)可得206x三114(mod211)，于是—5x三114(mod211)即5x三97(mod211)，再由5x三97(mod211)可得210x三97-42(mod211)，于是—x三97-42三65(mod211)故x三-65三146(mod211)。

4、換模法由ax三b(modm)(1)可得ax=b+my,模a后可得my三-b(moda)(2),當0<a<m時，解(2)比解(1)方便，而且若y是(2)的解，貝吐=耳竺是(1)的解。00a例4解同余式863x三880(mod2151)解因863是質數(shù)，且863J2151，故(863,2151)=1,從而同余式有唯一解,原同余式可化為863x=880+2151y，模863后得2151y三-880(mod863),即425y三-880(mod863),也即85y三—176(mod863),再化為85y=—176+863z，模85后得863z三176(mod85),即13z三6(mod85),再化為13z=6+85u，模13后得85u三一6(mod13),即7u三7(mod13),也即u三1(mod13),所以u=1所以u=1,06+85-1—176+863-7“z==7,y==69,013085880+2151?69863即x三173(mod2151)是原同余式的解。5、輾轉相除法例5解同余式863x三880(mod2151)解因為(863,2151)=1,所以同余式有唯一解利用輾轉相除法可得-496?863+199?2151=1,模2151后得—496?863三1(mod2151),所以x三—496?880三173(mod2151)。例6解同余式6x三15(mod33)解因為(6,33)=3115,所以同余式有3個解，由原同余式可得2x三5(mod11),解得x三8(mod11),因此原同余式的解為x三8,19,30(mod33),?！?孫子定理本節(jié)討論同余式組x三b(modm),x三b(modm),???,x三b(modm)1122kk的求解問題。定理1(孫子定理)設m,m，…,m是兩兩互質的正整數(shù)，m=mm…m,12k12km=mM,i=1,2,…,k,則同余式組x三b(modm),x三b(modm),???,TOC\o"1-5"\h\zii1122x三b(modm)的解是x三MMb+MMbHbMMb(modm),kk111222kkk其中MM三1(modm),i=1,2,…,k。iii證明因為(m,m)=1,i豐j所以(m,M)=1,于是Mx三1(modm)ijiiii有一解，設為M，貝9MM三1(modm),i=1,2,…,k,iiii又因為m=mM，所以mIM,i豐jiijirrrf于是MMb+MMbHbMMb三MMb三b(modm),111222kkkiiiii故x三MMb+MMb+…+MMb(modm)是原同余式組的解。111222kkk若x,x是適合同余式組的任意兩個整數(shù)，12貝9x三x(modm),i=1,2,…，k,于是x三x(modm),12i12fff因此，原同余式組只有一個解x三MMb+MMb+—bMMb(modm)。111222kkk推論1設正整數(shù)m,m，…,m兩兩互質，則同余式組12kax三b(modm),ax三b(modm),?…,ax三b(modm)111222kkkTOC\o"1-5"\h\z有解的充分必要條件是同余式ax三b(modm),i=1,2,…,k有解。iii證明必要性是顯然的，下證充分性。因為對i=1,2,…,k，同余式ax三b(modm)，所以dIb，這里d=(a,m)，iiiiiiii于是有ci使”三1(mod滬，從而原同余式組等價于iix三c廿(modi),x三c獷(mod1x三c廿(modi),x三c獷(mod1dd2d1122kk推論2若b,b,…,b分別通過模m,m,…,m的完全剩余系，則12k12kfffx三MMb+MMbHFMMb(modm)111222kkk通過模m=mm…m的完全剩余系。12k證明令x=工MMb，貝Ijx過mm…m個數(shù)，這m個數(shù)兩兩不同余。0iii012k這是因為若工M‘M這是因為若工M‘Mbiiii=1ZffMMb(modm)，

iiii=1i=1,2,…,k,i=1,2,…,k,矛盾。則MMb三MMb(modm)，即b三b(modm)，iiiiiiiiii定理1之所以稱為“孫子定理”，因為在我國古代的數(shù)學著作《孫子算經(jīng)》(紀元前后)中已經(jīng)提出了這種形式的問題，并且很好地解決了它。孫子定理在國外文獻和教科書中均稱為“中國剩余定理”，并且在代數(shù)學中被推廣成非常一般的形式。孫子算經(jīng)》中所提出的問題之一如下：今有物不知其數(shù)，三三數(shù)之剩二，

五五數(shù)之剩三，七七數(shù)之剩二，問物幾何答曰：二十三。用現(xiàn)在的記號，上述問題相當于求解同余式組x三2(mod3),x三3(mod5),x三2(mod7)。孫子算經(jīng)》中所用的方法可以列表如下：除數(shù)余數(shù)最小公倍數(shù)衍數(shù)乘率各總答數(shù)最小答數(shù)323X5X7=1055X7235X2X2140+63+30=233233-105X2=23537X3121X1X3723X5115X1X2程大位在《算法統(tǒng)宗》(1593)中將這一問題的算法總結成如下歌訣：三人同行七十稀，五樹梅花廿一枝，七子團圓半個月，除百零五便得知。推廣為一般的列表算法：除數(shù)余數(shù)最小公倍數(shù)衍數(shù)乘率各總答數(shù)m1b1m二吧…mkM1M'1MM'b111x三乞MM'b(modm)iiir=11

12341234解m=5-6-7-11=2310,M=6-7-11=462,M=5-7-11=385,12M二5?6?11二330,M二5?6?7二210,34f得f得M=31f得M=12f得M=13f得M=14解同余式462M三1(mod5)1f385M三1(mod6)2f330M三1(mod5)3f210M三1(mod5)4因此同余式組的解為x三3-462-b1+1-385-b+1-330-b+因此同余式組的解為x三3-462-b1234例2韓信點兵：有兵一隊,若列成五行縱隊,則末行一人,成六行縱隊,則末行五人,成七行縱隊,則末行四人,成十一行縱隊,則末行十人。求兵數(shù)解設兵數(shù)為x,貝Vx三1(mod5),x三5(mod6),x三4(mod7),x三10(mod11)故解為x三3-462-1+1-385-5+1-330-4+1-210-10三6731三2111(mod2310)。定理2同余式組x三b(modm),i=1,2,…,k有解的充分必要條件是iib三b(mod(m,m)),i豐j=1,2,…,k。ijij若上述條件成立，則同余式組對模［m,m,…,m］有唯一解。12k例3解同余式組x三8(mod15),x三3(mod10),x三l(mod8)。解因為8三3(mod(15,10)),8三1(mod(15,8)),3三1(mod(10,8)),所以同余式組有唯一解。先解同余式組x三8(mod15),x三3(mod10)。由x三8(mod15)可矢口x=8+15y,代入x三3(mod10)得y三1(mod2),代入得x三23(mod30)。再解同余式組x三23(mod30),x三1(mod8),可得原同余式組的解是x三113(mod120)。另解原同余式組可化為x三8(mod5)x三3(mod5)<x三x三3(mod5)<x三2(mod3)x三1(mod23)<x三3(mod5)，即x三3(mod2)x三1(mod23)由孫子定理可解得x三113(mod120)?！?質數(shù)模的同余式本節(jié)討論質數(shù)模的同余式(1)f(x)三0(modp),其中f(x)=axn+axn-ihba,p為質數(shù)，a豐0(modp)。nn-10n定理1同余式⑴與一個次數(shù)不超過p-1的質數(shù)模同余式等價。證明由多項式的帶余除法可知f(x)=(xp-x)q(x)+r(x)，d(r(x))<p-1,由費馬定理可知，VxgZ,有xp一x三0(modp),于是f(x)三r(x)(modp)，因此，同余式⑴與r(x)三0(modp)等價。定理2設k<n,而x=a(modp),i=1,2,…,k是⑴的k個不同的解，貝ViVxgZ,f(x)三(x-a)(x-a)…(x-a)f(x)(modp),其中f(x)是一個n—k12kkk次多項式，首項系數(shù)為a。n證明由多項式的帶余除法可知f(x)=(x-a)f(x)+r,其中f(x)是一111個首項系數(shù)為a的n-1次多項式，r是一個常數(shù)，n因為/(a)三0(modp),所以r三0(modp),于是f(x)三(x-a)f(x)(modp),TOC\o"1-5"\h\zi11令x=a,i=2,3,…,k,貝U0三(a-a)f(a)(modp),ii11i又a羊a(modp),p為質數(shù)，故f(a)三0(modp\從而由歸納法可得結論。i11i定理3(1)VxgZ,xp-1一1三(x一1)(x一2)…(x-(p一1))(modp)；(2)(Wilson定理)(p一1)!+1三0(modp)。證明⑴因為(i,p)=1,i=1,2,…,p-1,所以由歐拉定理可知1,2,…,p-嘟是xp-1-1三0(modp)的解，于是由定理2可知xp-1一1三(x一1)(x一2)…(x-(p一1))f(x)(modp),f(x)為零次多項式，kk首項系數(shù)為1,即xp-1一1三(x一1)(x一2)…(x-(p一1))(modp)。(2)在(1)中令x=0,貝9(-1)(-2)…(-(p一1))三一1(modp),當p=2時，結論顯然成立；當p為奇質數(shù)時，(p-1)!+1三0(modp)。定理4同余式(1)的解數(shù)不超過它的次數(shù)。證明(反證法)設⑴的解數(shù)超過n,則⑴至少有n+1個解，設為x=a(modp),i=1,2,…,n+1,于是由定理2可知if(x)三a(x-a)(x-a)…(x-a)(modp)，n12n又f(a)三0(modp),故a(a-a)(a-a)…(a-a)三0(modp)，n十1nn十11n十12n十1n又因p為質數(shù)，a=0(modp),故必存在a，i=1,2,…,n,有a=a(modp)，niin十1矛盾，因此，結論成立。定理5若n<p,則同余式⑴有n個解的充分必要條件是f(x)除xp-x所得余式的一切系數(shù)都是p的倍數(shù)。證明由多項式的帶余除法可知xp-x=f(x)q(x)+r(x),d(r(x))<n,若⑴有n個解，則由費馬定理可知這n個解都是xp-x三0(modp)的解，于是這n個解也是r(x)三0(modp)的解，但6(r(x))<n,故由定理4可知r(x)的系數(shù)都是p的倍數(shù)。反之，若r(x)的系數(shù)都是p的倍數(shù)，貝9由費馬定理可知f(x)q(x)有p個不同的解(實際上是一切整數(shù))，假設f(x)的解數(shù)小于n,而q(x)的解數(shù)小于等于p-n,于是f(x)q(x)三0(modp)的解數(shù)小于n+(p-n)=p,矛盾，故同余式有n個解。質數(shù)模同余式f(x)=axn+axn-i+…+a三0(modp),a=0(modp)nn-10n的具體解法：1、簡化同余式，一般考慮以下簡化方法：(1)若f(x)的系數(shù)中有大于P的數(shù)，則可將其化到小于P;⑵若6(f(x))>p，則可用xp-x去除f(x),則可得到一個次數(shù)較低的與原同余式等價的同余式；(3)若f(x)關于模p有一個或幾個因式，則也可將原同余式的次數(shù)降低；⑷若f(x)已知有一解或幾解，則可析出因式將次數(shù)降低。2、將模的完全剩余系中的數(shù)逐一代入同余式，檢驗即可得解。例解同余式f(x)=x7-2x6-7x5+x+2三0(mod5)。解化簡系數(shù)，得x7一2x6-2x5+x+2三0(mod5),用x5-x去除，得r(x)=x3-2x2-x+2三0(mod5)與原同余式等價，將模5的完全剩余系-2,-1,0,1,2逐一代入，知原同余式的解是x三-1,1,2(mod5)?！?高次同余式的解法定理1⑴設m,m，…,m是k個兩兩互質的正整數(shù)，m=mm…m，貝V12k12k同余式f(x)三0(modm)與同余式組f(x)三0(modm),i=1,2,…,k等價；i(2)若T表示f(x)三0(modm)對模m的解數(shù)，i=1,2,…,k，T表示同余式iiif(x)三0(modm)對模m的解數(shù)，則T=TT-T。12k證明⑴設x是f(x)三0(modm)的解，則f(x)三0(modm)，00由同余性質6可知f(x)三0(modm)，i=1,2,…,k；0i反之，若x是同余式組f(x)三0(modm)，i=1,2,…,k的解，則0if(x)三0(modm)，i=1,2,…,k，由同余性質5可知f(x)三0(modm)。0i0因此，同余式/(x)三0(modm)與同余式組/(x)三0(modm)，i=1,2,…,k等價。i(2)設f(x)三0(modm)的T個不同的解為x三b(modm)，t=1,2,…,T，iiitiiiii=1,2,…,k,則同余式組f(x)三0(modm)，i=1,2,…,k的解即為下列同余式i組的解x三b(modm),x三b(modm)，…,x三b(modm)，t=1,2,…,T，TOC\o"1-5"\h\z1t12t2ktkii12ki=1,2,-,k,共有TT…個同余式組，由孫子定理可知，每個同余式組對12k模m恰有一解，故有TT…丁個解，并且由孫子定理之推論2可知這TT…T12k12k個解對模m兩兩不同余，因此，f(x)三0(modm)的解數(shù)為TT--T。12k例1解同余式f(x)=x4+2x3+8x+9三0(mod35)。解原同余式與同余式組f(x)三0(mod5),f(x)三0(mod7)等價，而同余式f(x)三0(mod5)的解為x三1,4(mod5)，同余式f(x)三0(mod7)的解為x三3,5,6(mod7)，故原同余式有6個解，它們分別是下列同余式組的解：x三1(mod5)[x三4(mod5)x三3,5,6(mod7)[x三3,5,6(mod7)由孫子定理可得6個解為：x三6,19,24,26,31,34(mod35)。定理2設x三x(modp),即x=x+pt,teZ是f(x)三0(modp)的一1111f解，并且pJf(x)，則x=x+pt恰好給出了f(x)三0(modpa)的一解(對模111pa來說)：x=x+pat,teZ,即卩x三x(modpa)，其中x三x(modp)。aaaaa1證明對a作數(shù)學歸納法。當a=2時，要求由x=x+pt給出f(x)三0(modp2)的一解，也即要求11滿足f(x+pt)三0(modp2)的t。111由泰勒展開可知f(x)+ptf'(x)三0(modp2)，111于是tf'(x)三_""i)(modp)，11pfff因為pJf(x)，即(p,f(x))=1所以同余式對模p有唯一解：三t(modp)，1111f即t=t+pt，teZ，代入x=x+pt得112211fx=x+p(t+pt)=x+p21，teZ,其中x三x(modp)。11222221假設結論對之情形成立，即x=x+pt恰好給出了f(x)三0(modpa-1)的11一解：x=x+pa-it，teZ，x三x(modp)，TOC\o"1-5"\h\za-1a-1a-1a-11將其代入f(x)三0(modpa)由泰勒展開，得f(x)+pa-1tf'(x)三0(modpa)，a-1a-1a-1于是tf'(x)三-/""a-1)(modp)，a-1a-1pa-1,f因為x三x(modp)，所以f'(x)三f'(x)(modp),從而pJf(x)，a-11a-11a-1故上面同余式有唯一解:：三t(modp),即t=t+pt,teZ,a-1a-1a-1a-1aa代入x=x+pa-1t得f(x)三0(modpa-1)的一解：a-1a-1fx=x+pa-1(t+pt)=x+pat,teZ,其中x三x(modp)。a-1a-1aaaaa1因此，結論普遍成立。

例2解同余式f(x)=x