费马小定理 - NOI提高级教程

📖 费马小定理：素数幂次定理

费马小定理 (Fermat's Little Theorem) 是数论中的一个重要定理，它不仅是寻找模逆元的强大武器，也是许多素性测试算法的基石。

📐 定理陈述

若 $p$ 为质数，且整数 $a$ 不是 $p$ 的倍数（即 $\gcd(a, p) = 1$），则有：

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

其等价形式为：对于任意整数 $a$，均有 $a^p \equiv a \pmod p$。

📐 模置换证明法 (The Permutation Proof)

考虑序列 $S = \{1, 2, \ldots, p-1\}$。我们将每个元素乘上底数 $a$ 后模 $p$，得到新集合：

$S' = \{1a \bmod p, \; 2a \bmod p, \; \ldots, \; (p-1)a \bmod p\}$

核心定理：$S'$ 也是集 $\{1, 2, \ldots, p-1\}$ 模 $p$ 下的一个置换（即一一映射且互不重复）。

因此，将两个集合的元素分别累乘所得的积模 $p$ 依然相等：

$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod p$

由于 $\gcd((p-1)!, p) = 1$，两边同时消去 $(p-1)!$，即证出：$a^{p-1} \equiv 1 \pmod p$。

质数 p:

底数 a:

选择参数 $p$ 和 $a$，点击“开始置换演示”可以查看置换的双射映射流光连线。

等价关系式 3^6 ≡ 1 (mod 7)

原集 S 累乘 6! = 720

置换集 S' 累乘 3^6 * 6! ≡ 720 (mod 7)

逆元 a^-1 mod p 3^5 ≡ 5

🔗 模置换射影映射双射图 (Bijection Mapping Canvas)

原数集 S

× a mod p

置换余数集 S'

// 快速幂算法 O(log p)
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

// 利用费马小定理求逆元：a^(p-2) mod p
long long getInverse(long long a, long long p) {
    return power(a, p - 2, p);
}

📋 置换推导历史步骤