費(fèi)馬小定理是數(shù)論中的一個(gè)重要定理,其內(nèi)容為:

　　假如p是質(zhì)數(shù)，且(a,p)=1，那么 a^(p-1) ≡1(mod p)

　　費(fèi)馬小定理的歷史

　　皮埃爾•德•費(fèi)馬于1636年發(fā)現(xiàn)了這個(gè)定理，在一封1640年10月18日的信中他第一次使用了上面的書(shū)寫(xiě)方式。在他的信中費(fèi)馬還提出a是一個(gè)質(zhì)數(shù)的要求，但是這個(gè)要求實(shí)際上是不存在的。與費(fèi)馬小定理相關(guān)的有一個(gè)中國(guó)猜想，這個(gè)猜想是中國(guó)數(shù)學(xué)家提出來(lái)的，其內(nèi)容為：當(dāng)且僅當(dāng)2^(p-1)≡1(mod p)，p是一個(gè)質(zhì)數(shù)。

　　假如p是一個(gè)質(zhì)數(shù)的話(huà)，則2^(p-1)≡1(mod p)成立(這是費(fèi)馬小定理的一個(gè)特殊情況)是對(duì)的。但反過(guò)來(lái)，假如2^(p-1)≡1(mod p)成立那么p是一個(gè)質(zhì)數(shù)是不成立的(比如341符合上述條件但不是一個(gè)質(zhì)數(shù))。因此整個(gè)來(lái)說(shuō)這個(gè)猜想是錯(cuò)誤的。一般認(rèn)為中國(guó)數(shù)學(xué)家在費(fèi)馬前2000年的時(shí)候就已經(jīng)認(rèn)識(shí)中國(guó)猜測(cè)了，但也有人認(rèn)為實(shí)際上中國(guó)猜測(cè)是1872年提出的，認(rèn)為它早就為人所知是出于一個(gè)誤解。

　　費(fèi)馬小定理的證明

　　一、準(zhǔn)備知識(shí)：

　　引理1.剩余系定理2

　　若a,b,c為任意3個(gè)整數(shù)，m為正整數(shù)，且(m,c)=1,則當(dāng)ac≡bc(modm)時(shí)，有a≡b(modm)

　　證明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因?yàn)?m,c)=1即m,c互質(zhì)，c可以約去，a–b≡0(mod m)可得a≡b(mod m)

　　引理2.剩余系定理5

　　若m為整數(shù)且m>1,a[1],a[2],a[3],a[4],…a[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-1)，所有的整數(shù)必然這些整數(shù)中的1個(gè)對(duì)模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1

　　引理3.剩余系定理7

　　設(shè)m是一個(gè)整數(shù)，且m>1，b是一個(gè)整數(shù)且(m,b)=1。如果a1,a2,a3,a4,…am是模m的一個(gè)完全剩余系，則ba[1],ba[2],ba[3],ba[4],…ba[m]也構(gòu)成模m的一個(gè)完全剩余系。

　　證明：若存在2個(gè)整數(shù)ba和ba[j]同余即ba≡ba[j](mod m)，根據(jù)引理2則有a≡a[j](mod m)。根據(jù)完全剩余系的定義和引理4(完全剩余系中任意2個(gè)數(shù)之間不同余，易證明)可知這是不可能的，因此不存在2個(gè)整數(shù)ba和ba[j]同余。由引理5 可知ba[1],ba[2],ba[3],ba[4],…ba[m]構(gòu)成模m的一個(gè)完全剩余系。

　　引理4.同余定理6

　　如果a,b,c,d是四個(gè)整數(shù)，且a≡b(mod m),c≡d(mod m),則有ac≡bd(mod m)

　　證明：由題設(shè)得ac≡bc(mod m),bc≡bd(mod m)，由模運(yùn)算的傳遞性可得ac≡bc(mod m)

　　二、證明過(guò)程：

　　構(gòu)造素?cái)?shù)p的完全剩余系P={1,2,3,4…(p-1)}，因?yàn)?a,p)=1，由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一個(gè)完全剩余系。令W=1*2*3*4…*(p-1)，顯然W≡W(mod p)。令Y=a*2a*3a*4a*…(p-1)a,因?yàn)閧a,2a,3a,4a,…(p-1)a}是p的完全剩余系，由引理2以及引理4可得 a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp)。易知(W,p)=1，由引理1可知a^(p-1)≡1(modp)

　　費(fèi)馬小定理在數(shù)論中的地位

　　費(fèi)馬小定理是數(shù)論四大定理(威爾遜定理，歐拉定理(數(shù)論中的歐拉定理，即歐拉函數(shù))，中國(guó)剩余定理和費(fèi)馬小定理)之一，在初等數(shù)論中有著非常廣泛和重要的應(yīng)用。實(shí)際上，它是歐拉定理的一個(gè)特殊情況(見(jiàn)于詞條“歐拉函數(shù)”)。

　　費(fèi)馬小定理的實(shí)際應(yīng)用

　　如上所述，中國(guó)猜測(cè)只有一半是正確的，符合中國(guó)猜測(cè)但不是質(zhì)數(shù)的數(shù)被稱(chēng)為“偽質(zhì)數(shù)”。

　　對(duì)于中國(guó)猜測(cè)稍作改動(dòng)，即得到判斷一個(gè)數(shù)是否為質(zhì)數(shù)的一個(gè)方法：

　　如果對(duì)于任意滿(mǎn)足1 < b < p的b下式都成立：

　　b^(p-1)≡1(mod p)

　　則p必定是一個(gè)質(zhì)數(shù)。

　　實(shí)際上，沒(méi)有必要測(cè)試所有的小于p的自然數(shù)，只要測(cè)試所有的小于p的質(zhì)數(shù)就可以了。

　　這個(gè)算法的缺點(diǎn)是它非常慢，運(yùn)算率高;但是它很適合在計(jì)算機(jī)上面運(yùn)行程序進(jìn)行驗(yàn)算一個(gè)數(shù)是否是質(zhì)數(shù)。