威尔逊定理

· · 算法·理论

1. 定理陈述

定理（Wilson's Theorem）
设 n \in \mathbb{N},\ n > 1，则

(n-1)! \equiv -1 \pmod{n}

成立 当且仅当 n 为素数。

等价地，若 p 为素数，则

p \mid (p-1)! + 1.

2. 证明

2.1 必要性：p 为素数 \Rightarrow (p-1)! \equiv -1 \pmod{p}

设 p 为素数，考虑模 p 的乘法群 \mathbb{Z}_p^\times = \{1, 2, \dots, p-1\}。

  1. 对任意 a \in \mathbb{Z}_p^\times，存在唯一逆元 a^{-1}，使得

    a \cdot a^{-1} \equiv 1 \pmod{p}.

  2. 若 a \equiv a^{-1} \pmod{p}，则 a^2 \equiv 1 \pmod{p}，即

    (a-1)(a+1) \equiv 0 \pmod{p}.

    由于 p 为素数，必有 a \equiv 1 或 a \equiv p-1 \pmod{p}。
    因此 仅有 1 与 p-1 是自身的逆元。

  3. 对其余元素 \{2, 3, \dots, p-2\}，可两两配对为 (a, a^{-1})，每对乘积模 p 同余于 1。

  4. 综上：

    \begin{aligned} (p-1)! &= 1 \cdot 2 \cdots (p-2) \cdot (p-1) \\ &\equiv 1 \cdot (p-1) \pmod{p} \\ &\equiv -1 \pmod{p}. \end{aligned}

2.2 充分性：(n-1)! \equiv -1 \pmod{n} \Rightarrow n 为素数

若 n 为合数且 n > 4，则存在因子 d\ (1 < d < n)，使得 d \mid (n-1)!，从而

(n-1)! \equiv 0 \pmod{d}.

若同时有 (n-1)! \equiv -1 \pmod{n}，则 -1 \equiv 0 \pmod{d}，矛盾。
直接验证 n = 4 不满足原式，故 n 必为素数。

3. 推论

4. 数值示例

验证 p = 5：

4! = 24,\quad 24 \bmod 5 = 4 \equiv -1 \pmod{5}.

定理成立。