威爾遜定理
概念
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），
所以，費馬小定理的另一種表述為：假如p是質數，且(a,p)=1，那么a^p ≡a（mod p）。
