假如p是質(zhì)數(shù)，且(a,p)=1，那么 a^(p-1) ≡1（mod p）
假如p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的(p-1)次方除以p的余數(shù)恒等于1
歷史
與費(fèi)馬小定理相關(guān)的有一個中國猜想，這個猜想是中國數(shù)學(xué)家提出來的，其內(nèi)容為：當(dāng)且僅當(dāng)2^(p-1）≡1(mod p），p是一個質(zhì)數(shù)。 假如p是一個質(zhì)數(shù)的話，則2^(p-1）≡1(mod p）成立（這是費(fèi)馬小定理的一個特殊情況）是對的。但反過來，假如2^(p-1）≡1(mod p）成立那么p是一個質(zhì)數(shù)是不成立的（比如341符合上述條件但不是一個質(zhì)數(shù)）。因此整個來說這個猜想是錯誤的。一般認(rèn)為中國數(shù)學(xué)家在費(fèi)馬前2000年的時候就已經(jīng)認(rèn)識中國猜測了，但也有人認(rèn)為實(shí)際上中國猜測是1872年提出的，認(rèn)為它早就為人所知是出于一個誤解。 一、準(zhǔn)備知識： 引理1．剩余系定理2 若a,b,c為任意3個整數(shù)，m為正整數(shù)，且（m,c)=1，則當(dāng)ac≡bc(mod m）時，有a≡b(mod m) 證明：ac≡bc(mod m）可得ac–bc≡0(mod m）可得（a-b)c≡0(mod m）因?yàn)椋╩,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個整數(shù)，若在這m個數(shù)中任取2個整數(shù)對m不同余，則這m個整數(shù)對m構(gòu)成完全剩余系。 證明：構(gòu)造m的完全剩余系（0,1,2，…m-1），所有的整數(shù)必然這些整數(shù)中的1個對模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3，…r=i-1,1<i<=m。令（1）：a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m）（順序可以不同），因?yàn)橹挥性谶@種情況下才能保證集合{a1,a2,a3,a4，…am}中的任意2個數(shù)不同余，否則必然有2個數(shù)同余。由式（1）自然得到集合{a1,a2,a3,a4，…am}對m構(gòu)成完全剩余系。 引理3．剩余系定理7 設(shè)m是一個整數(shù)，且m>1，b是一個整數(shù)且（m,b)=1。如果a1,a2,a3,a4，…am是模m的一個完全剩余系，則ba[1],ba[2],ba[3],ba[4]，…ba[m]也構(gòu)成模m的一個完全剩余系。 證明：若存在2個整數(shù)ba和ba[j]同余即ba≡ba[j](mod m），根據(jù)引理1則有a≡a[j](mod m）。根據(jù)完全剩余系的定義和引理4（完全剩余系中任意2個數(shù)之間不同余，易證明）可知這是不可能的，因此不存在2個整數(shù)ba和ba[j]同余。由引理5可知ba[1],ba[2],ba[3],ba[4]，…ba[m]構(gòu)成模m的一個完全剩余系。 引理4．同余定理6 如果a,b,c,d是四個整數(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≡bd(mod m) 二、證明過程： 構(gòu)造素?cái)?shù)p的完全剩余系P={1,2,3,4…（p-1)}，因?yàn)椋╝,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，因?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）
posted on 2012-04-11 07:16
luis 閱讀(899)
評論(0) 編輯 收藏 引用 所屬分類:
組合數(shù)學(xué)