同余簡化剩余系

初等數(shù)論(16)(第二章同余第七節(jié)簡化剩余系(2))一、復(fù)習(xí)二、例題例2什么樣的正整數(shù)滿足:(2x)=(3x)解設(shè)x=2a3by,其中ab為非負整數(shù)，6|y。若b>0,(a、b大于或等于0)則平(2x)=中(2a+1)平(3b)中(y)=2aX3b,x(3”(y)■:(3x)=:(2a)■:(3b+1):(y)=2aJX3bx(3-1);(y)這時中(2x)和中(3x)不會相等。所以在中(2x)=5(3x)時，b=0,x=2ayo這時，平(2x)=2aX中(y),中(3x)=2X中(2a)x邛(y)由中(2x)=5(3x)得:(2a)=2a,，(a>0)故x=2ay,a為正整數(shù)，61yo例如x=215X35,則中(2X215X35)=215X<P(35)^(3X215X35)=(3—1)X214X中(35)TOC\o"1-5"\h\z1.例3證明：邛(n)=-n不可能成立。4，一、1，證明若*(n)=—n,則4n。設(shè)412kn2p1p2P，其中Pi為奇質(zhì)數(shù)，a之2,則1o：-211?2...-kn=2P1P2Pk4巴0=2。、尸p尸一瞟T(r-1)…0-1)于是P1P2Pk=2(P1-1)(p2-1)(Pk-1)上式右邊為偶數(shù)，左邊為奇數(shù)，矛盾。...、1故不存在n,使得((n)=—n。4

例4設(shè)m與n是正整數(shù)，證明:邛(mn)中((m,n))=(m,n)中(m)中(n)。證明設(shè)m=p；1pkkm1,n=pjpkkn1?Pi|mvpi|nv(mvni)=1,則(mn)=(p；1?pkkkm1n1)TOC\o"1-5"\h\z__k1.rk--k1-p1pk(11、)：(m1)：(n1pi7n))=1、)：(m1)：(n1pi7n))=(p；in{21}min{)k」k}、pk)k=(m,n)［【(1i11pi），由此得(mn)((m,n))=(m,n)--kpjpk'l(1--)(m1)i=1pip11pk(1--)：(n1)i=1pi=(m,n):(m):(n)例5設(shè)nwn,證明：（i）若n是奇數(shù)，則中（4n）=2中（n）;證明我們有（4,n）=1中(4n)=平(22n)=cp(22)cp(n)=2中(n);例如n=5,則有中(4n)=邛(22)中(5)=2X4=8,模20的簡化剩余系中有8個元素1,3,7,9,11,13,17,19(ii)中(n)=1n的充要條件是n=2k，依N;證明若n=2k,則邛(2k)=2k(1-1)=2kJL=1n,若中(n)=ln,設(shè)n=2kni,21ni,則由1nm2nLLn=(n)=(2kni)=(2k)(n1nm2nL=2k,(nL)=L2knL-(n1)2nL推出中(ni)=ni,所以ni=i,即n=2k;1(m)5(n)=—n的充要條件是3n=2k31,k,IWN;證明若n=2k31,則^(n)^(2krP(3l)=2k(i-1)3l(i-L)4n._.i若中(n)=—n,3設(shè)n=2k3lni,6|n1，則由1n=：(n)=；(2k3lni)3=：(2k)：(3l)：(ni)iIi.=2(i-i)3(i-3)(ni)"3：(ni)ni推出中（ni）=ni,所以ni=i,即n=2k31。（若中（n1）=i,則ni=i或ni=2。）初等數(shù)論（17）（第二章同余第八節(jié)Euler定理（i））本節(jié)中所介紹的Euler定理，在理論和應(yīng)用兩個方面都是很重要的。定理1(Euler定理)設(shè)m是正整數(shù),(a,m)=1,則a*m)三i(modm)。證明由第三節(jié)定理2,設(shè)｛xi,X2,…，x(^m)｝是模m的一個簡化剩余系，則｛axnax?,…，ax(p(m)｝也是模m的簡化剩余系，因此axiax2"'ax@m)三xix2*"x吹m)(modm),!-(m)a%)xix2??*xq:(m)三xix2x犧)(modm)(1)由于(xix2…x，m),m)=i,所以m(a“m)_i)得出a^m)三i(modm)。例如(5,i2)=i,邛(i2)=4,54=252三i2=i(modi2)。例如，(7,i2)=i,中(i2)=4,74三(一5)4=(5)4三252三i2=i(modi2)。再如(5,i7)=i,邛(i7)=i6,5i6=25423三9三8i三i58三254三94三i78三494423三9三8i三i58三254三94三i78三494m由Euler定理我們可以得到對于模m的一個簡化剩余系中的任何一個整數(shù)x,都有x"m)三i(modm)例如m=i6,m的簡化剩余系為｛i,3,5,7,9,ii,8.i=ii3,i5｝,中(m)=8(modi6)(modi6)(modi6)(modi6)定理2(Fermat)設(shè)p是質(zhì)數(shù)，則對于任意的整數(shù)a,有ap三a(modp)。證明若(a,p)=i,則由定理i得到ap"三i(modp)=ap三a(modp)。若(a,p)>i,則pa,所以ap三0三a(modp)。例如取p=3,a=6,則，63三6(mod3)取p=3,a=5,則，53三23三8三5(mod3)取p=7,a=5,貝U57三(一2)7三一2X82三-2X1三5(mod7)公元前50年左右，我國已經(jīng)知道p2p_2。這是費馬小定理的特殊情形。例如525_2=3011211-2=204617217—2=131070費馬小定理的逆定理不成立，例如2341三2(mod341)但341不是質(zhì)數(shù)，我們稱這樣的合數(shù)為偽質(zhì)數(shù)。例1證明341是偽質(zhì)數(shù)。證明只要證明341是合數(shù)，且2341三2(mod341)就可以了。341=11X31。又由費馬小定理知211三2(mod11)231三2(mod31)所以有2341=(211)31三231=29X(211)2三29X22=211三2(mod11)及23"=(231)11三211=2X1024三2X1三2(mod31)即11|2341—2,312341—2,又(11,31)=1,所以341|2341-2也就是2341三2(mod341)這就證明了341是偽質(zhì)數(shù)。341是最小的偽質(zhì)數(shù)，在1000以下還有另外兩個偽質(zhì)數(shù)：561=3X11X17,645=3X5X43N=561時，對每一個與561互質(zhì)的整數(shù)a,

ap-l三1(modp)都成立。例如取a=7則7560三1560三1(mod3)7560三49280三5280e6257°36257°父703214三(-1)14封(mod11)7560三4928°三(⑵280三2280三1670三(-1)70三3214三1(mod17)即37560_1,117560-1,17|7560—1,又(3,11,17)=1,所以3X11X177560,1即7560三1(mod561)。例2證明有無窮多個偽質(zhì)數(shù)。證明若an是一個偽質(zhì)數(shù)，則an2an—2,令an書=2an—1,以下證明1、an+1是合數(shù)。2、an十112af-2則由第一章第三節(jié)例11(教材22頁)證明：當(dāng)2n_1為質(zhì)數(shù)時，n一定是質(zhì)數(shù)。知an+1是合數(shù)。因為若an+1不是質(zhì)數(shù),a_.an書=2n-1為合數(shù)，則an是質(zhì)數(shù)，與an是偽質(zhì)數(shù)相矛盾。a一又因為an2n—2,所以an十一1=2an-1一1=2an-2=kan,k亡N,從而2an(mod2047)。」一1二2kan-1;(2an)k-1=(mod2047)。被2an—1整除，即2an1-1-1=0(modan1)a-2ani.1(2(2于是an+1是偽質(zhì)數(shù)。例如341是偽質(zhì)數(shù)，an+1=2341-1是偽質(zhì)數(shù),先證明2341—1可以被2047整除，即2341三2341=(211)31(2048)31=131=1(mod2047),2341—1是合數(shù)。以下證明23412341—12：2341121-22341一1一1二2341一2;k341一341_341___22"-1=22/-1=2k341-1=(2341)k-1=(2341-1)Q2341-12341-1可以整除22一1”—1從而2341—1可以2341112(2223411-1)=22-1-2。例5求710000與79999的末三位數(shù)字。解求一個數(shù)的末三位數(shù)字，就是求這個數(shù)除以1000的余數(shù)。因為（1000）=（2353）=22524=400所以由Euler定理，7400三1(mod1000),從而，710000=7400X25三125三1(mod1000),即710000的末三位數(shù)字為0,0,1。因為7X79999=710000三1三1001(mod1000),99991001所以，7-^―1143(mod1000),即79999的末三位數(shù)字為1,4,3。Euler說明為了求79999的末三位數(shù)字，應(yīng)當(dāng)先求710000的末三位數(shù)字。因為后者借助Euler定理不難求出。初等數(shù)論（18）（第二章同余第八節(jié)Euler定理（2））一、復(fù)習(xí)二、例題例4若n之1,則工中（d）=n。d|nd時,證明考慮將整數(shù)1,2,…，n,根據(jù)它們與n的最大公約數(shù)分類，即（a,n）將a歸入Cdd時,例如n=12時，1,2,…，12被分為以下6類：Ci={1,5,7,11},C2={2,10},

C3={3,9},C4={4,8},C6={6},Ci2={12}這樣，每一個a恰好屬于一個類，因此,nC3={3,9},C4={4,8},C6={6},Ci2={12}這樣，每一個a恰好屬于一個類，因此,n=工（cd的元素的個數(shù)）。d|n由于（a,n)=d,瑞)ddd-a-…=1,而一的個數(shù)就是1,2,…，daa一中與一互質(zhì)的數(shù)的dd個數(shù)，即（Cd中的元素個數(shù)為邛（2）,從而

don="dIn當(dāng)d跑遍n的因數(shù)時,n也跑遍n的因數(shù)，所以￡中ddinn（一）=￡中（d）。因此ddin工中(d)=n成立。d|n例6設(shè)n是正整數(shù)，則511n十2n+3n+4n的充要條件是4卜。證明因為中(5)=4,所以，k4三1(mod5),1<k<4。因此，設(shè)n=4q+r,0<r<3,則1n三1r(mod5)2n三2r(mod5)3n三3r(mod5)4n三4r(mod5)1n+2n+3n+4n三1r+2r+3r+4r三1r+2r+(-2)r+(-1)r(mod5)(1)用r=0,1,2,3分別代入式(1)即可得出所需結(jié)論。r=0,1,2,3時，1r+2「+(—2)r+(—1)「=4,0,10,0,r=0時，511n+2n+3n+4n,5|1n+2n+3n+4n,r=0。即若4n,則5]>+2n+3n+'4n,若511n.2n-3n?4n,則4no例7設(shè)a,b,c,m是正整數(shù)，m>1,(b,m)=1,并且ba三1(modm),bc三1(modm),(1)記d=(a,c),貝Ubd三1(modm)。證明利用輾轉(zhuǎn)相除法可以求出整數(shù)x,y,使得ax+cy=d,顯然xy<0。若x>0,y<0,由(1)式知1三ba^a*=bdb"y=bd(bc)'三bd(modm)。若x<0,y>0,由(1)式知1三bcy=bdb-ax=bd(ba)-x三bd(modm)。(注意證明過程中的指數(shù)大于0)例如取m=15,b=19,a=10,C=12,則1912三(一4)12M66三1(mod15),1910三(一4)10三165=\(mod15),2=(10,12),192三(-4)2M62M(mod15)。例8設(shè)(a,m)=1,d0是使ad三1(modm)成立的最小正整數(shù)，則d°|邛(m)。證明由Euler定理，a*m)三1(modm),所以存在d0M中(m),使ad三1(modm)因此，由帶余數(shù)除法，有中(m)=qd0+r,q=Z,q>0,0<r<d。。因此，由上式及do的定義，利用定理1,我們得到1=a(m)=aqd0r=ar(modm)即整數(shù)r滿足ar三1(modm),0<r<do。由d0是使ad三1(modm)成立的最小正整數(shù)可知必是r=0,即d0中(m)。例如取m=17,則中(m)=1628三44三162三(T)2M(mod17)8是使2d三1(mod17)成立的最小正數(shù)，8I16=邛(m)。再如取m=19,則中(m)=1859三5X58三5X254三5X64三5X172三5X(-2)2三20M(mod19)9是使59弓(mod19)的最小整數(shù)，918=中(19)。例9設(shè)p是質(zhì)數(shù)，p|bn_1,n三N,則下面的兩個結(jié)論中至少有一個成立：(i)pbd-1對于n的某個因數(shù)d<n成立；(ii)p三1(modn)。若2|n,p>2,則(ii)中的modn可以改為mod2n。證明記d=(n,p-1),由Euler定理有bp,三1(modp),又bn三1(modp),(b,p)=1由例題6,有bd三1(modp)。若d<n,則dn,結(jié)論(i)成立。若d=n,則np_1,p三1(modn),這就是結(jié)論(ii)。若2|n,p>2,貝UpM(mod2)。又p三1(modn),利用同余的基本性質(zhì)，得到p三1(mod2n)。注：例8給出了一個求質(zhì)因數(shù)的方法，就是說，整數(shù)bn-1的質(zhì)因數(shù)p,是bd-1(當(dāng)dn時)的質(zhì)因數(shù)，或者是形如kn+1的數(shù)(當(dāng)2.|n,p>2時，是形如2kn+1的數(shù))。例如將38—1分解因數(shù)。由例5,n=8,38—1的因數(shù)是31—1,32—1,34—1的因數(shù)，或是9,17,25,33,41,……中的質(zhì)數(shù)。31-1=2,32-1=8,34-1=809,17,25,33,41