初中數(shù)學(xué)競(jìng)賽講座——數(shù)論部分費(fèi)馬小定理

1、初中數(shù)學(xué)競(jìng)賽講座 分（費(fèi)馬小定理）數(shù)論部作者:日期:第9講費(fèi)爾馬小定理-、基礎(chǔ)知識(shí)： .法國(guó)數(shù)學(xué)家費(fèi)爾馬在1640年提出了一個(gè)有關(guān)整數(shù)器余數(shù)的定理，在解決許多關(guān)于某 個(gè)整數(shù)事除以某個(gè)整數(shù)的余數(shù)問(wèn)題時(shí)非常方便有用，在介紹這個(gè)定理之前，我們先來(lái)看一 些具體的同余式，請(qǐng)同學(xué)們注意觀察，發(fā)現(xiàn)這些同余式符合什么規(guī)律.3=1 (mod 2), 5三 1 (mod 2), 7=1 (mod 2).22=i (mod 3), 411 (mod 3), 5-1 (mod 3).24sl (mod 5), 34sl (mod 5), 44sl (mod 5).26s (23) 2sl (mod 7), 3(33)

2、 ?三 1 (mod 7), 4(43)(mod 7).這些同余式都符合同一個(gè)規(guī)律，這個(gè)規(guī)律就是費(fèi)爾馬小定理.費(fèi)爾馬小定理:如果是質(zhì)數(shù)，(a, p) =1,那么"(mod p)與費(fèi)馬小定理相關(guān)的有一個(gè)中國(guó)猜想，這個(gè)猜想是中國(guó)數(shù)學(xué)家提出來(lái)的，其內(nèi) 容為:當(dāng)且僅當(dāng)2Pl(mod p), 是一個(gè)質(zhì)數(shù)。假如是一個(gè)質(zhì)數(shù)的話，則2。-展l(mod p)成立(這是費(fèi)馬小定理的一個(gè)特殊情 況)是對(duì)的。但反過(guò)來(lái)，假如2肌展l(mod p)成立那么是一個(gè)質(zhì)數(shù)是不成立的(比 如341符合上述條件但不是一個(gè)質(zhì)數(shù))。如上所述，中國(guó)猜測(cè)只有一半是正確的，符合中國(guó)猜測(cè)但不是質(zhì)數(shù)的數(shù)被稱為 “偽質(zhì)數(shù)”。對(duì)于中國(guó)猜測(cè)

3、稍作改動(dòng)，即得到判斷一個(gè)數(shù)是否為質(zhì)數(shù)的一個(gè)方法：如果對(duì)于任意滿足1 < b < p的b下式都成立：/ '-l(mod p),則p必定是 一個(gè)質(zhì)數(shù)。實(shí)際上，沒(méi)有必要測(cè)試所有的小于的自然數(shù)，只要測(cè)試所有的小于的質(zhì)數(shù) 就可以了。這個(gè)算法的缺點(diǎn)是它非常慢，運(yùn)算率高：但是它很適合在計(jì)算機(jī)上而運(yùn)行程序 進(jìn)行驗(yàn)算一個(gè)數(shù)是否是質(zhì)數(shù)。(一)準(zhǔn)備知識(shí)：引理1.若“ec為任意3個(gè)整數(shù)，機(jī)為正整數(shù)，且則當(dāng)“ybc(mod?) 時(shí)，有(t=b(mod/n)證明：cM-c(mod m)可得 ac-by0(mod可得(a-)c三0(mod ?)因?yàn)??,()= 1 即機(jī),c互質(zhì)，c可以約去，-三O(n】

4、od ?)可得“三(mod m)引理2.若一為整數(shù)且m> 1,« 1 M2,a3M4,-am為，個(gè)整數(shù)，若在這m個(gè)數(shù)中任取 2個(gè)整數(shù)對(duì)m不同余，則這個(gè)整數(shù)對(duì)，構(gòu)成完全剩余系。證明：構(gòu)造，的完全剩余系(0,1,2,川-1),所有的整數(shù)必然是這些整數(shù)中的 1 個(gè)對(duì)模 m 同余。取 /*=0,2=1/3=2,4=3,r尸i-lJviW/n。令(1)： 產(chǎn)門(mén)(mod m),ci2=r2(mod m). .<zWI=/WI(niod j)(順序可以不同)，因?yàn)橹挥性谶@ 種情況下才能保證集合2M3«4,”局中的任意2個(gè)數(shù)不同余，否則必然有2個(gè)數(shù) 同余。由式(1)自然得到集合

5、("1M2M3M4,對(duì)，構(gòu)成完全剩余系。引理3.設(shè)小是一個(gè)整數(shù),且,b是一個(gè)整數(shù)且(TH力)=1 .如果"IM2M33. 11m是模，的一個(gè)完全剩余系，則ba,bci2,ba3.ba4,.bam也構(gòu)成模m的一個(gè)完全剩余 系。證明：若存在2個(gè)整數(shù)而和同余即加尸(mod m),根據(jù)引理1則有“產(chǎn)句(mod。根據(jù)完全剩余系的定義可知這是不可能的,因 此不存在2個(gè)整數(shù)ba,和同余。由引理2可知bai,ba2,ba3,ba4t.bam構(gòu)成模m的 一個(gè)完全剩余系。引理4.如果“力,c,"是四個(gè)整數(shù),且三(mod zn),csJ(mod ?),貝ij有。三d(mod證明:由題設(shè)

6、得ac=bcmod m),bc=bd(mod m),由模運(yùn)算的傳遞性可得ac=bc(m od m)(二)證明過(guò)程：構(gòu)造素?cái)?shù)p的完全剩余系P=l,2,3,4.(/7-l),因?yàn)?“,p)=l,由引理3可得A=(“, 2/3,4凡。-1)”也是p的一個(gè)完全剩余系。令W=l*2*3*4.*(p-1),顯然用W(mo d p). 令 y=a*2“*3“*4“*(p-l)a,因?yàn)椤?2a,3“,4a,S-l)“是 p 的完全剩余系,由引 理 2 以及引理 4 可得 “*2a*3"*p)即 1收產(chǎn)展卬(modp)。 易知(W.p)= 1.由引理1可知ap-=l(modp) 二、典型例題：例1設(shè)為

7、正整數(shù).證明：7產(chǎn)+/的充要條件是彳3"/+1.證明若7,'+3,則71/1,于是，由Am?，小定理，知= l(n»d 7), 從而，由知彳(3"+3)3,故彳3W+1.反過(guò)來(lái)，若彳3"3+1,則7IH,并且7|(3”/ + 1)./,即7.6+3,n ' = l(mod 7), 73”+/J.命題獲證。說(shuō)明 涉及指數(shù)的同余式經(jīng)常需要用到戶6/7.小定理，因?yàn)橛墒?根小定理得出的結(jié) 論中，同余式的一邊是1,這帶來(lái)很大的方便.例2由尸小定理知，對(duì)任意奇質(zhì)數(shù)p ,都有三l(mod ).問(wèn)：是否存在合數(shù)， 使得2"7三l(mod)成立

8、?解 這樣的合數(shù)存在，而且有無(wú)窮多個(gè).其中最小的滿足條件的合數(shù) = 341 = 11x31 (它是從兩個(gè)不同奇質(zhì)數(shù)作乘積去試算出來(lái)的).事實(shí)上，由于= l 023 = 341x3,故21° 三 l(mod341),所以2540三產(chǎn)三l(mod341),故341符合要求.進(jìn)一步，設(shè)“是一個(gè)符合要求的奇合數(shù)，則2"-1是一個(gè)奇合數(shù)(這一點(diǎn)利用四式分解可知)。再設(shè)2Ml = 4xq,q為正奇數(shù)，則22"= 22(產(chǎn)”1= 2-1=(2。產(chǎn)-1三產(chǎn)一 1三 0(mod V -1).因此2-1也是一個(gè)符合要求的數(shù),依此類推(結(jié)合341符合要求)，可知有無(wú)窮多個(gè)滿足 條件的合

9、數(shù).說(shuō)明 滿足題中的合數(shù)稱為“偽質(zhì)數(shù)”，如果對(duì)任意(,)=1都有"I三l(nx)d ) 成立，那么合數(shù)稱為“絕對(duì)偽質(zhì)數(shù)工請(qǐng)讀者尋找“絕對(duì)偽質(zhì)數(shù)'二例3設(shè)為質(zhì)數(shù).證明：存在無(wú)窮多個(gè)正整數(shù)，使得證明 如果 =2,那么取為偶數(shù)，就有命題成立.設(shè) > 2 ,則由Fem小定理知三 l(nnd /?).因此，對(duì)任意正整數(shù)k,都有三 l(n»d p),所以，只需證明存在無(wú)窮多個(gè)正整數(shù)攵，使得Zr(/?-l) = 1(mod/?)(這樣，令 =k(- 1),就有2"而這只需攵三l(mod),這樣的攵當(dāng)然有無(wú)窮多個(gè).所以，命題成立.說(shuō)明 用尸口7小小定理處理數(shù)論中的一

10、些存在性問(wèn)題有時(shí)非常方便、簡(jiǎn)潔. 例4設(shè)工為整數(shù)，是V+1的奇質(zhì)因子，證明：p = l(mod4). -=、 證明 由于,p為奇質(zhì)數(shù)，若三/ l(mod4),則p = 3(mod4)，可設(shè)p = 4% + 3 ,此時(shí)， 由= -l(mod ),得-7 =/+2 =(/產(chǎn)+1 三(T產(chǎn)+1 三 _(gd p)而由FC777"小定理，應(yīng)有= l(nx)d p),結(jié)合上式將導(dǎo)出目2矛盾.所以，p = l(mod4).說(shuō)明 利用此題的結(jié)論，我們可以證明：存在無(wú)窮多個(gè)模4余1的正整數(shù)為質(zhì)數(shù).事實(shí)上，若只有有限個(gè)質(zhì)數(shù)模4余1,設(shè)它們是P1,2,P,考慮數(shù) (21%P”f+l的質(zhì)因子即可導(dǎo)出矛盾.

11、例5求所有的質(zhì)數(shù)p,使得是一個(gè)完全平方數(shù).P解 設(shè)是一個(gè)滿足條件的質(zhì)數(shù)，則顯然是一個(gè)奇質(zhì)數(shù),由尸em小定理知p-p-i而 2P-1-1 = (2亍-1)(2亍+1), p-ip-i故2丁-1 或 p2 亍 +1.p-i p-ip-i由于(2 一 1,2= +1) = (2 - 1,2) = 1,p-ip-i所以，p2 2 一1與p2? +1中恰有一個(gè)成立.p-ip-i p-i若2k-1,則由條件及(2-1,2+1) = 1可知存在正整數(shù)x ,使得P-12 +1=/,此時(shí) (x1)(x+1) = 29所以，x 1與x + 1都是2的冥次，而X為奇數(shù)，故x 1與x+1是兩個(gè)相繼的偶數(shù)，所 以，只能

12、是x 1 = 2, x +1 + 4,故 x = 3,此時(shí) p = 7.p-i若 2h+ 1,則同上知存在正整數(shù)X,使得p-i丁1 = /,當(dāng) >3時(shí)，導(dǎo)致p-ix2 =2丁-1 三-l(mod 4), 矛盾，故 =3.另一方面，當(dāng) =3 .和7時(shí)，-分別為1和9,都是完全平方數(shù). P綜上可知 =3或7.例6.求14589+32項(xiàng)除以13的余數(shù).解:因 13 是質(zhì)數(shù),且(145, 13) =1, (3, 13) =1由費(fèi)爾馬小定理得:145|2=1 (mod 89), 312= (mod 89).145(145十)7.145145$ (mod 13)32002三(3i2)i66.3iM,

13、0 (mod 13)又T45三2 (mod 13), 31 (mod 13)A 145MM (mod 13), 310 (33) 33=3 (mod 13)所以，145%3加2三6+3三9 (mod 13),即145啊32皿除以13的余數(shù)是9.例7.設(shè)是質(zhì)數(shù)，且后2.求證：產(chǎn)+2P+3。+.+ (p-l) M) (modp)證明：由于是質(zhì)數(shù)且后2,所以對(duì)任意正整數(shù)<p，都有(，)=1,根據(jù)費(fèi)爾馬小定理得，np !=1 (modp),于是，/三(mod”)(=1, 2, 3,p )因此，1,+2P+3,+ (p-1) 三 1+2+3+.+ (p-1) (modp)三(二"-(mo

14、dp)2由于P是不等于2的質(zhì)數(shù)，所以匕1是整數(shù).2故如_!2=o (mod”)，所以 P+2p+.+ (p 1)，三0 (mod/?)2說(shuō)明：費(fèi)爾馬小定理也可以寫(xiě)成另外一種形式：如果是質(zhì)數(shù)，對(duì)任意正整數(shù)”，都有 dj (mod/?)»這是因?yàn)楫?dāng)0W時(shí),(p,。)=1,有是一 (modp)故al (modp)；當(dāng) P I 時(shí)，顯然有 p，一a,即(mod p).費(fèi)爾馬小定理的逆定理不成立，也就是說(shuō)，當(dāng)QW (modp)時(shí)，不一定是質(zhì)數(shù)， 例如5'三1 (mod 4),且(5, 4) =1,但4不是質(zhì)數(shù).例8.求證:對(duì)任意整數(shù)小兒而(小一)都能被30整除.分析:因?yàn)?30=2x3

15、x5,所以只需證明 21ab(a4-6*), 3 I ah(a4-b4), 5 I ab(a4b4)9 因?yàn)?2,3, 5都是質(zhì)數(shù)，所以可以考慮用費(fèi)爾馬小定理.證明：因?yàn)?0=2x3x5,所以只需證明2, 3, 5都能整除"("一)即可，因2是質(zhì)數(shù)，根據(jù)費(fèi)爾馬小定理得，(mod 2), bb (mod 2),所以(t/2) 2=a2=a (mod 2), b4= (/P) H (mod 2)ab(a4-b4)=ab (a-b) rhah2=aba 10 (mod 2), RP 2 I ab(a4b4).又因?yàn)?也是質(zhì)數(shù)，根據(jù)費(fèi)爾馬小定理得/A (mod 3), bb (mo

16、d 3)/. ab(n4 b4)=ab(a2 - />2)(niod 3)<z3/? - ah3(mod 3)=ahab (mod 3) =04mod 3),即 31""-)例9.證明：對(duì)任意自然數(shù)>1, 2- 1都不能被整除證明：若為偶數(shù)，2一 1必是奇數(shù)，貝N 12- 1若為奇數(shù)，且">1,假設(shè) 12-1設(shè)P為”的最小質(zhì)因數(shù)，則2“三1 (modp),再設(shè)是滿足2(modp)的最小正整數(shù)，即 2,三 1 (modp),若xjx,可設(shè)4、r+q, OVgO,那么22rM三(29北24三2'餐1 (modp)這與，的最小性矛盾，因此

17、rlx,又因2"三1 (modp),所以川.根據(jù)費(fèi)爾馬小定理得2廠展1 (modp),因此rlp-1由川，/"I”一 1知r是的小于的正約數(shù)，故=1,得 I 21,即11,矛盾，假 設(shè)不成立，即 12- 1,綜上所述，對(duì)任意自然數(shù)>1, 2- 1都不能被整除.三、模擬訓(xùn)練：1求出258儂除以7的余數(shù)是多少。解：由于25與7互質(zhì)，由費(fèi)馬小定理可知對(duì)模7而言，251 (mod 7)所以 25800256xI333+(256)1333x252曰2 (mod 7)故余數(shù)為22 .假設(shè)為任意一個(gè)大于5的質(zhì)數(shù)，試證：必可整除即=J_匕0證明：由于和10互質(zhì)且9p=l(F,由費(fèi)馬小

18、定理可知對(duì)模而言，1尸三1 (modp) 因此，一定能整除9町，又由于和9互質(zhì)，因此p一定能整除他3 .假設(shè)=3-2是一個(gè)質(zhì)數(shù)，試證：如果p可整除十"+卜3和一都是整數(shù)),那么又和占 必定都是的倍數(shù)。證明：由可整除a2+ab+b2f p必定也能整除(a-)32+R?+2)=aL/r'，因此蘇三 (modp)左右兩邊同時(shí)取k次方，得(產(chǎn)三戶(modp) (1)假設(shè)不能整除小 那么必定也不能整除岳由費(fèi)馬小定理可知對(duì)模而言，(產(chǎn)】三"/三1( mod p)將p=3k+2 代入上式得：a3M=b3M=l (modp) (2)綜合(1) (2)可知 a=b=l (mod/?)

19、因此(尸+(“用)*3+(尸+("3(尸(mod p)所以3、是的倍數(shù)，又3和互質(zhì)，可知"一定是的倍數(shù)，這與假設(shè)不能整除 “矛盾，因此"和b必定都是p的倍數(shù)。四、【延伸閱讀】(1)形如我+1的質(zhì)數(shù)個(gè)數(shù)有無(wú)數(shù)個(gè)。假設(shè)是任意一個(gè)大于1的正整數(shù)：加顯然為偶數(shù),因此(川A+l為奇數(shù),而(加廣+1 的每個(gè)質(zhì)因子都可表示為軟+1或4hl的形式。假設(shè)=4hl是(用戶+1的一個(gè)質(zhì)因子(可知.和川互質(zhì)),由于(!)2三一1 (modp)將左右兩邊同時(shí)取牛次方，制川尸三卜1尸(modp)由于寫(xiě)*=24-1為奇數(shù)，因此(川產(chǎn)三(-1) (mod/?)但這與費(fèi)馬小定理矛盾，因此根據(jù)費(fèi)馬小

20、定理，由于和，!互質(zhì)，(nA必定會(huì)和1對(duì)模 P同余。由此我們推知5!)41不可能有形如4hl的質(zhì)因子，也就是(加尸+1只有形如軟+1的質(zhì) 因子。又由于(加戶+1的每個(gè)質(zhì)因子顯然都大于明因此我們就證明了：不管是多少，一 定有比/?大而且形如軟+1的質(zhì)數(shù)存在，這就說(shuō)明了等差數(shù)列159,13,中包含無(wú)窮多個(gè) 質(zhì)數(shù)。(2)費(fèi)馬小定理的逆定理當(dāng)p為質(zhì)數(shù)，由費(fèi)馬小定理我們知道20-2必定是p的倍數(shù)(即前面的討論中當(dāng)”=2 的情形)；反過(guò)來(lái)成不成立呢？也就是說(shuō)，如果有某個(gè)正整數(shù)可以整除2-2,我們能不 能斷定/? 一定是質(zhì)數(shù)呢？如果可以的話，這將是個(gè)不錯(cuò)的判斷任意整數(shù)是否為質(zhì)數(shù)的方 法：歷史上確實(shí)曾經(jīng)有一段

21、時(shí)期數(shù)學(xué)家們猜測(cè)這個(gè)方法可行，不過(guò)法國(guó)數(shù)學(xué)家Pierre Sanus 于1819年指出n=341是一個(gè)反例：341是11與13的積，因此不是質(zhì)數(shù)，但是由234,-2=2(2,0)J4-134=2(2i<,-1)(.)=2(1023)(.)=2(3X341)(.) 可知341能整除2刈-2.對(duì)任意正整數(shù)”，如果有某個(gè)大于1的正整數(shù)本身不是質(zhì)數(shù)卻能整除/-“，我們稱 對(duì)底數(shù)”而言是一個(gè)偽質(zhì)數(shù)(英文常稱作加e),因此對(duì)底數(shù)2而言，341是 一個(gè)偽質(zhì)數(shù)(即341是一個(gè)2-pseudoprime)。幾個(gè)衍生出來(lái)的問(wèn)題是：341是唯一的加e嗎？除了奇數(shù)的偽質(zhì)數(shù)外，是否 還存在著偶偽質(zhì)數(shù)?對(duì)任意正整數(shù)

22、小“-pse加”加e的個(gè)數(shù)是有限還是無(wú)限？對(duì)底數(shù)2而言，如果是一個(gè)奇?zhèn)钨|(zhì)數(shù)，我們不難證明2"-1將是另一個(gè)更大的奇?zhèn)钨|(zhì) 數(shù)：既然我們已知奇?zhèn)钨|(zhì)數(shù)341的存在，對(duì)底數(shù)2來(lái)說(shuō)奇?zhèn)钨|(zhì)數(shù)的個(gè)數(shù)因此是無(wú)窮的，尋 找偶偽質(zhì)數(shù)(對(duì)底數(shù)2而言)的工作比尋找奇?zhèn)钨|(zhì)數(shù)要困難許多，其中最小的數(shù)直到1950 年才由美國(guó)數(shù)學(xué)家D.H.Le/”ner找到,其值為161038=2x數(shù)x 1103.由于2,6,038-2 = 2 (2,6,037-1 )要說(shuō)明161038可以整除2。38_2,我們只要說(shuō)明73和1103 (皆為質(zhì)數(shù))都能 整除2。37即可。由戈161034可經(jīng)質(zhì)因數(shù)分解為32x29x617,因此2037/=2 (29) 29 6，1 乃 617=(21) (.) = (511)