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 次剩余