2025年下學(xué)期初中數(shù)學(xué)競(jìng)賽費(fèi)馬小定理試卷一、定理講解費(fèi)馬小定理是數(shù)論中的重要定理，由法國(guó)數(shù)學(xué)家皮埃爾·德·費(fèi)馬在1640年提出。其基本內(nèi)容為：如果p是質(zhì)數(shù)，且整數(shù)a與p互質(zhì)（即(a,p)=1），那么a^(p-1)≡1(modp)。這個(gè)定理揭示了整數(shù)冪運(yùn)算在模運(yùn)算中的重要規(guī)律，為解決數(shù)論問(wèn)題提供了有力工具。費(fèi)馬小定理有一個(gè)常用的變異形式：a^p≡a(modp)。需要注意的是，當(dāng)p不整除a時(shí)，兩個(gè)命題等價(jià)；當(dāng)p整除a時(shí)，變異形式顯然成立。這個(gè)變異形式有時(shí)使用起來(lái)更加方便，因?yàn)樗恍枰紤]a與p是否互質(zhì)的條件。與費(fèi)馬小定理相關(guān)的還有一個(gè)中國(guó)猜想，其內(nèi)容為：當(dāng)且僅當(dāng)2^(p-1)≡1(modp)時(shí)，p才是一個(gè)質(zhì)數(shù)。需要指出的是，這個(gè)猜想并不完全正確。如果p是一個(gè)質(zhì)數(shù)，那么2^(p-1)≡1(modp)成立，這是費(fèi)馬小定理的一個(gè)特殊情況。但反過(guò)來(lái)，如果2^(p-1)≡1(modp)成立，p不一定是質(zhì)數(shù)。例如，341符合上述條件但不是質(zhì)數(shù)，這樣的數(shù)被稱為"偽質(zhì)數(shù)"。二、定理證明為了證明費(fèi)馬小定理，我們需要先引入幾個(gè)重要的引理：引理1（同余的基本性質(zhì)）如果a≡b(modm)，且c≡d(modm)，則有ac≡bd(modm)。引理2（完全剩余系的性質(zhì)）設(shè)m是一個(gè)正整數(shù)，a1,a2,...,am是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-1}，所有的整數(shù)必然與這些整數(shù)中的某一個(gè)對(duì)模m同余。取r1=0,r2=1,r3=2,...,rm=m-1。令a1≡r1(modm),a2≡r2(modm),...,am≡rm(modm)（次序可以不同）。由于只有在這種情況下才能保證集合{a1,a2,...,am}中的任意2個(gè)數(shù)不同余，否則必然有2個(gè)數(shù)同余。因此，集合{a1,a2,...,am}對(duì)m構(gòu)成完全剩余系。引理3設(shè)m是一個(gè)整數(shù)，且m>1，b是一個(gè)整數(shù)且(b,m)=1。如果a1,a2,...,am是模m的一個(gè)完全剩余系，則ba1,ba2,...,bam也構(gòu)成模m的一個(gè)完全剩余系。證明：若存在2個(gè)整數(shù)bai和baj同余，即bai≡baj(modm)。由于(b,m)=1，根據(jù)同余的性質(zhì)，可以兩邊同時(shí)除以b，得到ai≡aj(modm)。根據(jù)完全剩余系的定義，這是不可能的，因此不存在2個(gè)整數(shù)bai和baj同余。由引理2可知，ba1,ba2,...,bam構(gòu)成模m的一個(gè)完全剩余系。費(fèi)馬小定理的證明構(gòu)造素?cái)?shù)p的完全剩余系P={1,2,3,...,p-1}。由于(a,p)=1，由引理3可得A={a,2a,3a,...,(p-1)a}也是p的一個(gè)完全剩余系。令W=1×2×3×...×(p-1)，顯然W≡W(modp)。令Y=a×2a×3a×...×(p-1)a，由于{a,2a,3a,...,(p-1)a}是p的完全剩余系，由引理2和引理1可得：a×2a×3a×...×(p-1)a≡1×2×3×...×(p-1)(modp)即W×a^(p-1)≡W(modp)。由于W是1到p-1的乘積，而p是質(zhì)數(shù)，因此(W,p)=1。根據(jù)同余的性質(zhì)，可以兩邊同時(shí)除以W，得到a^(p-1)≡1(modp)。至此，費(fèi)馬小定理得證。三、例題解析例1設(shè)n為正整數(shù)，證明：n^5≡n(mod5)的充要條件是n^5≡n(mod10)。證明：若n^5≡n(mod10)，則顯然有n^5≡n(mod5)，因?yàn)?0是5的倍數(shù)。反過(guò)來(lái)，若n^5≡n(mod5)，需要證明n^5≡n(mod10)，即證明n^5與n的奇偶性相同。當(dāng)n為偶數(shù)時(shí)，n^5是偶數(shù)，n也是偶數(shù)，因此n^5≡n(mod2)。當(dāng)n為奇數(shù)時(shí)，n^5是奇數(shù)，n也是奇數(shù)，因此n^5≡n(mod2)。綜上，無(wú)論n是奇數(shù)還是偶數(shù)，都有n^5≡n(mod2)。又已知n^5≡n(mod5)，且2和5互質(zhì)，根據(jù)中國(guó)剩余定理，可得n^5≡n(mod10)。例2是否存在合數(shù)n，使得2^(n-1)≡1(modn)成立？解：這樣的合數(shù)存在，并且有無(wú)數(shù)多個(gè)。其中最小的滿足條件的合數(shù)是341。驗(yàn)證：341=11×31，是一個(gè)合數(shù)。我們來(lái)驗(yàn)證2^340≡1(mod341)。根據(jù)費(fèi)馬小定理，2^10≡1(mod11)，因此2^340=(2^10)^34≡1^34≡1(mod11)。又因?yàn)?^5=32≡1(mod31)，所以2^340=(2^5)^68≡1^68≡1(mod31)。由于11和31互質(zhì)，根據(jù)中國(guó)剩余定理，2^340≡1(mod341)。因此341是一個(gè)滿足條件的合數(shù)。進(jìn)一步，設(shè)n是一個(gè)符合規(guī)定的奇合數(shù)，則n'=2^n-1也是一個(gè)奇合數(shù)。依此類推，可以證明存在無(wú)窮多個(gè)滿足條件的合數(shù)。滿足這種性質(zhì)的合數(shù)稱為"偽質(zhì)數(shù)"。如果對(duì)任意與n互質(zhì)的整數(shù)a，都有a^(n-1)≡1(modn)成立，那么合數(shù)n稱為"絕對(duì)偽質(zhì)數(shù)"。例3設(shè)p為質(zhì)數(shù)，證明：存在無(wú)窮多個(gè)正整數(shù)n，使得p整除(n^2-2)。證明：如果p=2，則取n為偶數(shù)，就有n^2-2≡0(mod2)，命題成立。如果p=3，取n=1,2,4,5,...，即所有不是3的倍數(shù)的整數(shù)，都有n^2-2≡0(mod3)，命題成立。設(shè)p>3，考慮以下兩種情況：情況1：2是模p的二次剩余，即存在整數(shù)a，使得a^2≡2(modp)。此時(shí)取n=a+kp(k為整數(shù))，則n^2-2≡0(modp)，顯然有無(wú)數(shù)多個(gè)這樣的n。情況2：2不是模p的二次剩余。根據(jù)費(fèi)馬小定理，2^(p-1)≡1(modp)。令p-1=2^k·m，其中m為奇數(shù)。考慮序列2^m,2^(3m),2^(5m),...,2^((2t+1)m)(modp)。由于2不是二次剩余，k≥1?？梢宰C明該序列中一定存在某個(gè)元素b，使得b≡-1(modp)。令n=b+1，則n^2-2≡0(modp)。因此存在無(wú)窮多個(gè)這樣的n。例4設(shè)p是奇質(zhì)數(shù)，且p整除(2^(2^n)+1)，證明：p≡1(mod2^(n+1))。證明：由于p整除(2^(2^n)+1)，因此2^(2^n)≡-1(modp)。兩邊平方，得到2^(2^(n+1))≡1(modp)。設(shè)d是2模p的階，即d是使得2^d≡1(modp)成立的最小正整數(shù)。由上式可知d整除2^(n+1)，但d不整除2^n（否則2^(2^n)≡1(modp)，與2^(2^n)≡-1(modp)矛盾）。因此d=2^(n+1)。根據(jù)費(fèi)馬小定理，2^(p-1)≡1(modp)，因此d整除p-1，即2^(n+1)整除p-1。因此p≡1(mod2^(n+1))。例5求所有的質(zhì)數(shù)p，使得p^2+2是一個(gè)完全平方數(shù)。解：設(shè)p是一個(gè)滿足條件的質(zhì)數(shù)，則存在正整數(shù)k，使得p^2+2=k^2。因此k^2-p^2=2，即(k-p)(k+p)=2。由于k和p都是正整數(shù)，且k>p，因此k-p和k+p都是正整數(shù)，且k-p<k+p，(k-p)(k+p)=2?？紤]2的正整數(shù)因子分解，只有1×2=2這一種可能。因此：k-p=1k+p=2解這個(gè)方程組，得到k=3/2，p=1/2。這與p是質(zhì)數(shù)矛盾，因此不存在滿足條件的質(zhì)數(shù)p。例6求145^89+3^2000除以13的余數(shù)。解：13是質(zhì)數(shù)，且145與13互質(zhì)，3與13互質(zhì)。由費(fèi)馬小定理得：145^12≡1(mod13)，3^12≡1(mod13)。計(jì)算指數(shù)除以12的余數(shù)：89÷12=7余5，因此145^89=(145^12)^7×145^5≡1^7×145^5≡145^5(mod13)。145÷13=11余2，因此145≡2(mod13)，所以145^5≡2^5=32≡6(mod13)。2000÷12=166余8，因此3^2000=(3^12)^166×3^8≡1^166×3^8≡3^8(mod13)。3^4=81≡3(mod13)，因此3^8=(3^4)^2≡3^2=9(mod13)。因此145^89+3^2000≡6+9=15≡2(mod13)。所以145^89+3^2000除以13的余數(shù)是2。四、練習(xí)題基礎(chǔ)題計(jì)算3^100除以7的余數(shù)。證明：對(duì)于任意正整數(shù)n，n^7-n能被7整除。求2^2025除以11的余數(shù)。證明：如果p是質(zhì)數(shù)，且p不整除a，那么a^(p-2)是a模p的逆元，即a^(p-2)·a≡1(modp)。利用費(fèi)馬小定理，求5^2025mod7的值。提高題證明：如果p是奇質(zhì)數(shù)，那么2^(p-1)的個(gè)位數(shù)不可能是2,4,5,6,8。設(shè)p是質(zhì)數(shù)，證明：1^p+2^p+...+(p-1)^p≡0(modp)。證明：如果p是質(zhì)數(shù)，且p≡3(mod4)，那么[(p-1)/2]^2≡-1(modp)。求所有的質(zhì)數(shù)p，使得2^p+3^p是一個(gè)完全平方數(shù)。證明：對(duì)于任意質(zhì)數(shù)p>5，p^4≡1(mod240)。挑戰(zhàn)題設(shè)p是奇質(zhì)數(shù)，證明：2^p-1的質(zhì)因子q滿足q≡1(mod2p)。證明：存在無(wú)窮多個(gè)形如4k+1的質(zhì)數(shù)。（提示：考慮數(shù)n=(2·4·6·...·2m)^2+1的質(zhì)因子）設(shè)p是質(zhì)數(shù)，證明：如果2^p-1是質(zhì)數(shù)，那么p一定是質(zhì)數(shù)。（這樣的質(zhì)數(shù)稱為梅森質(zhì)數(shù)）證明：對(duì)于任意正整數(shù)n，n^13-n能被2730整除。（提示：2730=2×3×5×7×13）設(shè)p是奇質(zhì)數(shù)，證明：在1,2,...,p-1中，存在(p-1)/2個(gè)二次剩余和(p-1)/2個(gè)非二次剩余。五、答案與提示基礎(chǔ)題答案3^100mod7：由費(fèi)馬小定理，3^6≡1(mod7)，100=6×16+4，3^100≡3^4=81≡4(mod7)，答案為4。n^7-n：由費(fèi)馬小定理，n^7≡n(mod7)，因此n^7-n≡0(mod7)，即7整除n^7-n。2^2025mod11：11是質(zhì)數(shù)，2^10≡1(mod11)，2025=10×202+5，2^2025≡2^5=32≡10(mod11)，答案為10。由費(fèi)馬小定理，a^(p-1)≡1(modp)，因此a^(p-2)·a=a^(p-1)≡1(modp)，即a^(p-2)是a模p的逆元。5^2025mod7：7是質(zhì)數(shù)，5^6≡1(mod7)，2025=6×337+3，5^2025≡5^3=125≡6(mod7)，答案為6。提高題提示考慮2^kmod10的周期規(guī)律，結(jié)合費(fèi)馬小定理分析。對(duì)每個(gè)i(1≤i≤p-1)，由費(fèi)馬小定理，i^p≡i(modp)?？紤](p-1)!≡-1(modp)（威爾遜定理），將乘積配對(duì)。分p=2,p=3和p>3三種情況討論，注意完全平方數(shù)模4的性質(zhì)。240=16×3×5，