在数论的浩瀚星空中，威尔逊定理（Wilson's Theorem）无疑是一颗璀璨的明珠。它由英国数学家约翰·威尔逊提出，后经拉格朗日严格证明。该定理建立了素数与阶乘之间深刻而优美的联系，是初等数论中判定素数的经典充要条件。
对于任意整数 n > 1，n 是素数的充分必要条件是：
(n-1)! ≡ -1 (mod n)
等价于 (n-1)! + 1 能被 n 整除。
如果 n 是合数且 n > 4，则 (n-1)! ≡ 0 (mod n)。
这意味着对于大多数合数，其阶乘模 n 的结果恒为 0，这是排除合数的强力工具。
虽然以威尔逊命名，但该定理最早由波斯数学家哈兹尼发现，后由拉格朗日给出第一个完整证明。它在现代密码学和大数分解领域仍有重要理论价值。
威尔逊定理之所以成为经典，不仅在于其形式简洁，更在于它揭示了乘法群 Z_n 的结构性质。在模 p 的剩余类环中，除了 1 和 -1 以外的元素都能两两配对互为逆元，最终只剩下 1 和 -1 相乘，从而得到 -1。这种对称性是理解原根和离散对数问题的关键入口。
本章节通过层层递进的威尔逊定理例题，展示如何在不同场景下灵活运用该定理。我们将从基础验证到复杂同余方程求解，逐步拆解解题思路。
题目： 利用 威尔逊定理 验证 5, 7, 11 是否为素数。
解析： 根据定理，若 n 为素数，则 (n-1)! ≡ -1 (mod n)。
4! = 2424 ÷ 5 = 4 ... 44 ≡ -1 (mod 5)，所以 5 是素数。✅6! = 720720 ÷ 7 = 102 ... 66 ≡ -1 (mod 7)，所以 7 是素数。✅10! = 36288003628800 mod 11。3628800 = 11 × 329890 + 10。题目： 验证 n = 4 和 n = 6 时的情况。
解析：
3! = 66 mod 4 = 22 ≠ -1 (mod 4)（因为 -1 ≡ 3）。符合定理，4 不是素数。5! = 120120 mod 6 = 00 ≠ -1 (mod 6)。符合定理，6 不是素数。注意：对于所有合数 n > 4，(n-1)! 必然能被 n 整除，即余数为 0。
题目： 求满足 x^2 ≡ -1 (mod p) 的解，其中 p 是形如 4k+3 的素数。
分析： 这是一个经典的数论陷阱题。我们需要结合 威尔逊定理 和费马小定理来判断解的存在性。
假设 x^2 ≡ -1 (mod p) 有解。
两边同时取 (p-1)/2 次幂：
x^(p-1) ≡ (-1)^((p-1)/2) (mod p)
根据费马小定理，x^(p-1) ≡ 1 (mod p)。
所以：1 ≡ (-1)^((p-1)/2) (mod p)
因为 p = 4k + 3，所以 (p-1)/2 = 2k + 1 是奇数。
(-1)^(奇数) = -1。
于是得到：1 ≡ -1 (mod p)
这意味着 p | 2，即 p = 2。
但这与 p = 4k+3 矛盾（除非 k 无解）。
结论：当 p ≡ 3 (mod 4) 时，方程 x^2 ≡ -1 (mod p) 无解。
关联思考： 如果 p ≡ 1 (mod 4)，则 (p-1)/2 为偶数，此时 1 ≡ 1 成立，方程必有解。这正是二次互反律的一个推论。
题目： 计算 20! mod 23。
解析： 23 是素数。根据 威尔逊定理：
22! ≡ -1 (mod 23)
展开 22!：
22 × 21 × 20! ≡ -1 (mod 23)
注意到 22 ≡ -1, 21 ≡ -2 (mod 23)。
代入得：
(-1) × (-2) × 20! ≡ -1 (mod 23)
2 × 20! ≡ -1 (mod 23)
2 × 20! ≡ 22 (mod 23)
两边除以 2（即乘以 2 的逆元，这里 2 的逆元是 12，因为 2×12=24≡1）：
20! ≡ 11 (mod 23)
或者更简单地：
20! ≡ -1/2 ≡ -1 × 12 ≡ -12 ≡ 11 (mod 23)。
题目： 设 p 为奇素数，求证：1 × 3 × 5 × ... × (p-2) ≡ (-1)^((p+1)/2) (mod p)。
证明思路： 本题考察的是双阶乘与 威尔逊定理 的结合。
(p-1)! = 1 × 2 × 3 × ... × (p-1) ≡ -1 (mod p)(p-1)! = [1 × 3 × ... × (p-2)] × [2 × 4 × ... × (p-1)](p-1)/2 个 2。2 × 4 × ... × (p-1) = 2^((p-1)/2) × [1 × 2 × ... × (p-1)/2]2^((p-1)/2) × ((p-1)/2)!2^((p-1)/2) ≡ (2/p) (mod p)。k ≡ -(p-k) (mod p)。2m 对应 -(p-2m)。k! × (p-1-k)! ≡ (-1)^(k+1) (mod p) 的性质），最终可证得结论。结论： 该公式展示了奇数阶乘在模素数下的特殊性质，是解决高难度数论竞赛题的利器。
除了作为纯数学理论的验证工具，威尔逊定理在现代计算机科学和密码学中也有着不可忽视的应用价值。
虽然直接使用 威尔逊定理 计算阶乘效率极低（O(n)），无法用于大数分解，但它为 Miller-Rabin 等概率算法提供了理论参照。在某些特定的伪随机数生成器设计中，利用 (p-1)! 的性质可以构造出具有良好统计特性的序列。
RSA 加密算法依赖于两个大素数 p 和 q 的生成。虽然生成过程不直接调用 威尔逊定理，但理解 威尔逊定理 有助于深入理解 Z_p 群的阶和结构，进而掌握欧拉函数 φ(n) 的计算原理。
在顶级编程竞赛中，常出现需要计算 n! mod m 的问题。当 m 为素数且 n ≥ m 时，答案直接为 0；当 n < m 时，需利用 威尔逊定理 倒推。例如已知 (m-1)! ≡ -1，求 (m-k)! mod m，只需连续除以 m-1, m-2...`即可。
威尔逊定理直接验证的时间复杂度为 O(p)，对于大数完全不适用。相比之下，Miller-Rabin 算法的时间复杂度仅为 O(k log³p)，在实际工程中占据绝对主导地位。
在解决“已知余数求原数”的问题时，威尔逊定理 提供了一种独特的逆向视角。通过将阶乘展开并利用逆元消去，可以将复杂的乘积问题转化为简单的线性同余问题。
对于非素数模数，威尔逊定理 也有其推广形式，这涉及到高斯整数和模 n 的原根的存在性讨论。
对于任意合数 n > 4，(n-1)! ≡ 0 (mod n)。这一性质非常有用，因为它提供了一个快速的合数判定法则：如果 (n-1)! mod n ≠ 0 且 ≠ -1，则该计算有误；如果等于 0，则 n 必为合数（n>4）。
当模数为 2p（p 为奇素数）时，(2p-1)! ≡ 0 (mod 2p)。这是因为 2p-1 的阶乘中包含了因子 2 和 p，显然能被 2p 整除。
威尔逊定理 实际上是欧拉定理 a^φ(n) ≡ 1 (mod n) 在特定情况下的体现。当 n=p 时，φ(p) = p-1，且乘法群 Z_p 是循环群，其元素的乘积即为 -1。
| 模数 n 类型 | (n-1)! mod n 的值 | 备注 |
|---|---|---|
| n = 1 | 0 | 定义特殊情况 |
| n = 2 | 1 ≡ -1 | 素数，符合定理 |
| n = 3 | 2 ≡ -1 | 素数，符合定理 |
| n = 4 | 2 | 合数，特例（不为 0） |
| n = 素数 p (p>2) | -1 | 标准威尔逊定理 |
| n = 合数 (n>4) | 0 | 一般规律 |
针对广大数学爱好者和学生在自学威尔逊定理过程中遇到的困惑，我们整理了以下深度解答。
尽管 威尔逊定理 是素数判定的充要条件，但其计算量巨大。计算 (p-1)! 需要进行 p-1 次乘法运算。对于大素数（如 100 位数字），其阶乘的位数天文数字般庞大，存储和计算都不现实。因此，实际应用中多采用 Miller-Rabin 素性测试 或 AKS 素性测试 等更高效算法。
两者都是关于素数的性质，但侧重点不同。费马小定理 关注的是幂运算：a^(p-1) ≡ 1 (mod p)，适用于任何与 p 互质的 a。威尔逊定理 关注的是阶乘：(p-1)! ≡ -1 (mod p)。费马小定理更容易计算，常用于加密；威尔逊定理结构更严谨，常用于理论证明。
如果 n ≥ p，结果直接为 0。如果 n < p 且 p 较小，直接循环计算。如果 p 很大但 n 接近 p（例如求 (p-k)! mod p），可以利用 威尔逊定理 倒推：
(p-1)! ≡ -1
(p-1)(p-2)...(p-k+1) × (p-k)! ≡ -1
将左边的大数取模后，求逆元即可得到 (p-k)!。这种方法可以将复杂度从 O(p) 降低到 O(k log p)。
非常常见。它是高中奥数（CMO）和大学数学建模的基础知识点。常出现在数论大题中，用于证明整除性、求解同余方程或构造反例。掌握其证明过程（特别是逆元的配对思想）是拿高分的关键。