两个数论魔法：费马小定理和威尔逊定理

你是否想过，不用一个个试除，就能快速判断一个数是不是质数？或者，你知道为什么某些加密算法（比如RSA）能保证你的密码安全？这背后藏着两个神奇的“数学魔法”——费马小定理和威尔逊定理。它们就像数论世界的“超能力”，一个用分糖果的故事让你记住，一个用排队游戏让你理解。下面我们就边玩边学，再用C++代码亲手验证这些魔法。

1. 费马小定理：分糖果的“剩一颗”规律

核心思想：当你有一堆糖果（数量为 $a$ ），想分给 $p$ 个小朋友（ $p$ 必须是质数），而且 $a$ 不能被 $p$ 整除（也就是每人分不到整数颗）。那么，如果你把糖果数量取 $a$ 的 $p-1$ 次方，再除以 $p$ ，余数一定是 1！

用数学语言说：
若 $p$ 是质数，且 $\gcd(a, p) = 1$ （即 $a$ 与 $p$ 互质），则

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

举个具体例子

小朋友人数 $p = 7$ （质数），糖果数 $a = 2$ （2 不能被 7 整除）。
计算 $2^{7-1} = 2^6 = 64$ ，64 ÷ 7 = 9 余 1。果然余数为 1！
试试 $p = 5$ ， $a = 3$ ： $3^{4} = 81$ ，81 ÷ 5 = 16 余 1。
再试试 $p = 11$ ， $a = 5$ ： $5^{10} = 9765625$ ，除以 11 的余数是多少？用计算机算一下，也是 1！

为什么说它是“魔法”？

因为当 $p$ 很大时，直接计算 $a^{p-1}$ 会得到一个天文数字。但我们只需要余数，可以用快速幂（模运算）在电脑上瞬间算出来。这个特性被广泛用于：

快速判断质数（但不完美，见后文）
RSA加密：RSA 的安全性基于大数分解的困难，而加密/解密过程要用到费马小定理的推广——欧拉定理。
求乘法逆元：如果想找一个数 $x$ 使得 $a \cdot x \equiv 1 \pmod{p}$ ，那么 $x \equiv a^{p-2} \pmod{p}$ （因为 $a \cdot a^{p-2} = a^{p-1} \equiv 1$ ）。这在竞赛中经常用到。

2. 威尔逊定理：排队游戏的“循环节”秘密

核心思想：让 $p$ 个小朋友按编号 1, 2, 3, …, $p-1$ 排成一圈，把他们的编号全部乘起来，得到 $(p-1)!$ 。然后给这个乘积加上 1，问：加上 1 后的数能否被 $p$ 整除？只有 $p$ 是质数时，这个规律才成立。

用数学语言：
$p$ 是质数 当且仅当 $(p-1)! + 1 \equiv 0 \pmod{p}$ 。
换句话说， $(p-1)! \equiv -1 \pmod{p}$ 。

举个例子

$p = 5$ ： $(5-1)! = 4! = 24$ ， $24 + 1 = 25$ ，25 ÷ 5 = 5，余数为 0，所以 5 是质数。
$p = 7$ ： $6! = 720$ ，720 + 1 = 721，721 ÷ 7 = 103，整除，所以 7 是质数。
反例： $p = 4$ （合数）： $(4-1)! = 3! = 6$ ，6 + 1 = 7，7 ÷ 4 余 3，不是 0，说明 4 不是质数。
再试 $p = 6$ ： $5! = 120$ ，120 + 1 = 121，121 ÷ 6 余 1，不是 0。

为什么叫“排队游戏”？

想象小朋友们按顺序排成一圈，你会发现在质数的情况下，除了 1 和 $p-1$ 这两个“特殊小朋友”，其他小朋友都能两两配对，使得乘积模 $p$ 余 1（比如 2 × 3 = 6 ≡ 1 mod 5）。最后剩下的 1 和 $p-1$ 乘起来是 $p-1$ ，相当于 $-1$ 。所以整个乘积就是 $-1$ 模 $p$ 。把这个故事编成程序，就能用来验证质数。

很多同学觉得：如果 $a^{p-1} \equiv 1 \pmod{p}$ ，那么 $p$ 一定是质数。这是错的！ 有一些合数也能“骗过”这个测试，比如 $p = 341$ （341 = 11 × 31），取 $a = 2$ ，你会发现 $2^{340} \equiv 1 \pmod{341}$ ，但 341 是合数。这种合数叫 伪质数（Fermat pseudoprime）。所以费马小定理只能作为“可能是质数”的依据，不能100%确定。

错误2：忽略“a 和 p 互质”的条件

如果 $a$ 能被 $p$ 整除（比如 $a = 7, p = 7$ ），那么 $a^{p-1} \equiv 0 \pmod{p}$ ，而不是 1。所以使用费马小定理前，要确保 $\gcd(a,p)=1$ 。

错误3：直接计算大阶乘

威尔逊定理虽然优美，但计算 $(p-1)!$ 对于大 $p$ 极其耗时（需要 $p-1$ 次乘法），所以不能用来判断大质数。它更多用于理论证明和极小的质数验证。

4. 用 C++ 完整验证两个定理

下面我们写一段完整的程序，既用费马小定理做素性检验（注意它只能检测“可能是质数”），又用威尔逊定理真实验证小质数。为了直观，我们让用户输入一个数，然后分别用两种方法检查。

#include <iostream>
using namespace std;

// 快速幂函数：计算 a 的 b 次方模 m
long long pow_mod(long long a, long long b, long long m) {
    long long res = 1;          // 结果，初始为 1
    while (b > 0) {
        if (b & 1) {            // 如果当前二进制位是 1
            res = res * a % m;  // 乘上 a 并取模
        }
        a = a * a % m;          // a 平方并取模
        b >>= 1;                // b 右移一位
    }
    return res;
}

// 用费马小定理做素性检验（底数选 2 和 3，降低被伪质数欺骗的概率）
bool fermat_test(long long p) {
    if (p < 2) return false;          // 小于 2 不是质数
    if (p == 2 || p == 3) return true; // 2 和 3 是质数
    // 用两个底数 a = 2 和 a = 3 测试（对大多数小数足够）
    if (pow_mod(2, p - 1, p) != 1) return false;
    if (pow_mod(3, p - 1, p) != 1) return false;
    return true;  // 通过两个测试，可能是质数
}

// 用威尔逊定理验证质数（仅适合小 p）
bool wilson_test(long long p) {
    if (p < 2) return false;
    long long factorial = 1;            // 存储 (p-1)!
    for (long long i = 1; i < p; ++i) {
        factorial = factorial * i % p;  // 边乘边取模，避免溢出
    }
    // 威尔逊定理：(p-1)! ≡ -1 mod p 即 (p-1)! + 1 能被 p 整除
    return (factorial + 1) % p == 0;
}

int main() {
    long long n;
    cout << "请输入一个整数（不超过 10 万，否则威尔逊定理会非常慢）：";
    cin >> n;

    // 费马检验
    bool fermat_result = fermat_test(n);
    cout << "费马小定理检验（底数2和3）：";
    if (fermat_result)
        cout << n << " 可能是质数（注意可能有伪质数）" << endl;
    else
        cout << n << " 一定是合数" << endl;

    // 威尔逊检验（谨慎使用，n 太大时会卡死）
    if (n <= 10000) {  // 只对小范围使用，避免长时间计算
        bool wilson_result = wilson_test(n);
        cout << "威尔逊定理检验：";
        if (wilson_result)
            cout << n << " 是质数（威尔逊定理准确）" << endl;
        else
            cout << n << " 是合数" << endl;
    } else {
        cout << "n 太大，不进行威尔逊检验（计算太慢）" << endl;
    }

    return 0;
}

运行示例：

请输入一个整数（不超过 10 万，否则威尔逊定理会非常慢）：7
费马小定理检验（底数2和3）：7 可能是质数（注意可能有伪质数）
威尔逊定理检验：7 是质数（威尔逊定理准确）

请输入一个整数：341
费马小定理检验（底数2和3）：341 可能是质数（注意可能有伪质数）
威尔逊定理检验：341 是合数

你看，对于 341（等于 11×31），费马检验误判了（因为 $2^{340} \equiv 1 \mod 341$ ），而威尔逊定理正确识别它是合数。所以不要完全依赖费马小定理，但如果改用多个底数（比如 Miller–Rabin 检验），准确性会大大提高。

5. 相关知识点指引

欧拉定理：费马小定理的推广，当模数不是质数时， $a^{\varphi(n)} \equiv 1 \pmod{n}$ ，其中 $\varphi(n)$ 是欧拉函数。RSA 加密的核心就是这个。
Miller–Rabin 素性检验：改进了费马检验，用多个底数和二次探测，是目前最常用的概率性素性检验方法（CSP-S 可能会考）。
乘法逆元：利用费马小定理求模质数下的逆元，是组合数学（如计算大组合数取模）的必备技能。
中国剩余定理：另一个经典的数论工具，常与费马小定理结合解题。

这两个定理就像数论世界的“两块积木”，掌握了它们，你就能搭建更复杂的数学城堡。下次遇到判断质数、加密解密、求解同余方程的问题，别忘了这些神奇的“魔法”哦！

费马小定理与威尔逊定理