FANDOM


威爾森定理是一個判別一個數是否為質數的方法,但在事實上此方法未必實用,因為判別的對象越來越大時,判定其階乘會越來越困難。

說明编辑

威爾森定理敘述如下:

對於任意正整數n,n是質數當且僅當$ (n-1)! \equiv -1\pmod{n} $時。

若n=2時,此定理可能會有問題,但當n=2時,$ 1 \equiv -1\pmod{2} $,故定理依舊可以成立。

證明编辑


此處所給之證明可能不嚴謹,或有所疏漏,還請大家校驗與修正


以下僅討論n>2的狀況:

若n是合數(即不是質數的數),則因n的每個因數及其乘方小於n-1(n的因數不可能等於n-1),而有$ n|(n-1)! $,且由n|(n-1)!可推出n為合數,故若n不為(n-1)!的因數,則n必須是質數。

若n是質數,則因1、2、3、‧‧‧、n-1構成n的一個完全剩餘系,且對於1、2、3、‧‧‧、n-1等皆有其逆元,且其逆元具唯一性,其中除1和n-1的逆元與自己相同外,其他數的逆元皆不同於自身(在模質數n的狀況下,若一個數x的逆元與自己同,則有$ x^2 \equiv 1\pmod{n} $,故有n|(x-1)(x+1),從中可得n|x-1或n|x+1,意即$ x \equiv 1\pmod{n} $$ x \equiv -1\pmod{n} $),且任意數與其逆元皆可包含於某個完全剩餘系中,加上同餘的乘法具交換性,因此,在將每個數與其逆元相乘後,只剩1與n-1未與其逆元相乘(1的逆元為1、n-1的逆元為n-1),故$ (n-1)! \equiv (n-1)\pmod{n} $,並因$ (n-1)\equiv -1\pmod{n} $,而有$ (n-1)! \equiv -1\pmod{n} $,故當n為質數時,$ (n-1)! \equiv -1\pmod{n} $

參見编辑