本课时有配套视频讲解，购买后即可观看（永久有效）
威尔逊定理
一、课上练习
编程练习
（暂无）
二、知识总结
✨ 核心思想
威尔逊定理（Wilson's Theorem）是数论中一个优雅的定理，它给出了质数的一个充要条件：
一个正整数 p ≥ 2 是质数，当且仅当 (p-1)! ≡ -1 (mod p)。
等价表述：(p-1)! ≡ p-1 (mod p)，或者 (p-1)! + 1 ≡ 0 (mod p)。
虽然威尔逊定理在判定大数是否为质数时因为阶乘的计算量而不实用，但在某些数论推导和竞赛题中有重要应用。
✨ 定理内容与证明
定理
若 p 是质数，则 (p-1)! ≡ -1 (mod p)。
证明思路
当 p 是质数时，模 p 下的乘法群 {1, 2, ..., p-1} 中，每个元素都有唯一的逆元。
关键观察：大多数元素的逆元与自身不同。元素 a 满足 a ≡ a^(-1) (mod p) 当且仅当 a^2 ≡ 1 (mod p)，即 (a-1)(a+1) ≡ 0 (mod p)。因为 p 是质数，所以 a ≡ 1 或 a ≡ -1 ≡ p-1 (mod p)。
因此，在 {1, 2, ..., p-1} 中，除了 1 和 p-1 以外，其余元素可以两两配对（a 和 a^(-1) 配对），配对乘积为 1。
(p-1)! = 1 × 2 × ... × (p-1)
= 1 × (配对乘积全为1) × (p-1)
= 1 × 1 × (p-1)
= p-1
≡ -1 (mod p)逆定理
若 (n-1)! ≡ -1 (mod n) 且 n ≥ 2，则 n 是质数。
证明（反证法）：若 n 是合数，设 n = a × b（1 < a, b < n）。则 a 出现在 (n-1)! 的因子中，因此 a | (n-1)!。又因为 a | n，所以 (n-1)! mod n 应该能被 a 的某些因子整除，不可能等于 -1。
✨ 代码实现
验证威尔逊定理
wilson_verify.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6// 验证威尔逊定理：对质数 p，计算 (p-1)! mod p
7ll wilson_check(ll p) {
8 ll factorial = 1;
9 for (ll i = 2; i < p; i++) {
10 factorial = factorial * i % p;
11 }
12 return factorial; // 如果 p 是质数，结果应为 p-1（即 -1 mod p）
13}
14
15// 利用威尔逊定理判断质数（仅适用于小数，效率低）
16bool is_prime_wilson(ll n) {
17 if (n < 2) return false;
18 if (n == 2) return true;
19
20 ll factorial = 1;
21 for (ll i = 2; i < n; i++) {
22 factorial = factorial * i % n;
23 }
24 return factorial == n - 1; // (n-1)! ≡ -1 (mod n)
25}
26
27int main() {
28 ios::sync_with_stdio(false);
29 cin.tie(nullptr);
30
31 // 验证前几个质数
32 vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23};
33 for (int p : primes) {
34 ll result = wilson_check(p);
35 cout << "(p=" << p << ") (p-1)! mod p = " << result
36 << " , p-1 = " << p - 1
37 << (result == p - 1 ? " ✓" : " ✗") << "\n";
38 }
39
40 cout << "\n测试合数：\n";
41 vector<int> composites = {4, 6, 8, 9, 10, 12, 15};
42 for (int n : composites) {
43 ll result = wilson_check(n);
44 cout << "(n=" << n << ") (n-1)! mod n = " << result
45 << (result == n - 1 ? " (像质数?)" : " (合数)") << "\n";
46 }
47
48 return 0;
49}应用：求 (n! mod p) 中 p 是质数的情况
wilson_application.cpp
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6// 快速幂
7ll power(ll base, ll exp, ll mod) {
8 ll result = 1;
9 base %= mod;
10 while (exp > 0) {
11 if (exp & 1) result = result * base % mod;
12 base = base * base % mod;
13 exp >>= 1;
14 }
15 return result;
16}
17
18// 利用威尔逊定理：已知 (p-1)! ≡ -1 (mod p)
19// 可以推导出 (p-2)! ≡ 1 (mod p)
20// 更一般地：(p-k-1)! ≡ (-1)^k * inv((p-1)(p-2)...(p-k)) (mod p)
21
22// 当 n 接近 p 时，利用威尔逊定理从 (p-1)! 反推 n!
23// n! mod p = (p-1)! / ((n+1)(n+2)...(p-1)) mod p
24// = (-1) * inv((n+1)(n+2)...(p-1)) mod p
25ll factorial_near_p(ll n, ll p) {
26 if (n >= p) return 0; // p | n!
27
28 // 从 (p-1)! = -1 反推
29 // n! = (p-1)! / ((n+1)(n+2)...(p-1))
30 // n! = -1 * inv(product) mod p
31
32 ll product = 1;
33 for (ll i = n + 1; i < p; i++) {
34 product = product * i % p;
35 }
36
37 // n! ≡ -1 * inv(product) ≡ (p-1) * inv(product) (mod p)
38 ll inv_product = power(product, p - 2, p);
39 return (p - 1) * inv_product % p;
40}
41
42int main() {
43 ios::sync_with_stdio(false);
44 cin.tie(nullptr);
45
46 ll p = 97; // 一个质数
47
48 // 验证：当 n 接近 p 时
49 cout << "p = " << p << "\n";
50 for (ll n = p - 5; n < p; n++) {
51 ll result = factorial_near_p(n, p);
52 cout << n << "! mod " << p << " = " << result << "\n";
53 }
54
55 return 0;
56}✨ 执行示例
验证 p = 7
(7-1)! = 6! = 720
720 mod 7 = 720 - 102*7 = 720 - 714 = 6
6 = 7 - 1 = -1 (mod 7) ✓配对过程：
- 1 的逆元是 1（自身）
- 6 的逆元是 6（自身，因为 6 ≡ -1）
- 2 的逆元是 4（因为 2×4 = 8 ≡ 1 mod 7）
- 3 的逆元是 5（因为 3×5 = 15 ≡ 1 mod 7）
所以：6! = 1 × (2×4) × (3×5) × 6 = 1 × 1 × 1 × 6 = 6 ≡ -1 (mod 7)
验证 n = 4（合数）
(4-1)! = 3! = 6
6 mod 4 = 2
2 ≠ 3 (即 4-1)
所以 4 不是质数 ✓验证 n = 6（合数）
(6-1)! = 5! = 120
120 mod 6 = 0
0 ≠ 5 (即 6-1)
所以 6 不是质数 ✓✨ 解题步骤详解
- 识别威尔逊定理的应用场景：
- 题目涉及
(p-1)!或接近p的阶乘。 - 需要证明某个数是质数。
- 需要从
(p-1)!反推较小阶乘的模值。
- 题目涉及
- 直接应用：
(p-1)! mod p = p-1。 - 反向推导：利用
n! = (p-1)! / ((n+1)(n+2)...(p-1))在模 p 下计算。 - 结合逆元：反向推导中的除法需要用模逆元实现。
- 特殊推论：
(p-2)! ≡ 1 (mod p)（因为(p-1)! = (p-1) × (p-2)!，而(p-1) ≡ -1）- 当 p > 2 时，
((p-1)/2)!^2 ≡ (-1)^((p+1)/2) (mod p)
✨ 常见错误
- 用威尔逊定理判大数质数：计算 (n-1)! 需要 O(n) 时间，对于大数（>10^8）完全不可行。应使用 Miller-Rabin 等算法。
- 忘记 n ≥ p 时 n! mod p = 0：当 n ≥ p 时，n! 包含因子 p，所以 n! mod p = 0。
- 混淆 ≡ -1 和 ≡ 1：威尔逊定理是
(p-1)! ≡ -1，不是 1。类似的(p-2)! ≡ 1。 - 对合数误用定理：威尔逊定理的逆向使用——如果
(n-1)! mod n ≠ n-1，则 n 一定是合数。 - 溢出问题：计算阶乘时每一步都要取模，避免中间结果溢出。
✨ 算法评价
| 指标 | 值 |
|---|---|
| 理论价值 | 极高，是质数的充要条件 |
| 实用价值 | 有限，主要用于数学推导和特定竞赛题 |
| 时间复杂度 | 直接计算阶乘 O(p)，不适合大数 |
| 竞赛应用 | 推导阶乘相关恒等式、构造题 |
威尔逊定理虽然在实际计算中效率不高，但它揭示了质数与阶乘之间的深刻联系。在竞赛中，它常作为数学推导的工具出现，帮助简化涉及阶乘和质数模运算的问题。