1.威爾遜定理

當(dāng)且僅當(dāng)p為素?cái)?shù)時(shí)：( p -1 )! ≡ -1 ( mod p )

或者這么寫( p -1 )! ≡ p-1 ( mod p )

或者說(shuō)若p為質(zhì)數(shù)，則p能被(p-1)!+1整除

2.歐拉定理

歐拉定理，也稱費(fèi)馬-歐拉定理

若n,a為正整數(shù)，且n,a互質(zhì)，即gcd(a,n) = 1，則

a^φ(n) ≡ 1 (mod n)

3.孫子定理（中國(guó)剩余定理）

用現(xiàn)代數(shù)學(xué)的語(yǔ)言來(lái)說(shuō)明的話，中國(guó)剩余定理給出了以下的一元線性同余方程組

4.費(fèi)馬小定理

假如p是質(zhì)數(shù)，若p不能整除a，則 a^(p-1) ≡1（mod p），若p能整除a，則a^(p-1) ≡0（mod p）。

或者說(shuō)，若p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的(p-1)次方除以p的余數(shù)恒等于1。

順便提一下,費(fèi)馬大定理:當(dāng)整數(shù)n >2時(shí)，關(guān)于x, y, z的方程 x^n + y^n = z^n 沒(méi)有正整數(shù)解

威爾遜定理、歐拉定理、孫子定理（中國(guó)剩余定理）、費(fèi)馬小定理并稱數(shù)論四大定理。

威爾遜定理

概念

p可整除(p-1)!+1是p為質(zhì)數(shù)的充要條件

證明

充分性

如果p不是素?cái)?shù)，

當(dāng)p=4時(shí)，顯然（p-1)!≡6≡2(mod p),

當(dāng)p>4時(shí)，若p不是完全平方數(shù)，則存在兩個(gè)不等的因數(shù)a，b使得ab=p，

則(p-1)!≡nab≡0(mod p);

若p是完全平方數(shù)即p=k^2，因?yàn)閜>4,所以k>2，k,2k<p，

(p-1)!≡n(k*2k)≡n'k^2≡0(mod p)。

必要性

若p是素?cái)?shù),取集合 A={1,2,3,...p -1}; 則A 構(gòu)成模p乘法的縮系,即任意i∈A ,存在j∈A,使得:( i j ) ≡ 1 ( mod p )

那么A中的元素是不是恰好兩兩配對(duì)呢?

不一定,但只需考慮這種情況x^2 ≡ 1 ( mod p )

解得: x ≡ 1 ( mod p ) 或 x ≡ p - 1 ( mod p )

其余兩兩配對(duì);故而( p - 1 )! ≡ 1﹡( p -1 ) ≡ -1 ( mod p )

歐拉定理

概念

歐拉定理，也稱費(fèi)馬-歐拉定理。

若n,a為正整數(shù)，且n,a互素，即gcd(a,n) = 1，則

a^φ(n) ≡ 1 (mod n)

證明

設(shè)x（1），x（2），...，x(φ(n))是一個(gè)以n為模的縮系，

則ax（1），ax（2），...，ax（φ(n) ）也是一個(gè)以n為模的縮系（因?yàn)椋╝，n）=1）。

于是有ax（1）ax（2）...ax（φ(n) ）≡x（1）x（2）...x(φ(n))（mod n），

所以a^φ(n) ≡ 1 (mod n)。證畢。

孫子定理

概念

孫子定理，又稱中國(guó)剩余定理。

中國(guó)剩余定理說(shuō)明：假設(shè)整數(shù)m1,m2, ... ,mn兩兩互質(zhì)，則對(duì)任意的整數(shù)：a1,a2, ... ,an，方程組S有解，并可構(gòu)造得出。構(gòu)造詳見詞條“中國(guó)剩余定理”。

證明

將構(gòu)造結(jié)果代入驗(yàn)證即可。

費(fèi)馬小定理

概念

假如p是質(zhì)數(shù)，若p不能整除a，則 a^(p-1) ≡1（mod p），若p能整除a，則a^(p-1) ≡0（mod p）。

若p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的(p-1)次方除以p的余數(shù)恒等于1。

證明

因?yàn)閜是質(zhì)數(shù)，且（a，p)=1，所以φ(p)=p-1。

由歐拉定理可得a^(p-1) ≡1（mod p）。證畢。

對(duì)于該式又有a^p ≡a（mod p），而且此式不需要（a，p）=1，

所以，費(fèi)馬小定理的另一種表述為：假如p是質(zhì)數(shù)，a是整數(shù)，那么a^p ≡a（mod p）。

威爾遜定理、歐拉定理、孫子定理（中國(guó)剩余定理）、費(fèi)馬小定理并稱數(shù)論四大定理。