奧數探秘之費馬小定理

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

費馬小定理的歷史

皮埃爾•德•費馬于16發(fā)現了這個定理，在一封1610月18日的信中他第一次使用了上面的書寫方式。在他的信中費馬還提出a是一個質數的要求，但是這個要求實際上是不存在的。

與費馬小定理相關的有一個中國猜想，這個猜想是中國數學家提出來的，其內容為：當且僅當2^(p-1)≡1(mod p)，p是一個質數。

假如p是一個質數的話，則2^(p-1)≡1(mod p)成立(這是費馬小定理的一個特殊情況)是對的。但反過來，假如2^(p-1)≡1(mod p)成立那么p是一個質數是不成立的(比如341符合上述條件但不是一個質數)。因此整個來說這個猜想是錯誤的。

一般認為中國數學家在費馬前的時候就已經認識中國猜測了，但也有人認為實際上中國猜測是18提出的，認為它早就為人所知是出于一個誤解。

費馬小定理的證明

一、準備知識：

引理1.剩余系定理2

若a,b,c為任意3個整數，m為正整數，且(m,c)=1,則當ac≡bc(modm)時，有a≡b(modm)

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

引理2.剩余系定理5

若m為整數且m>1,a[1],a[2],a[3],a[4],…a[m]為m個整數，若在這m個數中任取2個整數對m不同余，則這m個整數對m構成完全剩余系。

證明：構造m的完全剩余系(0,1,2,…m-1)，所有的整數必然這些整數中的1個對模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1

引理3.剩余系定理7

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

證明：若存在2個整數ba和ba[j]同余即ba≡ba[j](mod m)，根據引理2則有a≡a[j](mod m)。根據完全剩余系的定義和引理4(完全剩余系中任意2個數之間不同余，易證明)可知這是不可能的，因此不存在2個整數ba和ba[j]同余。

由引理5 可知ba[1],ba[2],ba[3],ba[4],…ba[m]構成模m的一個完全剩余系。

引理4.同余定理6

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

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

二、證明過程：

構造素數p的完全剩余系P={1,2,3,4…(p-1)}，因為(a,p)=1，由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一個完全剩余系。令W=1*2*3*4…*(p-1)，顯然W≡W(mod p)。

令Y=a*2a*3a*4a*…(p-1)a,因為{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)

費馬小定理在數論中的地位

費馬小定理是數論四大定理(威爾遜定理，歐拉定理(數論中的歐拉定理，即歐拉函數)，中國剩余定理和費馬小定理)之一，在初等數論中有著非常廣泛和重要的應用。實際上，它是歐拉定理的一個特殊情況(見于詞條“歐拉函數”)。

費馬小定理的實際應用

如上所述，中國猜測只有一半是正確的，符合中國猜測但不是質數的數被稱為“偽質數”。

對于中國猜測稍作改動，即得到判斷一個數是否為質數的一個方法：

如果對于任意滿足1 < b < p的b下式都成立：

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

則p必定是一個質數。

實際上，沒有必要測試所有的小于p的自然數，只要測試所有的小于p的質數就可以了。

這個算法的缺點是它非常慢，運算率高;但是它很適合在計算機上面運行程序進行驗算一個數是否是質數。