费马小定理与模逆元——用数学“反着来”解决除法问题

你有没有遇到过这种情况：在数学课上，老师让你计算 3 乘以几等于 1？你马上想到 3 × 1/3 = 1，但 1/3 是个小数，在编程的世界里，我们常常只允许整数。今天我们要讲的是在一个“循环”的数字世界里，如何找到一个整数，让它和另一个数相乘后结果等于 1。这个整数就叫模逆元（Modular Inverse），它就像一把“反着用的钥匙”，能帮我们把除法变成乘法。而费马小定理（Fermat's Little Theorem）就是快速打造这把钥匙的神奇方法。

一、从“找零钱”到“模逆元”

想象你有一个神奇的自动售货机：你投入1元硬币，它会吐出一颗糖。但你只有一张10元纸币，于是你投进去，机器应该找回9个1元硬币。可是这台机器有点怪——它只会找零，而且找零的数量必须满足某种“循环规律”。

假如这个机器只认识1到12的数字（像钟表），投入10元，它应该找“-9元”？不对，因为负数在钟表里可以表示为+3（因为从10往前数9格，相当于往后数3格，10+3=13→1）。这里的关键是：找到一个数x，使得 (10 + x) mod 12 = 1。那么x = 3。更一般地说，如果投入a元，想得到1颗糖，需要找零x，使得 (a + x) ≡ 1 (mod m)。这个x就是a的模加法逆元。

但今天我们关心的不是加法，而是乘法。比如一个加密系统里，你需要对数字进行乘法运算，然后解密时需要一个“乘法逆”把结果变回去。例如：在模7的世界里，3乘以某个数等于1 mod 7，这个数就是3的模逆元，因为3×5=15≡1 mod 7，所以5是3模7的逆元。

这种“逆元”在密码学、RSA算法、快速幂运算中无处不在。而计算逆元的一种高效方法，就是利用费马小定理——前提是模数是一个素数。

二、复习：什么是同余和模运算

在正式讲定理前，我们先复习几个重要概念，这些是理解模逆元的基础。

同余：如果两个整数a和b除以m的余数相同，就说a与b模m同余，记作 a ≡ b (mod m)。例如 17 ≡ 3 (mod 7)，因为17÷7=2余3，3÷7=0余3。再比如，今天星期一是1，那么8天后是星期几？8 mod 7 = 1，所以还是星期一。同余就是“在钟表世界看时间”。

模逆元：给定整数a和正整数m，如果存在整数x使得 a·x ≡ 1 (mod m)，则称x为a模m的逆元，记作 x = a⁻¹ mod m。逆元存在的条件是a与m互质（最大公约数为1）。如果m是素数，那么只要a不是m的倍数（即a mod m ≠ 0），就一定有逆元。

为什么需要逆元？ 在编程中处理大整数除法时，直接除以一个数会得到小数，而在模运算世界里，我们只能用乘法来模拟除法。比如计算 (b / a) mod m，可以转化为 b 乘以 a 的逆元再取模：因为 b * a⁻¹ ≡ b / a (mod m) （假设a与m互质）。举个例子：你想知道 10 ÷ 3 在模7的世界里等于几？直接除不行的，因为 10/3 不是整数。但我们可以先找3模7的逆元（是5），然后计算 10 × 5 mod 7 = 50 mod 7 = 1，所以 10 ÷ 3 ≡ 1 (mod 7)。验证：3 × 1 = 3，并不等于10？注意，这里的“除法”是在模意义下，意思是找到一个数 x 使得 3x ≡ 10 (mod 7)。因为 3×1=3≠10，3×5=15≡1，3×6=18≡4，3×7=21≡0，都不等于10——等等，那我们刚才算的1是什么意思？实际上，我们算的是 10 × (3⁻¹) = 10 × 5 = 50 ≡ 1 mod 7，这其实是 10/3 ≡ 1 mod 7。但我们可以验证：3 × 1 = 3 ≡ 10? 不，3 ≠ 10 mod 7。这里出现了混淆：实际上，模除法 b / a 的正确含义是求 x 使得 a·x ≡ b (mod m)，那么 x = b * a⁻¹ mod m。所以 10/3 mod 7 就是 x = 10 × 5 = 50 ≡ 1 mod 7。检查：3 × 1 = 3，而 3 并不等于 10 mod 7（10 mod 7 = 3）。哦！发现 3 × 1 = 3，而 10 mod 7 = 3，所以 3 ≡ 10 (mod 7) 是成立的！因为 10-3=7，可以被7整除。所以 10/3 ≡ 1 (mod 7) 是正确的，因为 3 × 1 = 3 ≡ 10 (mod 7)。完美！所以模逆元让我们能够用乘法替换除法。

三、费马小定理：快速求逆元的秘密武器

费马小定理是数论中的一个神奇结论，由皮埃尔·德·费马在1640年提出。它说：

如果p是一个素数，a是任意整数且不能被p整除（即p不整除a），那么 a^(p-1) ≡ 1 (mod p)。

让我们用一个简单例子验证：取p=7，a=3。计算 3^(7-1)=3^6=729。729÷7=104×7+1，余数为1。确实成立。

这个定理有什么用呢？如果我们把等式两边同时乘以a⁻¹（逆元），就能得到 a^(p-2) ≡ a⁻¹ (mod p)。因为 a·a^(p-2) = a^(p-1) ≡ 1，所以 a^(p-2) 恰好就是a模p的逆元！

于是，求逆元问题就转化为求一个数的幂次再取模。而幂次可以很大（p-2），但我们可以用快速幂算法在O(log p)时间内计算出来。

注意事项：这个方法只适用于p是素数的情况。如果p不是素数，则需要用扩展欧几里得算法。但在GESP竞赛中，模数常常是素数（比如10^9+7），所以费马小定理很实用。

直观理解：糖果分堆的比喻

假设有p个糖果要分给a个小朋友（p是素数），每个小朋友分到的糖果数相同且不能有剩余。因为p是素数，所以只有a=1或a=p时才能正好分完。如果a不是1或p，那么总是会有剩余。这个剩余数就是某种“循环”。

另一种直观：想象一个钟表上有p个刻度（1到p-1）。你每次走a步，走了一圈之后（走了p-1步），你会发现你回到了起点？费马小定理告诉我们，走p-1步后，你一定会回到起点（即余数为1）。

四、推导过程（简单版）

为了不让公式枯燥，我们用生活中的“糖果分堆”来比喻。

费马小定理的直观解释：考虑集合{1,2,...,p-1}，每个数乘以a再模p，会得到这些数的另一种排列（因为a与p互质，乘法是一个置换）。把所有乘积乘起来：1·2·...·(p-1) × a^(p-1) ≡ 1·2·...·(p-1) (mod p)。两边约去共同的乘积（因为每个数模p非零，可约去），得到 a^(p-1) ≡ 1 mod p。

这个证明需要群论概念，但小学生只需记住结论即可。你只需要知道：用这个定理，求逆元就变成了算 a^(p-2) mod p。

五、代码实战：用快速幂求逆元

既然逆元 = a^(p-2) mod p，我们只需要实现一个高效的幂运算。注意：直接循环乘p-2次会超时（如果p很大，比如10^9+7）。所以要使用快速幂（二分幂）思想。

快速幂原理：将指数写成二进制，例如计算3^13，13的二进制是1101，那么3^13 = 3^8 * 3^4 * 3^1。每次将底数平方，根据指数二进制位决定是否累乘。

下面分别用C++和Python实现。注意每行变量定义都写了中文注释，方便理解。

C++代码

#include <iostream>
using namespace std;

// 快速幂函数：计算 base^exp % mod
// 参数 base: 底数，exp: 指数，mod: 模数
long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;          // 存储结果，初始为1
    base = base % mod;             // 先将base取模，防止溢出
    while (exp > 0) {
        // 如果当前最低位为1，则乘上当前base
        if (exp & 1) {
            result = (result * base) % mod;
        }
        // base平方，指数右移一位
        base = (base * base) % mod;
        exp >>= 1;                 // exp = exp / 2
    }
    return result;
}

// 用费马小定理求 a 模 p 的逆元（p必须为素数）
// 返回 a^(p-2) mod p
long long mod_inverse_fermat(long long a, long long p) {
    // 注意：a不能是p的倍数，否则逆元不存在
    if (a % p == 0) {
        cout << "逆元不存在，因为a是p的倍数" << endl;
        return -1;   // 返回-1表示出错
    }
    return fast_pow(a, p - 2, p);
}

int main() {
    long long a, p;
    // 示例：求 3 模 7 的逆元
    a = 3;
    p = 7;
    long long inv = mod_inverse_fermat(a, p);
    cout << a << " 模 " << p << " 的逆元是 " << inv << endl;
    // 验证：3 * inv % 7 应该等于1
    cout << "验证：" << a << " * " << inv << " % " << p << " = " << (a * inv) % p << endl;

    // 另一个例子：模数是常见的素数 1000000007
    a = 10;
    p = 1000000007;
    inv = mod_inverse_fermat(a, p);
    cout << a << " 模 " << p << " 的逆元是 " << inv << endl;
    cout << "验证：" << (a * inv) % p << endl;
    return 0;
}

Python代码

def fast_pow(base, exp, mod):
    """
    快速幂：计算 base^exp % mod
    :param base: 底数
    :param exp: 指数
    :param mod: 模数
    :return: 计算结果
    """
    result = 1              # 存储结果，初始为1
    base = base % mod       # 防止base过大
    while exp > 0:
        # 如果exp二进制最低位是1，乘上当前base
        if exp & 1:
            result = (result * base) % mod
        # base平方，指数右移一位
        base = (base * base) % mod
        exp >>= 1           # 相当于exp //= 2
    return result

def mod_inverse_fermat(a, p):
    """
    用费马小定理求a模p的逆元（p必须为素数）
    返回 a^(p-2) % p
    """
    if a % p == 0:
        print("逆元不存在，因为a是p的倍数")
        return None
    return fast_pow(a, p - 2, p)

# 测试
a = 3
p = 7
inv = mod_inverse_fermat(a, p)
print(f"{a} 模 {p} 的逆元是 {inv}")
print(f"验证：{a} * {inv} % {p} = {(a * inv) % p}")

# 大素数例子
a = 10
p = 1000000007
inv = mod_inverse_fermat(a, p)
print(f"{a} 模 {p} 的逆元是 {inv}")
print(f"验证：{(a * inv) % p}")

运行输出：

3 模 7 的逆元是 5
验证：3 * 5 % 7 = 1
10 模 1000000007 的逆元是 700000005
验证：1

注意：10模1000000007的逆元是700000005，因为10 * 700000005 = 7000000050，模1000000007等于1（可以自己验证）。

六、新手容易犯的错误

忘了检查a能不能被p整除
如果a是p的倍数（比如a=14, p=7），那么 a mod p = 0，逆元不存在。因为0乘以任何数都不可能等于1模p。费马小定理要求p不整除a，所以需要先判断 if a % p == 0。
模数p不是素数就乱用费马小定理
很多人看到“费马小定理”就套用，但p必须是素数。比如 p=8（合数），a=3，计算 3^(8-2)=3^6=729，729 mod 8 = 1，这并不等于3模8的逆元（实际上3模8的逆元是3，因为3×3=9≡1 mod 8）。注意，这里巧合了，但大多数情况p不是素数时，a^(p-2) mod p 不等于逆元。正确的做法是用扩展欧几里得算法。
没有考虑负数的情况
如果a是负数，比如 a = -3，p=7，那么直接求 fast_pow(-3, p-2, p) 可能会出错。应该先调整：a = (a % p + p) % p，确保a在0到p-1之间。
快速幂中忘记取模
在乘法时如果不取模，结果会迅速溢出（尤其在C++中）。一定要每一步都 % mod。
指数写成 p-1 而不是 p-2
费马小定理给出 a^(p-1) ≡ 1，所以逆元是 a^(p-2)，不是 a^(p-1)。新手容易搞混。

七、生活中的密码锁与分数计算

比喻一：密码锁的“反相钥匙”
想象一个数字密码锁，它有一个“乘法运算”功能。你输入一个数字a，锁会返回a乘以某个秘密值再取模的结果。如果你知道锁的模数p是素数，并且知道输出结果，怎么还原a？你需要找到a的“乘法逆元”——其实就是一把反相钥匙，用它乘以输出结果就能解锁。费马小定理告诉我们，这把反相钥匙就是a^(p-2) mod p。所以通过快速幂，我们可以快速生成反相钥匙。

比喻二：分数计算
假设你在一个只能使用整数和模运算的游戏中，需要计算 5/2 的结果。模数是13（素数）。那么你要求2模13的逆元，利用费马小定理：2^(13-2)=2^11=2048，2048 mod 13 = 7，所以 5/2 ≡ 5×7 = 35 mod 13 = 9。验证：2×9=18≡5 mod 13，正确！这样你就能在整数世界里做“分数”计算了。

八、总结、练习与拓展

知识点	关键点
模逆元定义	a·x ≡ 1 (mod p) 的x
存在条件	gcd(a,p)=1，p为素数时自动满足
费马小定理	a^(p-1) ≡ 1 mod p
逆元公式	a⁻¹ ≡ a^(p-2) mod p
实现方法	快速幂（二进制拆分）和取模运算

思考题（动手试试）：

如果p=13，求5的模13逆元，用手算和程序验证。
提示：5^(13-2)=5^11，手动计算或者用快速幂。
如果p=11，求7的逆元，然后计算 (9/7) mod 11 的值。
注意：这里“/”是模意义下的除法，即解方程 7x ≡ 9 (mod 11)。
为什么费马小定理不能用于模数为15的情况？请举例说明。
提示：取a=2，p=15，计算2^(15-2) mod 15 = 2^13 mod 15 = ? 并和2模15的逆元比较。

拓展阅读：

扩展欧几里得算法：适用于非素数模数的逆元求解。
欧拉定理：费马小定理的推广，对任意模数m（a与m互质）有 a^φ(m) ≡ 1 (mod m)。
RSA算法原理：利用模逆元和费马小定理实现加密解密。

现在你已经掌握了用费马小定理求模逆元的核心方法，快去试试自己写代码计算大素数下的逆元吧！

例题精讲