費(fèi)馬小定理及應(yīng)用

11費(fèi)馬小定理及應(yīng)用知識定位，卜 費(fèi)馬小定理是初中數(shù)學(xué)競賽數(shù)論中經(jīng)常出現(xiàn)的一種。要熟練掌握費(fèi)馬小定理是數(shù)論中的一個定理，數(shù)學(xué)表達(dá)形式和應(yīng)用。本節(jié)我們通過一些實(shí)例的求解，旨在介紹數(shù)學(xué)競賽中不定方程相關(guān)問題的常見題型及其求解方法本講將通過例題來說明這些方法的運(yùn)用。知識梳理*/- 1、歐拉函數(shù)：巾(m)是1,2,…，m中與m互質(zhì)的個數(shù)，稱為歐拉函數(shù)①歐拉函數(shù)值的計算公式：若m=pa1pa2…p%則"(m)=m(1—1)。一?)…。一；)12n p1 p2 pn111例如，30=2-3-5,則叭30)=30(1—-)(1--)(1-?=8.乙 J J②若p為素數(shù)，則U5(P)=P-1,5(Pk)=Pk-1(P-1),若p為合數(shù)，貝U①(p)<p-2,1③不超過n且與n互質(zhì)的所有正整數(shù)的和為5n5(n)；④若(a,b)=1n5(ab)=5(a)5(b),若a|b=5(a)|5(b)n⑤設(shè)d為n的正約數(shù)，則不大于n且與n有最大公因數(shù)d的正整數(shù)個數(shù)為5(-)，d同時E5(d)=^5。)=n；dn dn2、歐拉定理:若(a,m)=1,則a小(m)三1(modm).證明：設(shè)r1,r2,…，.⑻是模m的簡化剩余系，又,.，(&,m)=1,.,.a?r1,a?r2,…，&?.(此是模m的簡化剩余系，/.a?r1Xa?r2X…Xa?三r1Xr2X…Xrgmjmodm),又■(ri?r2?…?m)=1，/.axm)三1(modm).應(yīng)用：設(shè)(a,m)=1,c是使得ac三1(modm)的最小正整數(shù)，則c|巾(m).補(bǔ)充：設(shè)m>1是一個固定的整數(shù)，a是與m互質(zhì)的整數(shù)，則存在整數(shù)k(IWkWm),使ak三1(modm),我們稱具有這一性質(zhì)的最小正整數(shù)(仍記為k)稱為a模m的階，由a模m的階的定義，可得如下性質(zhì)：(1)設(shè)(a,m)=1,k是a模m的階，u,v是任意整數(shù)，則au三av(modm)的充要條件是u三v(modk),特別地，au三1(modm)的充要條件是k|u證明：充分性顯然.必要性：設(shè)u>v,l=u-v,由au三av(modm)及(a,m)=1知ai三1(modm).

用帶余除法，l=kq+r,0<r<k,故akq-ar三1(modm),，ar三1(modm),由k的定義知，必須r=0，所以u三v(modk).(2)設(shè)(a,m)=1,k是a模m的階，則數(shù)列a,a%…，期ak+i,…是模m的周期數(shù)列，最小正周期為k,而k個數(shù)a,a%…，ak模m互不同余.(3)設(shè)(a,m)=1,k是a模m的階，則k|巾(m),特別地，若m是素數(shù)P,則a模P的階整除p—1.(4)設(shè)(a,p)=1,則d0是a對于模P的階oad0三1(modp),且1,a,…，az對模p兩兩不同余.特別地，d°="(p)o1,a,…，a")-i構(gòu)成模p的一個簡化剩余系.定理：若l為a對模m的階，s為某一正整數(shù)，滿足as三1(modm),則s必為l的倍數(shù).3、費(fèi)爾馬小定理若p是素數(shù)，則ap三a(modp)若另上條件(a,p)=1,則ap-i三1(modp)4、證明費(fèi)馬小定理的預(yù)備定理定義1：設(shè)a、b和m是整數(shù)，其中m>0,如果有m|(a一b)，則有a三b(modm)。在證明費(fèi)馬小定理之前,我們先給出幾個引理引理1(剩余系定理2)若a,b,c為3個任意整數(shù)，m為正整數(shù)，若有ac三bc(modm)和(c,m)=1,則有a三b(modm)成立。證明：由條件可知ac-bc=0(modn)，化簡有(a一b)c=0(modm)又因為(c,m)=1所以有a一b三0(modm),即有a三b(modm)￡(n^Xc，-k￡(n^Xc，-kyk，其中()=

kkn!k!(n一k)!k=0證明：根據(jù)二項式的展開定理,我們有：+Cn-1X1yn-1+CnX0yn

nn(x+y)n=+Cn-1X1yn-1+CnX0yn

nn=X=Xn+C1Xn-1y+

n+Cn-1Xyn-1+ynn由組合公式可得：￡n(n)由組合公式可得：￡n(n)Xn-k

kyk,其中kk=0n!k!(n一k)!引理3(多項式定理)如果冷k2,k3,……冷和n均是正整數(shù)，且有nN1和Vk2+k3+……+n，則有(x+x+ + x)n=乙Y xk1xk2…xkm1 2 m k1,k2,k3, km1 2 mk1+k2+k3+…+km=n其中(n!k1，k2，…kmk!k!???k!12m(1)初等方法證明：對任意的非負(fù)整數(shù)m及素數(shù)p，恒有【2】(m+1)p=mp+C1mp+1+ +Cp-1m+1三mp+1(modp)pp即有(m+1)p-mp三1(modp)令m=0,1,2,3,……,a-1得p-0p三1(modp)p-1p三1(modp)p-2p三1(modp)(a-1)p-(a-2)p三1(modp)ap-(a-1)p三1(modp)上面各式分別相加得ap三a(modp)(2)二項式的展開法證明：設(shè)集合s={aap三a(modp)}，其中p是質(zhì)數(shù)，aeN，因為0p=0，所以對任意的p有0p三0(modp)則0es現(xiàn)假設(shè)kes,則kP三p(modp)，我們要想得到k+1es,(k+1)p三(k+1)(modp)，通過二項式定理有:(k+1)p=kp+1p+￡^p\p-j三k+1(modp)

jj=1如果(a,p)=1，則化簡ap三a(modp)有ap-1三1(modp)如果a是負(fù)數(shù)，則對任意的r恒有a三r(modp)成立，其中0<r<p-1.從而有ap三rp三r三a(modp).4、威爾遜定理：P為質(zhì)數(shù)O(p-1)!=-1(modp)證明：充分性：若P為質(zhì)數(shù)，當(dāng)P=2,3時成立，當(dāng)p>3時，令x￡{1,2,3,…，p-1},貝U(%,p)=1,在％,2%，…,(p-1)%中，必然有一個數(shù)除以p余1,這是因為%,2%，…，(p—1)%則好是p的一個剩余系去0.從而對V%€{1,2，…p一1},3y€{1,2，…,p一1}，使得%y三1(modp)；若%y三%y(modp),(%,p)=1,則%(y一y)三0(modp),p1(y一y)這不可能。1 2 12 12故對于不同的y,y€{1,2，…,p-1},有%y豐%y(modp).即對于不同的%對應(yīng)于不12 1 2同的y,即1,2，…，p-1中數(shù)可兩兩配對，其積除以p余1,然后有%，使%2三1(modp),即與它自己配對，這時%2-1三0(modp),(%+1)(%-1)三0(modp),%=p-1或％=1.除%=1,p-1外，別的數(shù)可兩兩配對，積除以p余1.故(p-1)!三(p-1>1三-1(modp).必要性：若(p-1)!三一1(modP),假設(shè)P不是質(zhì)數(shù)，則P有真約數(shù)d>1,故(p—1)!三一1(modd),另一方面，d<p,故d|(p—1)!,從而(p—1)!三0(modd),矛盾！??.P為質(zhì)數(shù).5、算術(shù)基本定理任何一個大于1的整數(shù)都可以分解成質(zhì)數(shù)的乘積.如果不考慮這些質(zhì)因子的次序,則這種分解法是唯一的.即對任一整數(shù)n>1,有n=pa1P：2…P：k,其中P1<P尸…<Pk均為素數(shù)，a1、a2、…、ak都是正整數(shù).①正整數(shù)d是n的約數(shù)od=p%pB2…PT,(0WBWa,i=1,2,…，k)12k ii②由乘法原理可得：n的正約數(shù)的個數(shù)為r(n)=(a1+1)(a2+1)…(ak+1)③n的正約數(shù)的和為S(n)=(1+p1H HpaJd+p2H bpa2)…(1+PkH bp：J④n的正約數(shù)的積為T(n)=n2"n)⑤n為平方數(shù)的充要條件是：r(n)為奇數(shù). _(1)判斷質(zhì)數(shù)的方法：設(shè)n是大于2的整數(shù)，如果不大于的質(zhì)數(shù)都不是n的因子，則n是質(zhì)數(shù).(2)n!的標(biāo)準(zhǔn)分解：設(shè)P是不大于n的質(zhì)數(shù)，則n!中含質(zhì)數(shù)P的最高次冪為：nnn n 、P(n!)=[—]+[——]+[——]+…+[——](pm<n<pm+1).從而可以寫出n!的標(biāo)準(zhǔn)分解式.Pp2p3 pm例題精講【試題來源】【題目】證明：當(dāng)質(zhì)數(shù)p三7時，240|p4-1【答案】如下解析【解析】證明：???PN—1=(P—1)(P+1)(P"2+1)1°大于7的質(zhì)數(shù)必是奇數(shù)，??.2|P-2+1；2°(P—1)(P+1)是連續(xù)偶數(shù)，???8|(P-1)(P+1)；(整數(shù)的性質(zhì)一一兩個連續(xù)偶數(shù)中,其中一個是4的倍數(shù).)3°若P三±1(mod5)則5|(P—1)(P+1)若P三±2(mod5)則5|P"2+1；???5|(P—1)(P+1)(P"2+1)4°P是大于7的質(zhì)數(shù)必是奇數(shù)，則P三±1(mod3).?.3|(P—1)(P+1)p=7時，p-4-1=2400.綜上所述：240P4—1【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】當(dāng)堂例題【難度系數(shù)】4【試題來源】【題目】求20032005被17除所得的余數(shù).【答案】14【解析】解：20032005=(17X114+14)2005三142005(mod17),因為(17,14)=1,所以由費(fèi)馬小定理得1416三1(mod17),故20032005三142005三1416x125+5三145三（一3）5三（一3）（一3）三（一4）（-3）=12（mod17）,所以20032005被17除所得的余數(shù)是14.【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】當(dāng)堂練習(xí)【難度系數(shù)】3【試題來源】【題目】已知a為正整數(shù)，a三2,且(a,10)=1,求a20的末兩位數(shù)字【答案】01【解析】 解：???(&,10)=1,??.a為奇數(shù)，；.a20=a。(25)三1(mod25),又,「&2三1(mod4)na20三1(mod4),又,二(25,4)=1,/.a20=l(mod100),??.a2。的末兩位數(shù)字01.【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】當(dāng)堂例題【難度系數(shù)】3【試題來源】【題目】證明：方程12+5=y3無整數(shù)解.【答案】如下解析【解析】 證明：若y是偶數(shù)，則8|y3,X2三3(mod8)不可能.令x=2s,y=2t+1得2s2+2=4t3+612+3t,知t是偶數(shù)，令t=2j,代入得52+1=(16上2+12上+3)由(16j2+12j+3)三3(mod4)知存在4k+3型的奇素數(shù)P，使得p|(16j2+12j+3),從而p|S2+1,p=1 p-1即S2三一1(modp),有(s,p)=1,(s2)2三(-1)2(modp),于是sp-1三一1(modp)與費(fèi)爾馬小定理矛盾.【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】當(dāng)堂練習(xí)題【難度系數(shù)】4【試題來源】【題目】試證：對于每一個素數(shù)p,總存在無窮多個正整數(shù)小使得p|2n-n..【答案】如下解析【解析】 證明：若p=2,則n為偶數(shù)時結(jié)論成立.若p>2,則(2,p)=1,由費(fèi)爾馬小定理2p-i三1(modp),故對于任意m,有2m(p-i)三1(modp)....2m(P-i)—m(p—1)三1+m(modp),令1+m三0(mod口)，即皿=卜口一1,則對于n=m(p—1)=(kp—1)(p—1)(k￡N*),均有2n—n被p整除【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】當(dāng)堂例題【難度系數(shù)】3【試題來源】【題目】設(shè)a,b為正整數(shù)，對任意的自然數(shù)n有an+nbn+n，則a=b.【答案】如下解析【解析】證明：假設(shè)a與b不相等.考慮n=1有a+1|b+1，則a<b.設(shè)p是一個大于b的素數(shù)，設(shè)n是滿足條件的正整數(shù):n三1(mod(p-1)),n三一a(modp),由孫子定理這樣的n是存在的，如n=(a+l)(p—1)+1.由費(fèi)馬定理an=ak(p-i)+i三a(modp),所以an+n三0(modp),也即p\bn+n,再由費(fèi)馬定理bn+n三b-a(modp),所以p\b-a，矛盾.【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】當(dāng)堂練習(xí)題【難度系數(shù)】4習(xí)題演練—【試題來源】【題目】設(shè)p是奇素數(shù)，證明：2p—1的任一素因了具有形式2px+1,x是正整數(shù).【答案】如下解析【解析】證明：設(shè)q是2p—1的任一素因子，則qW2.設(shè)2模q的階是k,則由2p三1(modq)知k|p,故k=1或p(因p是素數(shù)，這是能確定階k的主要因素).顯然kW1,否則21三1(modq),這不可能，因此k=p.由費(fèi)馬小定理2q-1三1(modq)推出kIq-1,即pIq-1.因p、q都是奇數(shù)，故q—1=2px(x是個正整數(shù)).【知識點(diǎn)】費(fèi)馬小定理及應(yīng)用【適用場合】隨堂