Wilson 定理

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

說明

威爾森定理敘述如下：

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

若$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, \cdots, n-1$構成$n$的一個完全剩餘系，且對於$1, 2, 3, \cdots, 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}$。

參見

• 質數
• 同餘

上下節

• 上一節：指數
• 下一節：k 次剩餘