Wilson 定理是数论中的一个基本定理，它提供了一个判断一个数是否为素数的充分必要条件。该定理可以表述为：
对于任意正整数 p>1p > 1，pp 是素数当且仅当
(p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod p
证明
充分性：（反证法）如果 pp 不是素数，那么 pp 可以表示为两个因子的乘积，这两个因子都小于 pp。这意味着 (p−1)!(p-1)! 可以被 pp 整除，因此 (p−1)!≢−1(modp)(p-1)! \not\equiv -1 \pmod{p}。所以，如果 (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod{p}，pp 必须是素数。
必要性：如果 pp 是素数，那么模 pp 的整数乘法群是循环的，其中每个非零元素都有唯一的乘法逆元。除了 11 和 p−1p-1 外 (见下面证明)，其他元素可以两两配对，使得它们的乘积模 pp 同余于 11。因此，所有这些配对的乘积，再乘以 11 和 p−1p-1（它们的乘积模 pp 同余于 −1-1），将同余于 −1-1 模 pp。这就证明了如果 pp 是素数，那么 (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod{p}。
证明只有 11 和 −1-1 的逆是自身
若 pp 为素数，那么正整数 aa 模 pp 的逆就是 aa 本身当且仅当 a≡1a \equiv 1 或 a≡−1a \equiv -1.
证明：充分性显然，下面证明必要性：
aa 模 pp 的逆就是 aa 本身说明 a2≡1a^2 \equiv 1，所以 p∣a2−1p \mid a^2-1，所以 p∣(a+1)(a−1)p \mid (a+1)(a-1)，所以 p∣a+1p \mid a+1 或者 p∣a−1p \mid a-1，所以 a≡1a \equiv 1 或 a≡−1a \equiv -1.
使用原根证明
(p−1)!(p-1)! 可以写成：
(p−1)!≡g0×g1×g2×⋯×gp−2(modp).(p-1)! \equiv g^0 \times g^1 \times g^2 \times \dots \times g^{p-2} \pmod{p}.
(p−1)!≡g0+1+2+⋯+(p−2)(modp).(p-1)! \equiv g^{0+1+2+\dots+(p-2)} \pmod{p}.
(p−1)!≡g(p−2)(p−1)2(modp).(p-1)! \equiv g^{\frac{(p-2)(p-1)}{2}} \pmod{p}.
根据费马小定律，gp−1≡1 mod pg^{p-1}\equiv1\mathrm{~mod~}p，则 gp−12≡±1 mod pg^{\frac{p-1}{2}}\equiv\pm1\mathrm{~mod~}p，但 p−12<p\frac{p-1}{2}<p，因此 gp−12≢1 mod pg^{\frac{p-1}{2}}\not\equiv1\mathrm{~mod~}p，所以只能 gp−12≡−1 mod pg^{\frac{p-1}{2}}\equiv-1\mathrm{~mod~}p.
设 k=p−12k=\frac{p-1}{2}，gk≡−1g^k\equiv-1，则
(p−1)!=gk(2k−1)=(−1)2k−1=−1 mod p(p-1)!=g^{k(2k-1)}=(-1)^{2k-1}=-1\mathrm{~mod~}p
素数检测
对于任意正整数 p>1p > 1，如果 (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod p，那么 pp 是素数.
Wilson 定理可以用于素数检测，但是非常低效.
广义 Wilson 定理
对于素数 pp，有：
(−1)p−12(p−12!)2≡−1(modp)(-1)^{\frac{p-1}{2}} \left( \frac{p-1}{2}! \right)^2 \equiv -1 \pmod p
- 如果 p≡1(mod4)p \equiv 1 \pmod 4，则 (−1)p−12=1(-1)^{\frac{p-1}{2}} = 1。
- 如果 p≡3(mod4)p \equiv 3 \pmod 4，则 (−1)p−12=−1(-1)^{\frac{p-1}{2}} = -1。
证明
我们可以将 (p−1)!(p-1)! 分解为：
(p−1)!=(p−1)(p−2)(p−3)⋯2⋅1(p-1)! = (p-1)(p-2)(p-3) \cdots 2 \cdot 1
由于 p−1≡−1(modp)p-1 \equiv -1 \pmod p，我们可以重写这个式子为：
(p−1)!=(−1)(−2)(−3)⋯(−p−12)⋅1⋅2⋯(p−12)(p-1)! = (-1)(-2)(-3) \cdots \left( -\frac{p-1}{2} \right) \cdot 1 \cdot 2 \cdots \left( \frac{p-1}{2} \right)
这个式子的前半部分是 (−1)p−12(-1)^{\frac{p-1}{2}} 乘以 p−12!\frac{p-1}{2}! 的每个数字的负值，而后半部分是 (p−12)!\left( \frac{p-1}{2} \right)!。
所以：
(p−1)!=(−1)p−12(p−12!)2(p-1)! = (-1)^{\frac{p-1}{2}} \left( \frac{p-1}{2}! \right)^2
根据 Wilson 定理，将上述表达式代入，得到：
(−1)p−12(p−12!)2≡−1(modp)(-1)^{\frac{p-1}{2}} \left( \frac{p-1}{2}! \right)^2 \equiv -1 \pmod p