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}

參見编辑

您使用了广告屏蔽软件!


Wikia通过广告运营为用户提供免费的服务。我们对用户通过嵌入广告屏蔽软件访问网站进行了使用调整。

如果您使用了广告屏蔽软件,将无法使用我们的服务。请您移除广告屏蔽软件,以确保页面正常加载。