欧拉定理与费马小定理：从密码锁到幂模运算的利器

什么是欧拉定理？它用来做什么？

欧拉定理是数论中一个非常强大的工具，专门用来处理大幂模运算——也就是计算一个很大的数的幂除以另一个数后的余数。比如你想知道 $7^{222}$ 除以 10 余几，直接算会得到一个天文数字，但用欧拉定理几秒钟就能搞定。它还是现代密码学（如 RSA 加密）的理论基石之一，简单说就是：如果两个数互质，那么其中一个数的 φ(n) 次方模 n 等于 1。

为了讲清楚，我们先从两个生活中的小故事开始。

从两个小故事开始

故事一：密码锁的循环

想象你有一个密码锁，锁上有 n 个数字（0 到 n-1）。你每次旋转 a 格，那么重复操作多少次后，能恰好回到原点？这个问题的答案就和欧拉定理有关。

比如锁有 10 个档位（n=10），每次转 3 格。因为 3 和 10 互质（最大公约数是 1），根据欧拉定理，转 φ(10)=4 次后，位置会回到原点——实际上 3^4=81，81 mod 10=1，相当于转了 4 次就回到了初始档位。如果每次转 6 格，6 和 10 不互质，你就永远回不到原点（会陷入循环）。所以欧拉定理告诉了我们互质时回到原点的最少次数。

故事二：快速算幂的余数

再说一个具体问题：你想快速计算 $7^{222} \bmod 10$ （即 7 的 222 次方除以 10 的余数）。如果直接算， $7^{222}$ 是一个超级大的数，但利用欧拉定理，我们可以快速得到结果。怎么算？先卖个关子，下面慢慢讲。

核心概念：欧拉函数 φ(n)

欧拉定理中最重要的概念是欧拉函数 φ(n)，它表示小于等于 n 的正整数中与 n 互质的数的个数（互质就是最大公约数为 1）。举个简单的例子：

n = 10，小于等于 10 且与 10 互质的数有：1、3、7、9，共 4 个，所以 φ(10) = 4。
n = 7（质数），小于等于 7 且与 7 互质的数有：1、2、3、4、5、6，共 6 个，所以 φ(7) = 7-1 = 6。

对于质数 p，因为所有小于 p 的数都和它互质，所以 φ(p) = p-1。这个性质非常重要，因为费马小定理就是基于这个特例。

欧拉函数的计算方法

如果 n 可以分解成质因数的乘积 $n = p_1^{k_1} \times p_2^{k_2} \times \cdots$ ，那么 φ(n) 可以用公式计算：

φ(n) = n \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots

比如 n = 10 = 2 × 5，则 φ(10) = 10 × (1 - 1/2) × (1 - 1/5) = 10 × 1/2 × 4/5 = 4。

注意：公式中每个质因数只出现一次，即使质因数出现多次（如 12 = 2² × 3），写法也是 $n \times (1-\frac{1}{2}) \times (1-\frac{1}{3})$ 。

欧拉定理（Euler's Theorem）

定理内容：如果 a 和 n 互质（gcd(a, n) = 1），那么

a^{φ(n)} \equiv 1 \pmod{n}

其中 ≡ 表示同余，意思是 $a^{φ(n)}$ 除以 n 的余数等于 1。也就是说， $a^{φ(n)} \bmod n = 1$ 。

这个定理告诉我们，当 a 和 n 互质时，a 的 φ(n) 次幂模 n 的结果固定为 1。

直观理解（不严格但好记）

我们可以换个角度理解：考虑所有与 n 互质的数，一共 φ(n) 个，把它们叫做“互质集”。比如 n=10，互质集是 {1, 3, 7, 9}。如果取一个与 10 互质的数 a=3，我们把集合里的每个数都乘以 a 再模 10，得到：

1×3 = 3 → 3
3×3 = 9 → 9
7×3 = 21 → 1
9×3 = 27 → 7

结果变成了 {3, 9, 1, 7}，正好是原来集合的一个重排（顺序变了，但元素没变）。这意味着“乘以 a”这种操作相当于在互质集上做了一次置换。重复做 φ(n) 次（即乘以 a 的 φ(n) 次方），就会回到原来的顺序，相当于乘以 1。所以 $a^{φ(n)} \equiv 1$ 。

这个解释虽然不严格，但能帮你记住结论。

费马小定理：欧拉定理的“弟弟”

费马小定理说的是：如果 p 是质数，且 a 不是 p 的倍数（即 a 与 p 互质），那么

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

你看，费马小定理和欧拉定理形式完全一样，只不过费马小定理中 n 是质数 p，而欧拉函数 φ(p) = p-1，所以欧拉定理就变成了费马小定理。所以费马小定理是欧拉定理在 n 为质数时的特殊情况。

举例：p=7，a=3，那么 3^(7-1)=3^6=729，729 ÷ 7 = 104 × 7 + 1，余数为 1，确实成立。

对比表格

项目	费马小定理	欧拉定理
适用范围	n 是质数 p	n 是任意大于1的整数
条件	a 不是 p 的倍数（即 gcd(a,p)=1）	gcd(a,n)=1
结论	a^{p-1} ≡ 1 mod p	a^{φ(n)} ≡ 1 mod n
关系	费马小定理是欧拉定理的特例（当 n 为质数时 φ(p)=p-1）

所以，如果你背下了欧拉定理，费马小定理自然就记住了。而且欧拉定理在模为合数时也能用，更具一般性。

欧拉定理有什么用？

1. 化简幂模运算（核心应用）

利用欧拉定理，我们可以把大指数转换成小指数。

例子：计算 $7^{222} \bmod 10$
先求 φ(10)=4（因为 10=2×5，与 10 互质的数是 1,3,7,9 共 4 个）。7 与 10 互质，所以由欧拉定理， $7^4 \equiv 1 \pmod{10}$ 。
那么指数 222 = 4×55 + 2，所以

7^{222} = (7^4)^{55} \times 7^2 \equiv 1^{55} \times 49 \equiv 9 \pmod{10}

答案就是 9。是不是很快？如果直接算，7^222 有 188 位，人脑根本算不了。

另一个例子：计算 $3^{1000000} \bmod 7$
因为 7 是质数，φ(7)=6，且 3 与 7 互质，所以 $3^6 \equiv 1$ 。
1000000 ÷ 6 = 166666 余 4，所以 $3^{1000000} \equiv 3^4 = 81 \equiv 4 \pmod{7}$ 。答案就是 4。

2. 求模逆元

什么是模逆元？ 在模 n 下，如果 a 和 n 互质，那么存在一个数 x，使得 $a \times x \equiv 1 \pmod{n}$ ，这个 x 就叫做 a 的模 n 逆元。举个例子：在模 10 下，3 的逆元是 7，因为 3×7=21≡1。求逆元有什么用？在密码学中，加密时用 a，解密时就要用它的逆元。

欧拉定理直接给出了逆元的计算公式：

a^{φ(n)-1} \equiv a^{-1} \pmod{n}

因为 $a \times a^{φ(n)-1} = a^{φ(n)} \equiv 1$ 。所以逆元就是 $a^{φ(n)-1} \bmod n$ 。

例子：求 3 模 10 的逆元。φ(10)=4，所以 $3^{4-1}=3^3=27 \equiv 7 \pmod{10}$ ，逆元是 7，正确。

3. 素性检验（用费马小定理）

费马小定理可以用来快速判断一个数是否为质数（但要注意有“伪质数”存在，比如卡迈克尔数）。如果对于某个 a，a^{p-1} mod p 不等于 1，那么 p 一定是合数；如果等于 1，p 可能是质数，也可能是伪质数。但这种方法仍然很常用。

编程实现：验证欧拉定理

我们可以写程序，输入 a 和 n，判断是否互质，然后计算 a^{φ(n)} mod n 是否等于 1。这里需要用到快速幂（模幂运算），否则直接计算大整数会溢出或超时。

常见错误提醒（新手一定要看！）

忘记检查互质性：如果 a 和 n 不互质，欧拉定理不成立，直接套用会得到错误结果。
欧拉函数计算错误：对合数 n 分解时，要注意每个质因数只处理一次，而且分解要完整（比如 n=12=2²×3，计算 φ(12)=12×(1-1/2)×(1-1/3)=4，正确；漏掉指数会导致错误）。
快速幂中忘记取模：中间结果如果不取模，乘法会爆炸。
数据类型溢出：C++ 中 long long 在乘法时仍可能溢出，建议在乘法中加入模运算，或者使用 Python 的大整数（Python 无脑方便）。

C++ 代码示例

#include <iostream>
using namespace std;

// 快速幂：计算 a^b mod m
long long quick_pow(long long a, long long b, long long m) {
    long long res = 1;
    while (b) {
        if (b & 1)          // 如果当前二进制位为1
            res = (res * a) % m;
        a = (a * a) % m;    // a 自乘
        b >>= 1;            // 右移一位
    }
    return res;
}

// 最大公约数
long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 计算欧拉函数（质因数分解法）
long long phi(long long n) {
    long long result = n;
    long long temp = n;
    for (long long p = 2; p * p <= temp; p++) {
        if (temp % p == 0) {
            result = result / p * (p - 1);  // 一次处理一个质因数
            while (temp % p == 0) temp /= p; // 去除所有该质因数
        }
    }
    if (temp > 1) result = result / temp * (temp - 1); // 剩余质因数（大于sqrt(n)）
    return result;
}

int main() {
    long long a, n;
    cout << "请输入 a 和 n (a 和 n 互质才满足欧拉定理): ";
    cin >> a >> n;
    if (gcd(a, n) != 1) {
        cout << "a 和 n 不互质，欧拉定理不适用。" << endl;
        return 0;
    }
    long long phin = phi(n);
    long long result = quick_pow(a, phin, n);
    cout << "a^φ(n) mod n = " << a << "^" << phin << " mod " << n << " = " << result << endl;
    if (result == 1) {
        cout << "验证成功！欧拉定理成立。" << endl;
    } else {
        cout << "验证失败（不应该出现）" << endl;
    }
    return 0;
}

运行示例：

请输入 a 和 n (a 和 n 互质才满足欧拉定理): 7 10
a^φ(n) mod n = 7^4 mod 10 = 1
验证成功！欧拉定理成立。

Python 代码示例

# 快速幂
def quick_pow(a, b, m):
    res = 1
    while b:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res

# 最大公约数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 欧拉函数
def phi(n):
    result = n
    temp = n
    p = 2
    while p * p <= temp:
        if temp % p == 0:
            result = result // p * (p - 1)
            while temp % p == 0:
                temp //= p
        p += 1
    if temp > 1:
        result = result // temp * (temp - 1)
    return result

# 主程序
a = int(input("请输入 a: "))
n = int(input("请输入 n: "))
if gcd(a, n) != 1:
    print("a 和 n 不互质，欧拉定理不适用。")
else:
    phin = phi(n)
    result = quick_pow(a, phin, n)
    print(f"a^φ(n) mod n = {a}^{phin} mod {n} = {result}")
    if result == 1:
        print("验证成功！欧拉定理成立。")
    else:
        print("验证失败（不应该出现）")

运行示例（与C++相同）：

请输入 a: 7
请输入 n: 10
a^φ(n) mod n = 7^4 mod 10 = 1
验证成功！欧拉定理成立。

你也可以试着输入 a=3, n=7 来验证费马小定理（φ(7)=6，3^6 mod 7 = 1）。

拓展思考：欧拉定理的局限与下一步

欧拉定理有一个明显的限制：a 和 n 必须互质。如果 a 和 n 不互质（比如 a=2, n=10），那么 a^{φ(n)} mod n 不一定等于 1。那有没有办法在不互质时也化简幂模运算呢？这就是下一讲要学习的扩展欧拉定理（降幂公式），它可以在 a 和 n 不互质时仍然发挥威力，甚至能处理指数特别大的情况。

另外，欧拉定理还是RSA 加密算法的理论基础。在 RSA 中，我们选择两个大质数 p 和 q，令 n = p×q，则 φ(n) = (p-1)(q-1)。加密和解密分别用不同的指数，而欧拉定理保证了加密和解密能完美还原。如果你对密码学感兴趣，欧拉定理是必学的内容。

小结

欧拉定理：若 gcd(a,n)=1，则 $a^{φ(n)} \equiv 1 \pmod{n}$ 。
费马小定理是其特例：当 n 为质数 p 时，φ(p)=p-1，得到 $a^{p-1} \equiv 1 \pmod{p}$ 。
欧拉定理在快速计算大幂模、求模逆元等方面非常有用。
编程上需结合快速幂和欧拉函数实现验证，注意检查互质条件和数据类型。

现在，你可以用欧拉定理来快速计算像 $3^{1000000} \bmod 7$ 这样的问题了。不妨自己多找几个数字试一试，加深理解！

欧拉定理与费马小定理的关系