威爾遜定理

在初等數論中,威爾遜定理給出了判定一個自然數是否為素數的充分必要條件。即:若且唯若p為素數時:( p -1 )! ≡ -1 ( mod 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 )

必要性證明

證明:若p為質數,則p可整除(p-1)!+1。

方法一

p=2,命題顯然成立;

p=3,命題顯然成立;

假設B中被p除餘一的數是γa:

一若γ=1,則γa=a,它被p除余a,又因為a不等於1,所以γ=1不成立;

二若γ=p-1,則γa=(p-1)a,它被p除余p-a,又因為a不等於p-1,所以γ=p-1不成立;

由一二三知γ≠a且a,γ∈A。

a不同時,γ也相異;若a1≠a2, a1,a2∈A,且γa1≡γa2≡1(mod p),因,γa1,γa2∈B,而B中的元素關於mod p不同餘,可見a1≠a2,則γ1≠γ2。

即A中的每一個a均可找到與其配對的y,γ∈A使ay≡1(mod p),

又,a不同時,γ也相異。

因此,A中的偶數個(p-3個)元素可以分成(p-3)/2個二元組(a,y),每個二元組都滿足ay≡1(mod p),

∴ 1×2×3×4....(p-2)≡1(mod p)

p-1≡-1(mod p)

∴ (p-1)!≡-1(mod p)

從而p可整除(p-1)!+1

方法二

對於偶質數2,命題顯然成立;

對於奇質數,令a∈A={2,3,4.....p-2},則B={a,2a,3a,.....,(p-1)a}中不會有對於除數p同餘的兩個數;事實上αa,βa∈B,αa≡βa(mod p),則a|α-β|能被p整除,而a|α-β|∈B,B中的元素不可能被p除盡。於是B中被p除得的餘數形成集合{1,2,3,...,p-1}.

假設b中被p除餘一的數是γa:

一若γ=1,則γa=a,它被p除余a,所以γ=1不成立;

二若γ=p-1,則γa=(p-1)a,它被p除余a,所以γ=p-1不成立;

三若γ=a,則γa=a*a,由於a*a≡1(mod p),故應有a*a-1=(a+1)(a-1)≡0(mod p),這只能是a=1或a=p-1,此與a∈A矛盾,故不成立;

由一二三知γ≠a且a∈A。

a不同時,γ也相異;若a1≠a2, a1,a2∈A,且γa1≡γa2≡1(mod p),因,γa1,γa2∈B,而B中的元素關於mod p不同餘,可見a1≠a2,則γ1≠γ2。

依次取a為2,3,...,(p-1)/2;使γa≡1(mod p)的數γ分別為(p-1)/2+1,(p-1)/2+2,...,(p-1)/2,

即2*【(p-1)/2+1】≡3*【(p-1)/2+2】≡4*【(p-1)/2+3】≡...【(p-1)/2】*(p-2)≡1(mod p)

從而2*【(p-1)/2+1】*3*【(p-1)/2+2】*4*【(p-1)/2+3】*...*【(p-1)/2】*(p-2)≡1(mod p)

2*3*4*5*6*...*(p-2)≡1(mod p)

又p-1≡-1(mod p),則

(p-1)!=1*2*3*4*5*...*(p-2)*(p-1)≡-1(mod p)

從而p可整除(p-1)!+1

相關詞條

相關搜尋

熱門詞條

聯絡我們