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

第9講費(fèi)爾馬小定理一、基礎(chǔ)知識(shí)：法國數(shù)學(xué)家費(fèi)爾馬在１640年提出了一個(gè)有關(guān)整數(shù)冪余數(shù)的定理，在解決許多關(guān)于某個(gè)整數(shù)冪除以某個(gè)整數(shù)的余數(shù)問題時(shí)非常方便有用,在介紹這個(gè)定理之前,我們先來看一些具體的同余式，請(qǐng)同學(xué)們注意觀測(cè)，發(fā)現(xiàn)這些同余式符合什么規(guī)律．3≡1（mod２),5≡1（mｏd2)，７≡1（moｄ2)…2２≡１(ｍod3)，４２≡１(mod3),５2≡１(moｄ3)…24≡1（mod5)，34≡１(ｍod5)，4４≡1（mod5)…26≡(23）2≡1(mod７），３6≡(3３)2≡1(mod７)，４6≡（43)2≡１(moｄ7)…這些同余式都符協(xié)議一個(gè)規(guī)律,這個(gè)規(guī)律就是費(fèi)爾馬小定理.費(fèi)爾馬小定理：假如p是質(zhì)數(shù),（ａ,p）=１,那么ａp－1≡1(moｄp)與費(fèi)馬小定理相關(guān)的有一個(gè)中國猜想，這個(gè)猜想是中國數(shù)學(xué)家提出來的，其內(nèi)容為:當(dāng)且僅當(dāng)2p-１≡1（mｏdp)，p是一個(gè)質(zhì)數(shù)。假如p是一個(gè)質(zhì)數(shù)的話，則2p－１≡1(ｍｏdp）成立(這是費(fèi)馬小定理的一個(gè)特殊情況)是對(duì)的。但反過來,假如２p-1≡1(ｍｏdp)成立那么ｐ是一個(gè)質(zhì)數(shù)是不成立的（比如3４1符合上述條件但不是一個(gè)質(zhì)數(shù))。如上所述，中國猜測(cè)只有一半是對(duì)的的，符合中國猜測(cè)但不是質(zhì)數(shù)的數(shù)被稱為“偽質(zhì)數(shù)”。對(duì)于中國猜測(cè)稍作改動(dòng),即得到判斷一個(gè)數(shù)是否為質(zhì)數(shù)的一個(gè)方法:假如對(duì)于任意滿足1＜ｂ<p的ｂ下式都成立：ｂｐ-1≡1（ｍodｐ),則p必然是一個(gè)質(zhì)數(shù)。事實(shí)上，沒有必要測(cè)試所有的小于ｐ的自然數(shù)，只要測(cè)試所有的小于p的質(zhì)數(shù)就可以了。這個(gè)算法的缺陷是它非常慢,運(yùn)算率高；但是它很適合在計(jì)算機(jī)上面運(yùn)營程序進(jìn)行驗(yàn)算一個(gè)數(shù)是否是質(zhì)數(shù)。(一）準(zhǔn)備知識(shí):引理１.若a，ｂ,c為任意3個(gè)整數(shù)，ｍ為正整數(shù)，且(m,c)＝1,則當(dāng)ac≡bc（moｄm)時(shí),有ａ≡b(mｏdm)證明：aｃ≡ｂc(moｄm）可得ａc–bｃ≡０(modm）可得（ａ-b)ｃ≡0（modm)由于(m，ｃ)=1即m,c互質(zhì)，ｃ可以約去,a–b≡0(moｄm)可得a≡b(ｍodm)引理2．若m為整數(shù)且m>１，a1,a2,a3,a4，…ａm為m個(gè)整數(shù)，若在這m個(gè)數(shù)中任取2個(gè)整數(shù)對(duì)m不同余,則這m個(gè)整數(shù)對(duì)m構(gòu)成完全剩余系。證明：構(gòu)造m的完全剩余系（0，1,2,…m-１）,所有的整數(shù)必然是這些整數(shù)中的1個(gè)對(duì)模m同余。取r1=0,r２=1,r3=2,r4=3,…rｉ=ｉ-１,1<ｉ≤m。令(1):a１≡r1(modｍ)，a2≡r２(modｍ）,…am≡rm（ｍｏｄｍ）(順序可以不同)，由于只有在這種情況下才干保證集合{a1，a2,a3,ａ4，…am｝中的任意2個(gè)數(shù)不同余,否則必然有2個(gè)數(shù)同余。由式(1)自然得到集合{a１,a2,a3,ａ4,…am｝對(duì)m構(gòu)成完全剩余系。引理3．設(shè)ｍ是一個(gè)整數(shù),且m＞1,b是一個(gè)整數(shù)且（ｍ,b）=１。假如ａ1,a２,a3,a4,…aｍ是模m的一個(gè)完全剩余系,則ba1,bａ2,ba3，ｂa4,…bam也構(gòu)成模m的一個(gè)完全剩余系。證明:若存在2個(gè)整數(shù)bai和ｂaj同余即ｂａi≡ｂaj(mｏdm),根據(jù)引理1則有ai≡aj(modｍ)。根據(jù)完全剩余系的定義可知這是不也許的,因此不存在2個(gè)整數(shù)bａi和ｂａj同余。由引理2可知ba1，ｂa２,ba３,ba4,…bａm構(gòu)成模m的一個(gè)完全剩余系。引理4．假如a,b，c,d是四個(gè)整數(shù)，且a≡b(moｄm)，c≡ｄ（ｍｏｄm）,則有ａｃ≡bd（mｏdm）證明：由題設(shè)得ａc≡bc(modm),bc≡bｄ(ｍodm)，由模運(yùn)算的傳遞性可得aｃ≡bc(moｄm)(二)證明過程:構(gòu)造素?cái)?shù)p的完全剩余系P＝{1,2，3,4…（p-1）}，由于(a,p)=1，由引理3可得A=｛a,2a，3a,４ａ,…(p-1）ａ}也是ｐ的一個(gè)完全剩余系。令W=1*2*３＊4…*(p－1)，顯然Ｗ≡W(modｐ)。令Y=ａ*2ａ*３ａ*４ａ＊…(ｐ－１)ａ,由于{a,2a,3a,4a，…(p-1)ａ｝是p的完全剩余系,由引理２以及引理4可得a*２ａ*3a＊…(p-1）a≡１＊2＊3*…(p-1）（modp)即W＊ap－1≡W（ｍodp)。易知(二、典型例題:例1設(shè)為正整數(shù).證明:的充要條件是.證明若，則｜,于是,由Feｒｍat小定理,知從而，由,知,故反過來，若則|,并且,即，運(yùn)用小定理知故命題獲證。說明涉及指數(shù)的同余式經(jīng)常需要用到小定理,由于由小定理得出的結(jié)論中,同余式的一邊是,這帶來很大的方便.由小定理知,對(duì)任意奇質(zhì)數(shù),都有問:是否存在合數(shù)，使得成立？解這樣的合數(shù)存在,并且有無窮多個(gè).其中最小的滿足條件的合數(shù)(它是從兩個(gè)不同奇質(zhì)數(shù)作乘積去試算出來的)．事實(shí)上，由于故所以故３41符合規(guī)定.進(jìn)一步，設(shè)是一個(gè)符合規(guī)定的奇合數(shù)，則是一個(gè)奇合數(shù)(這一點(diǎn)運(yùn)用因式分解可知）。再設(shè)為正奇數(shù)，則因此也是一個(gè)符合規(guī)定的數(shù)．依此類推（結(jié)合符合規(guī)定）,可知有無窮多個(gè)滿足條件的合數(shù)．說明滿足題中的合數(shù)稱為“偽質(zhì)數(shù)”,假如對(duì)任意都有成立,那么合數(shù)稱為“絕對(duì)偽質(zhì)數(shù)”.請(qǐng)讀者尋找“絕對(duì)偽質(zhì)數(shù)”.設(shè)為質(zhì)數(shù).證明:存在無窮多個(gè)正整數(shù)，使得.證明假如,那么取為偶數(shù),就有，命題成立.設(shè),則由Ｆeｒmat小定理知因此，對(duì)任意正整數(shù)，都有所以,只需證明存在無窮多個(gè)正整數(shù)，使得(這樣，令就有.而這只需這樣的當(dāng)然有無窮多個(gè).所以，命題成立．說明用Ferｍａt(yī)小定理解決數(shù)論中的一些存在性問題有時(shí)非常方便、簡潔.設(shè)為整數(shù),是的奇質(zhì)因子，證明:證明由于為奇質(zhì)數(shù)，若≡／則，可設(shè)，此時(shí)，由得而由小定理，應(yīng)有結(jié)合上式將導(dǎo)出．矛盾.所以，說明運(yùn)用此題的結(jié)論，我們可以證明:存在無窮多個(gè)模余的正整數(shù)為質(zhì)數(shù)．事實(shí)上，若只有有限個(gè)質(zhì)數(shù)模余，設(shè)它們是.考慮數(shù)的質(zhì)因子即可導(dǎo)出矛盾.求所有的質(zhì)數(shù),使得是一個(gè)完全平方數(shù).解設(shè)是一個(gè)滿足條件的質(zhì)數(shù),則顯然是一個(gè)奇質(zhì)數(shù)．由小定理知,而故或由于所以，與中恰有一個(gè)成立.若,則由條件及可知存在正整數(shù)，使得,此時(shí)所以,與都是的冥次,而為奇數(shù),故與是兩個(gè)相繼的偶數(shù),所以,只能是故，此時(shí)若，則同上知存在正整數(shù)，使得當(dāng)時(shí),導(dǎo)致矛盾，故另一方面，當(dāng)和時(shí)，分別為和，都是完全平方數(shù)．綜上可知或.?例6.求14589+32023除以13的余數(shù)．解:因1３是質(zhì)數(shù),且（14５，13)=1，(3，1３）=１由費(fèi)爾馬小定理得：145１2≡１(mod89）,312≡(moｄ89）∴1４5８9≡（1451２）7·１455≡1455(ｍod13）３202３≡(３12）1６6·310≡310（ｍod13)又∵14５≡2(mod13）,3３≡１（mod1３）∴1４５5≡25≡6(mｏd１3),310≡(33)３３≡3（moｄ１3)所以，14589＋３2０2３≡6＋３≡9（ｍod１３），即14589+32０2３除以13的余數(shù)是９．例7．設(shè)ｐ是質(zhì)數(shù),且p≠2.求證：1p+2p+３p＋…＋(p－1)p≡0(ｍodp)證明:由于ｐ是質(zhì)數(shù)且ｐ≠2,所以對(duì)任意正整數(shù)ｎ＜p，都有（n,p)=1,根據(jù)費(fèi)爾馬小定理得，np-1≡１(ｍodｐ),于是np≡n（moｄp）(n=１，２,3,…，p－１）因此，１ｐ+２p＋3p+…＋(p-1）p≡１+2+３+…+（ｐ－1）（mｏdp）≡由于p是不等于2的質(zhì)數(shù)，所以是整數(shù).故≡0(mｏdp），所以1p+2ｐ+…＋（p－1)p≡0（moｄp)說明：①費(fèi)爾馬小定理也可以寫成此外一種形式：假如

p是質(zhì)數(shù),對(duì)任意正整數(shù)a，都有ａp≡a（modp),這是由于當(dāng)p|a時(shí)，(p，a）＝1，有ap-1≡1（ｍｏdp）故ａp≡a（mｏdｐ）；當(dāng)p|a時(shí),顯然有p|ap-ａ,即ap≡a(moｄp）．②費(fèi)爾馬小定理的逆定理不成立，也就是說，當(dāng)ａｐ－１≡1（mｏｄp)時(shí),p不一定是質(zhì)數(shù),例如５3≡１(mod４)，且(5，4）=１,但4不是質(zhì)數(shù).例8．求證：對(duì)任意整數(shù)ａ,b,aｂ（a4－b4)都能被3０整除.分析:由于３０=2×3×５，所以只需證明2|ａb(a4-ｂ4),3|aｂ(a4-b４),5|ab(ａ4－b４)，由于2，３,５都是質(zhì)數(shù),所以可以考慮用費(fèi)爾馬小定理．證明:由于30=２×３×5,所以只需證明2，3,5都能整除ａｂ(a4-b4）即可,因2是質(zhì)數(shù)，根據(jù)費(fèi)爾馬小定理得，a2≡a(mod２），ｂ2≡b(moｄ2),所以ａ4≡(a2)２≡a2≡a(ｍoｄ2)，b４≡(b2）2≡b2≡b(mｏd2）∴aｂ(a４－b4)≡aｂ(a－b)≡ａ２b－aｂ2≡ab－aｂ≡０（mod2）,即2|ab(a4-b４）．又由于3也是質(zhì)數(shù)，根據(jù)費(fèi)爾馬小定理得a３≡a(moｄ3),b3≡b(mｏd3)∴aｂ(ａ4-b４）≡aｂ（a2-ｂ2)(mod3)≡a3b-ab3(ｍod3)≡ab－ab(moｄ3)≡0(mod3），即3|aｂ(a4－b４）．例9．證明：對(duì)任意自然數(shù)n＞1，2n-1都不能被ｎ整除證明:若ｎ為偶數(shù),２n-1必是奇數(shù)，則n|2n-1若ｎ為奇數(shù)，且n＞1，假設(shè)ｎ|２n－1設(shè)p為n的最小質(zhì)因數(shù),則2n≡1(modp),再設(shè)r是滿足2x≡１（modｐ）的最小正整數(shù),即２r≡1（modp）,若ｒ|x，可設(shè)x=kｒ＋ｑ,0＜q＜r，那么2x≡2ｋr+q≡（2r）k·２ｑ≡2ｑ≡1（ｍｏｄp)這與ｒ的最小性矛盾，因此ｒ|x，又因2n≡1（ｍodp)，所以r｜ｎ．根據(jù)費(fèi)爾馬小定理得2ｐ－１≡1（ｍoｄp)，因此ｒ｜p-1由r|ｎ，r|ｐ－1知r是n的小于ｐ的正約數(shù)，故r=1，得p|2－1，即ｐ｜1，矛盾,假設(shè)不成立,即n|２n-1,綜上所述,對(duì)任意自然數(shù)ｎ>1,2n-1都不能被n整除.三、模擬訓(xùn)練：１．求出25８000除以7的余數(shù)是多少。解:由于25與７互質(zhì),由費(fèi)馬小定理可知對(duì)模７而言，256≡1(mod7)所以２5８０0０≡25６×１333+２≡（2５6）１３3３×252≡４２≡2（ｍod7）故余數(shù)為22．假設(shè)p為任意一個(gè)大于5的質(zhì)數(shù),試證：ｐ必可整除np＝證明:由于p和1０互質(zhì)且9ｎp=10p-1-1，由費(fèi)馬小定理可知對(duì)模ｐ而言，１0p-1≡１（modp)因此,p一定能整除9np，又由于ｐ和9互質(zhì),因此ｐ一定能整除ｎp3.假設(shè)p=3k＋2是一個(gè)質(zhì)數(shù)，試證：假如ｐ可整除a２＋ab+b2(ａ和b都是整數(shù))，那么a和b必然都是p的倍數(shù)。證明：由p可整除a2+ab+b2，ｐ必然也能整除(a-b)(ａ２+ab＋b2)=ａ３-b3,因此a3≡b3(moｄp)左右兩邊同時(shí)?。氪畏?得a3ｋ≡b3k（ｍｏdp）(1)假設(shè)p不能整除a,那么ｐ必然也不能整除ｂ：由費(fèi)馬小定理可知對(duì)模p而言,aｐ-1≡bｐ-１≡1（modp)將p=3k+２代入上式得:a3ｋ+１≡ｂ3k＋1≡1(ｍodp）（２)綜合（1）（2)可知a≡b≡１（mｏdp）因此a２＋ab+ｂ2≡a2+a2+a2≡3ａ2(mｏｄp所以3a2是p的倍數(shù),又3和p互質(zhì),可知a一定是p的倍數(shù)，這與假設(shè)ｐ不能整除a矛盾,因此ａ和b必然都是ｐ四、【延伸閱讀】(1）形如4k+1的質(zhì)數(shù)個(gè)數(shù)有無數(shù)個(gè)。假設(shè)ｎ是任意一個(gè)大于1的正整數(shù)：n!顯然為偶數(shù)，因此(n!)２＋1為奇數(shù),而(n!)2+1的每個(gè)質(zhì)因子都可表達(dá)為4ｋ＋1或4k－1的形式。假設(shè)ｐ＝4ｋ－1是（n!)2+1的一個(gè)質(zhì)因子(可知p和n!互質(zhì))，由于(n!)２≡－１(moｄp)將左右兩邊同時(shí)取eｑ＼f（eq\a(p-1),2)次方，得(n！)ｐ-1≡(mｏｄp)由于eq\ｆ（eq\a(p-1)，2)＝2k-１為奇數(shù),因此(n!)p-1≡(-1）（modp)但這與費(fèi)馬小定理矛盾，因此根據(jù)費(fèi)馬小定理,由于p和n！互質(zhì)，（ｎ!)p-１必然會(huì)和1對(duì)模p同余。由此我們推知（n!）2+1不也許有形如４ｋ-1的質(zhì)因子,也就是(n!)2＋1只有形如４k+1的質(zhì)因子。又由于(n!)2＋1的每個(gè)質(zhì)因子顯然都大于ｎ，因此我們就證明了:不管ｎ是多少，一定有比n大并且形如4ｋ+１的質(zhì)數(shù)存在，這就說明了等差數(shù)列1,5,9，13,…中包含無窮多個(gè)質(zhì)數(shù)。（2)費(fèi)馬小定理的逆定理當(dāng)ｐ為質(zhì)數(shù),由費(fèi)馬小定理我們知道2p-２必然是ｐ的倍數(shù)(即前面的討論中當(dāng)a=2的情形）;反過來成不成立呢?也就是說,假如有某個(gè)正整數(shù)n可以整除2ｎ－2，我們能不能斷定n一定是質(zhì)數(shù)呢？假如可以的話,這將是個(gè)不錯(cuò)的判斷任意整數(shù)n是否為質(zhì)數(shù)的方法;歷史上的確曾經(jīng)有一段時(shí)期數(shù)學(xué)家們猜測(cè)這個(gè)方法可行，但是法國數(shù)學(xué)家ＰｉerreSａｒｒｕs于１８2023指出n=341是一個(gè)反例：３41是11與13的積，因此不是質(zhì)數(shù)，但是由2３４1-２=2[(210）34-134]=2[(210-1)(…）]=2(1023)（…)＝2(3)(341)(…)可知３4１能整除２341-2．對(duì)任意正整數(shù)ａ,假如有某個(gè)大于１的正整數(shù)n自身不是質(zhì)數(shù)卻能整除an－a，我們稱n對(duì)底數(shù)ａ而言是一個(gè)［偽質(zhì)數(shù)](英文常稱作a－ｐsｅudopｒime),因此對(duì)底數(shù)2而言，341是一個(gè)偽質(zhì)數(shù)(即341是一個(gè)2－pseudopｒime)。幾個(gè)衍生出來的問題是：３4１是唯一的２-ｐｓeudoｐrime嗎？除了奇數(shù)的偽質(zhì)數(shù)外,是否還存在著[偶偽質(zhì)數(shù)]?對(duì)任意正整數(shù)a,ａ-pseudoprime的個(gè)數(shù)是有限還是無限？對(duì)底數(shù)２而言，假如n是一個(gè)奇?zhèn)钨|(zhì)數(shù)，我們不難證明２ｎ-１將是另一個(gè)更大的奇?zhèn)钨|(zhì)數(shù)；既然我們已知奇?zhèn)钨|(zhì)數(shù)３４1的存在,對(duì)底數(shù)２來說奇?zhèn)钨|(zhì)數(shù)的個(gè)數(shù)因此是無窮的，尋找偶偽質(zhì)數(shù)(對(duì)底數(shù)２而言）的工作比尋找奇?zhèn)钨|(zhì)數(shù)要困難許多，其中最小的數(shù)直到1９50年才由美國數(shù)學(xué)家D.H.Lehｍｅr找到，其值為161０3８＝２7３１1０3．由于２1610３8-2=2(２１61037-1)要說明1６1０3８可以整除2161038－2，我們只要說明73和110３(皆為質(zhì)數(shù))都能整除２161０3７-１即可。由于161037可經(jīng)質(zhì)因數(shù)分解為３2296１7，因此21６10３７-1=2(２9）2＝（29－1）（…)＝(５11