數論四大定理

威爾遜定理、歐拉定理、孫子定理（中國剩餘定理）、費馬小定理並稱數論四大定理。

基本介紹

• 中文名：數論四大定理
• 定理：威爾遜、歐拉、孫子、費馬小定理
• 屬性：數學
• 歐拉定理別稱：費馬-歐拉定理

威爾遜定理

概念

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

證明

充分性

如果p不是素數，

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

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

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

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

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

必要性

若p是素數,取集合 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為正整數，且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)。證畢。

孫子定理

概念

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

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

證明

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

費馬小定理

概念

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

若p是質數，且a,p互質，那么 a的(p-1)次方除以p的餘數恆等於1。

證明

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

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

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

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