威尔逊定理 - NOI提高级教程

📖 威尔逊定理：素数的阶乘准则

在数论中，威尔逊定理 (Wilson's Theorem) 给出了一个整数是素数的充分必要条件。虽然它在计算上效率不高，但在纯数论证明和公式推导中极其重要。

📐 定理定义与逆定理

定理内容：正整数 $p$ 是素数当且仅当：

$(p-1)! \equiv -1 \equiv p-1 \pmod p$

逆定理内容：若整数 $n > 4$ 为合数，则：

$(n-1)! \equiv 0 \pmod n$

其物理意义为，由于 $n$ 是合数，$(n-1)!$ 乘积中必然包含了 $n$ 的因数，导致它们的乘积能被 $n$ 整除。

📐 乘法逆元对消证明法

在模素数 $p$ 的意义下，每个元素 $x \in \{1, 2, \ldots, p-1\}$ 都存在唯一的一个乘法逆元 $y$ 使得 $xy \equiv 1 \pmod p$。

通过方程 $x^2 \equiv 1 \pmod p \implies (x-1)(x+1) \equiv 0 \pmod p$，可以证得仅有 $x = 1$ 和 $x = p-1$ 的乘法逆元是其自身。

因此，在求阶乘积 $(p-1)! = 1 \cdot 2 \cdot 3 \cdots (p-2) \cdot (p-1)$ 时，中间的项 $\{2, 3, \ldots, p-2\}$ 可以两两配对成逆元对，乘积全部化为 $1$。最终只留下 $1$ 和 $p-1$：

$(p-1)! \equiv 1 \cdot (1 \cdot 1 \cdots 1) \cdot (p-1) \equiv p-1 \equiv -1 \pmod p$

选择数值 p:

选择模数 $p$，点击“开始配对演示”查看乘法逆元的配对连线与抵消轨迹。

是否是质数是

阶乘值 (p-1)! 6! = 720

阶乘模余 (p-1)! mod p 6 ≡ -1 (mod 7)

自身逆元元素 {1, 6}

🕸️ 乘法逆元环形关联网络

自身逆元 (1 & p-1)

匹配逆元对

无逆元元素

// 基于威尔逊定理判定素数 (复杂度 O(N))
bool isPrimeWilson(long long n) {
    if (n <= 1) return false;
    long long fact = 1;
    for (int i = 1; i <= n - 1; i++) {
        fact = (fact * i) % n;
    }
    return fact == n - 1;
}

📋 配对抵消历史步骤