扩展欧拉定理（降幂公式）详解：不怕大指数，不怕不互质

你有没有遇到过这样的问题：要计算 $2^{100} \bmod 6$，$2$ 和 $6$ 不互质，欧拉定理说 $a^{\phi(n)} \equiv 1 \pmod{n}$ 的前提是 $a$ 和 $n$ 互质，这里不满足，怎么办？有没有一个通用的公式，不管底数和模数是否互质，都能把大指数降下来？答案是有的，它就是 扩展欧拉定理，也叫 欧拉降幂公式。它就像一把万能钥匙，当欧拉定理失效时，它仍然能帮我们快速计算超大指数的模运算。

为什么需要扩展欧拉定理？

先回顾一下欧拉定理：如果 $\gcd(a, m) = 1$，那么 $a^{\phi(m)} \equiv 1 \pmod{m}$。
例如 $3^{\phi(10)} = 3^4 = 81 \equiv 1 \pmod{10}$，确实成立。
但如果 $\gcd(a, m) \neq 1$，比如 $a = 2, m = 6$，我们计算一下：

• $\phi(6) = 2$，如果套用欧拉定理，会认为 $2^2 \equiv 1 \pmod{6}$，但实际 $2^2 = 4 \not\equiv 1 \pmod{6}$。
• 直接算 $2^{100} \bmod 6$，手工也能发现规律：$2^1 \equiv 2$，$2^2 \equiv 4$，$2^3 \equiv 2$，$2^4 \equiv 4$……偶数次幂得4，奇数次幂得2。$100$ 是偶数，结果是4。

显然欧拉定理不适用了。扩展欧拉定理就是来解决这个问题的——它不要求 $a$ 和 $m$ 互质，统一给出了降幂公式。

扩展欧拉定理的内容

设 $a, m$ 为正整数，$b$ 为自然数（$b \ge 0$），则

简单说：当指数 $b$ 小于 $\phi(m)$ 时，不能降幂，老老实实直接算（或者用快速幂）。
当指数 $b$ 大于等于 $\phi(m)$ 时，就可以用公式：先让指数对 $\phi(m)$ 取余，然后加上 $\phi(m)$，再用这个新指数去算。

为什么要加 $\phi(m)$？
因为当底数和模数不互质时，$a^{\phi(m)}$ 不一定等于1，但可以证明：当指数足够大（大于等于 $\phi(m)$）时，$a^k$ 和 $a^{k+\phi(m)}$ 模 $m$ 相等。所以加一个 $\phi(m)$，确保指数足够大，公式就成立。如果直接取模而不加，可能得到错误答案。

生活中的类比 ?

想象一下你在学校排队打饭。食堂有固定的窗口，每次只能打一份菜。你和食堂阿姨的“关系”就像是底数和模数：

• 如果你们互质（关系好），你每打一次饭，菜的种类完全不同，循环一圈正好回到起点（欧拉定理）。
• 如果不互质（关系不好），有些菜你永远打不到，但排队时间长了（指数够大），会出现循环。这个循环的长度就是 $\phi(m)$ 的因子。当你已经排了至少 $\phi(m)$ 次队后，再排一次就相当于加了一个循环，菜的种类不变。

所以加 $\phi(m)$ 就像“多排一轮队”，保证你已经进入稳定循环。

另一个更形象的例子：翻课本。假设一本数学书有 $m$ 页，你从第 1 页开始，每次翻 $a$ 页（可能翻多本）。如果 $a$ 和 $m$ 互质，你最终能翻遍所有页。如果不互质，有些页永远翻不到。但当你翻页的次数足够多（超过 $\phi(m)$ 次）后，翻页的模式就固定了。此时再多翻 $\phi(m)$ 次，你又会回到同一页。扩展欧拉定理就是把“多翻”的这个规律提炼出来，让你不用真的翻那么多次，直接通过公式算出结果。

分情况讲解：什么时候用？怎么用？

情况1：指数 $b < \phi(m)$

直接计算。因为指数太小，降幂公式不成立。例如：

• 计算 $2^1 \bmod 6$，$\phi(6)=2$，$1 < 2$，直接算得 $2$。
• 如果强行用公式：$2^{(1 \bmod 2) + 2} = 2^{3} = 8 \equiv 2 \pmod{6}$，竟然巧合相等，这是因为 $b$ 很小，加上 $\phi(m)$ 后指数变大，但结果不一定对，所以不能依赖巧合。一定要按条件判断。

情况2：指数 $b \ge \phi(m)$

用公式：先计算 $r = b \bmod \phi(m)$，然后新指数为 $r + \phi(m)$，再算 $a^{r+\phi(m)} \bmod m$。

例1：$2^{100} \bmod 6$

• $\phi(6)=2$，$100 \ge 2$，$r = 100 \bmod 2 = 0$，新指数 $0+2=2$，$2^2=4$，结果4。✔️

例2：$3^{1000000000} \bmod 10$

• $\phi(10)=4$，$b$ 很大，$1000000000 \bmod 4 = 0$，新指数 $0+4=4$，$3^4=81 \equiv 1 \pmod{10}$。验证：3的幂模10周期是4（循环：3,9,7,1），正好整除，结果1。✔️

例3：$5^{100} \bmod 12$

• $\phi(12)=\phi(2^2 \times 3) = 12 \times (1-\frac12)\times(1-\frac13)=4$。
• $b=100 \ge 4$，$100 \bmod 4 = 0$，新指数 $0+4=4$，$5^4=625$，$625 \bmod 12 = 1$。
• 验证：直接计算 $5^1=5$，$5^2=25\equiv1$，$5^3=5$，周期2，100是偶数，结果确实1。✔️

新手最容易犯的错误 ?

错误1：忘记判断 $b$ 是否 $\ge \phi(m)$，不论大小直接降幂

比如计算 $2^1 \bmod 6$，如果直接套用公式：$1 \bmod 2 = 1$，指数变为 $1+2=3$，得 $2^3=8\equiv2$，结果碰巧对了。但如果是 $2^2 \bmod 6$：$b=2 \ge \phi(6)=2$，公式正确：$2 \bmod 2 =0$，指数 $0+2=2$，得 $4$。
但假如换一个例子：$4^1 \bmod 9$，$\phi(9)=6$，$1 < 6$，应该直接算 $4\equiv4$。如果错误降幂：$1\bmod6=1$，指数 $1+6=7$，$4^7 \equiv 4^1 \cdot 4^6 \equiv 4 \times 4^6 \pmod{9}$，$4^6$ 用欧拉定理？但4和9互质（gcd=1），$4^6 \equiv 1$，所以 $4^7 \equiv 4$，竟然又对了？注意：这里底数和模数互质，欧拉定理成立，指数加 $\phi(m)$ 不影响结果，所以碰巧正确。但如果不互质且指数很小时，就会出错。例如 $2^1 \bmod 8$：$\phi(8)=4$，直接算 $2^1=2$；若错误用公式：$1\bmod4=1$，指数 $1+4=5$，$2^5=32\equiv0 \pmod{8}$，但正确答案是2！所以必须严格判断。

错误2：认为公式对所有 $b$ 都成立，不加 $\phi(m)$

有人觉得直接取模就行了：$a^b \equiv a^{b \bmod \phi(m)} \pmod{m}$。这在互质时是对的（因为 $a^{\phi(m)} \equiv 1$），但不互质时错误。比如 $2^{100} \bmod 6$，直接取模 $100\bmod2=0$，得 $2^0=1$，但实际是4。所以必须加 $\phi(m)$。

错误3：计算 $\phi(m)$ 时搞错

欧拉函数计算要分解质因数，注意公式：$\phi(n) = n \prod (1 - \frac{1}{p})$。例如 $m=8=2^3$，$\phi(8)=8 \times (1-1/2)=4$，不是 $8/2=4$ 这么简单，但结果一样。对于 $m=12$，分解 $2^2 \times 3$，$\phi(12)=12 \times (1-1/2) \times (1-1/3)=12 \times 1/2 \times 2/3 = 4$。可以用程序计算，但手动时容易漏掉质因数。

错误4：处理超大指数 $b$ 时，直接读入整数溢出

当 $b$ 有几百位时，C++ 的 long long 放不下。正确做法是读入字符串，判断 $b$ 是否小于 $\phi(m)$。如果 $b$ 很长，可以先用字符串长度比较，或逐位比较；然后如果需要取模，也要用大数取模方法。

完整可运行的代码示例

下面给出两个语言的完整实现，都包含了判断条件和大指数处理。

C++ 实现（适合 b 在 long long 范围内，但演示原理）

#include <iostream>
#include <cmath>
using namespace std;

// 快速幂：计算 a^b % m
long long quick_pow(long long a, long long b, long long m) {
    long long res = 1 % m;   // 结果，注意 m=1 时是0
    while (b) {
        if (b & 1)                    // 如果当前二进制位为1
            res = (res * a) % m;
        a = (a * a) % m;              // a 平方
        b >>= 1;                      // 右移一位
    }
    return res;
}

// 欧拉函数：返回 φ(n)
long long phi(long long n) {
    long long result = n;    // 初始为 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);
    return result;
}

// 扩展欧拉定理降幂计算 a^b % m
long long euler_pow(long long a, long long b, long long m) {
    if (m == 1) return 0;          // 任何数 mod 1 = 0
    long long phim = phi(m);
    // 如果 b < phim，直接快速幂
    if (b < phim) {
        return quick_pow(a, b, m);
    } else {
        // b >= phim，使用降幂公式：指数 = (b % phim) + phim
        long long exp = (b % phim) + phim;
        return quick_pow(a, exp, m);
    }
}

int main() {
    long long a, b, m;
    cout << "请输入 a, b, m (计算 a^b mod m): ";
    cin >> a >> b >> m;
    long long result = euler_pow(a, b, m);
    cout << a << "^" << b << " mod " << m << " = " << result << endl;
    return 0;
}

运行示例：

请输入 a, b, m (计算 a^b mod m): 2 100 6
2^100 mod 6 = 4

Python 实现（支持任意大指数 b，用字符串输入）

# 快速幂
def quick_pow(a, b, m):
    res = 1 % m
    while b:
        if b & 1:                # 当前位为1
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1                  # 右移
    return res

# 欧拉函数
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

# 扩展欧拉定理：b 可以是超大整数，用字符串输入
def euler_pow(a, b_str, m):
    if m == 1:
        return 0
    phim = phi(m)
    # 判断 b_str 表示的数是否小于 phim
    # 方法：先比较字符串长度，再逐位比较
    b_len = len(b_str)
    # 如果 b 的长度比 phim 的字符串长度小，肯定 < phim
    len_phim = len(str(phim))
    if b_len < len_phim:
        b = int(b_str)
        return quick_pow(a, b, m)
    # 如果长度相等，比较字符串大小
    if b_len == len_phim:
        if b_str < str(phim):   # 字符串比较，按字典序，注意数字长度相等时有效
            b = int(b_str)
            return quick_pow(a, b, m)
    # 此时 b >= phim
    # 计算 b % phim，因为 b 可能超大，用大数取模
    remainder = 0
    for ch in b_str:
        remainder = (remainder * 10 + int(ch)) % phim
    exp = remainder + phim
    return quick_pow(a, exp, m)

# 主程序
a = int(input("请输入 a: "))
b_str = input("请输入 b (可以是很大的整数): ")
m = int(input("请输入 m: "))
result = euler_pow(a, b_str, m)
print(f"{a}^{b_str} mod {m} = {result}")

运行示例：

请输入 a: 2
请输入 b (可以是很大的整数): 10000000000000000000000000000000000000
请输入 m: 6
2^10000000000000000000000000000000000000 mod 6 = 4

注意：Python 的 str(phim) 和 b_str 比大小，如果 b_str 长度大于 len_phim，直接认为 b >= phim。如果长度相等，直接用字符串比较（因为数字长度一样，字典序等同于数值大小）。这里做了一个简单的判断，实际上还可以更严谨（比如先去除前导零），但对于一般输入足够。

扩展欧拉定理在竞赛中的应用

信息学竞赛中，经常出现求超大指数模的问题，比如计算 $a^{b^c} \bmod m$（幂塔）。这时需要递归地使用扩展欧拉定理：先对最外层指数用公式，内层又要处理指数上的指数，每次递归模数变为 $\phi(m), \phi(\phi(m)), \dots$，直到模数为1。因为 $\phi(1)=0$，此时任何数 mod 1 = 0，递归结束。这个过程称为 欧拉降幂递归。因为 $\phi(n)$ 缩小得很快（至少减半），深度是 $O(\log n)$，非常高效。

例如：计算 $2^{3^{4^5}} \bmod 10$，需要递归两次（模10→φ(10)=4→φ(4)=2→φ(2)=1）。如果你学会了单层降幂，多层只是重复使用而已。

相关知识点指引

• 欧拉函数：计算 $\phi(n)$ 的方法是基础，需要掌握质因数分解。
• 欧拉定理：当 $\gcd(a,m)=1$ 时，$a^{\phi(m)} \equiv 1 \pmod{m}$。
• 快速幂：用二分法在 $O(\log b)$ 内计算 $a^b \mod m$。
• 中国剩余定理：扩展欧拉定理的证明有时会用到它，但不需要深入。
• RSA 加密：欧拉定理是 RSA 的理论支柱，扩展欧拉定理则用于解密过程中大指数的计算。
• 模运算的性质：例如 $(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$。

掌握了这些，你就能游刃有余地处理各种指数爆炸的计算问题。数论就像搭积木，把每个小定理理解透彻，组合起来就能解决复杂问题。继续加油，你正在成为数学与编程小达人！