基礎數(shù)論四大定理

1.威爾遜定理

當且僅當p為素數(shù)時：( p -1 )! ≡ -1 ( mod p )

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

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

2.歐拉定理

歐拉定理，也稱費馬-歐拉定理

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

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

3.孫子定理（中國剩余定理）

用現(xiàn)代數(shù)學的語言來說明的話，中國剩余定理給出了以下的一元線性同余方程組

4.費馬小定理

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

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

順便提一下,費馬大定理:當整數(shù)n >2時，關于x, y, z的方程 x^n + y^n = z^n 沒有正整數(shù)解

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

威爾遜定理

概念

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

證明

充分性

如果p不是素數(shù)，

當p=4時，顯然（p-1)!≡6≡2(mod p),

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

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

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

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

必要性

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

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

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

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

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

歐拉定理

概念

歐拉定理，也稱費馬-歐拉定理。

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

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

證明

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

則ax（1），ax（2），...，ax（φ(n) ）也是一個以n為模的縮系（因為（a，n）=1）。

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

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

孫子定理

概念

孫子定理，又稱中國剩余定理。

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

證明

將構造結果代入驗證即可。

費馬小定理

概念

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

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

證明

因為p是質數(shù)，且（a，p)=1，所以φ(p)=p-1。

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

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

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

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