扩展欧拉定理(降幂公式)
你有没有遇到过这样的问题:要计算 2100 mod 62^{100} \bmod 62100mod6,222 和 666 不互质,欧拉定理说 aϕ(n)≡1(modn)a^{\phi(n)} \equiv 1 \pmod{n}aϕ(n)≡1(modn) 的前提是 aaa 和 nnn 互质,这里不满足,怎么办?有没有一个通用的公式,不管底数和模数是否互质,都能把大指数降下来?答案是有的,它就是 扩展欧拉定理,也叫 欧拉降幂公式。它就像一把万能钥匙,当欧拉定理失效时,它仍然能帮我们快速计算超大指数的模运算。
为什么需要扩展欧拉定理?
先回顾一下欧拉定理:如果 gcd(a,m)=1\gcd(a, m) = 1gcd(a,m)=1,那么 aϕ(m)≡1(modm)a^{\phi(m)} \equiv 1 \pmod{m}aϕ(m)≡1(modm)。 例如 3ϕ(10)=34=81≡1(mod10)3^{\phi(10)} = 3^4 = 81 \equiv 1 \pmod{10}3ϕ(10)=34=81≡1(mod10),确实成立。 但如果 gcd(a,m)≠1\gcd(a, m) \neq 1gcd(a,m)=1,比如 a=2,m=6a = 2, m = 6a=2,m=6,我们计算一下:
- ϕ(6)=2\phi(6) = 2ϕ(6)=2,如果套用欧拉定理,会认为 22≡1(mod6)2^2 \equiv 1 \pmod{6}22≡1(mod6),但实际 22=4≢1(mod6)2^2 = 4 \not\equiv 1 \pmod{6}22=4≡1(mod6)。
- 直接算 2100 mod 62^{100} \bmod 62100mod6,手工也能发现规律:21≡22^1 \equiv 221≡2,22≡42^2 \equiv 422≡4,23≡22^3 \equiv 223≡2,24≡42^4 \equiv 424≡4……偶数次幂得4,奇数次幂得2。100100100 是偶数,结果是4。
显然欧拉定理不适用了。扩展欧拉定理就是来解决这个问题的——它不要求 aaa 和 mmm 互质,统一给出了降幂公式。
扩展欧拉定理的内容
设 a,ma, ma,m 为正整数,bbb 为自然数(b≥0b \ge 0b≥0),则
ab≡{ab(modm)如果 b<ϕ(m)a(b mod ϕ(m))+ϕ(m)(modm)如果 b≥ϕ(m)a^b \equiv \begin{cases} a^b \pmod{m} & \text{如果 } b < \phi(m) \ a^{(b \bmod \phi(m)) + \phi(m)} \pmod{m} & \text{如果 } b \ge \phi(m) \end{cases}ab≡{ab(modm)a(bmodϕ(m))+ϕ(m)(modm)如果 b<ϕ(m)如果 b≥ϕ(m)
简单说:当指数 bbb 小于 ϕ(m)\phi(m)ϕ(m) 时,不能降幂,老老实实直接算(或者用快速幂)。 当指数 bbb 大于等于 ϕ(m)\phi(m)ϕ(m) 时,就可以用公式:先让指数对 ϕ(m)\phi(m)ϕ(m) 取余,然后加上 ϕ(m)\phi(m)ϕ(m),再用这个新指数去算。
为什么要加 ϕ(m)\phi(m)ϕ(m)? 因为当底数和模数不互质时,aϕ(m)a^{\phi(m)}aϕ(m) 不一定等于1,但可以证明:当指数足够大(大于等于 ϕ(m)\phi(m)ϕ(m))时,aka^kak 和 ak+ϕ(m)a^{k+\phi(m)}ak+ϕ(m) 模 mmm 相等。所以加一个 ϕ(m)\phi(m)ϕ(m),确保指数足够大,公式就成立。如果直接取模而不加,可能得到错误答案。
生活中的类比 ?
想象一下你在学校排队打饭。食堂有固定的窗口,每次只能打一份菜。你和食堂阿姨的“关系”就像是底数和模数:
- 如果你们互质(关系好),你每打一次饭,菜的种类完全不同,循环一圈正好回到起点(欧拉定理)。
- 如果不互质(关系不好),有些菜你永远打不到,但排队时间长了(指数够大),会出现循环。这个循环的长度就是 ϕ(m)\phi(m)ϕ(m) 的因子。当你已经排了至少 ϕ(m)\phi(m)ϕ(m) 次队后,再排一次就相当于加了一个循环,菜的种类不变。
所以加 ϕ(m)\phi(m)ϕ(m) 就像“多排一轮队”,保证你已经进入稳定循环。
另一个更形象的例子:翻课本。假设一本数学书有 mmm 页,你从第 1 页开始,每次翻 aaa 页(可能翻多本)。如果 aaa 和 mmm 互质,你最终能翻遍所有页。如果不互质,有些页永远翻不到。但当你翻页的次数足够多(超过 ϕ(m)\phi(m)ϕ(m) 次)后,翻页的模式就固定了。此时再多翻 ϕ(m)\phi(m)ϕ(m) 次,你又会回到同一页。扩展欧拉定理就是把“多翻”的这个规律提炼出来,让你不用真的翻那么多次,直接通过公式算出结果。
分情况讲解:什么时候用?怎么用?
情况1:指数 b<ϕ(m)b < \phi(m)b<ϕ(m)
直接计算。因为指数太小,降幂公式不成立。例如:
- 计算 21 mod 62^1 \bmod 621mod6,ϕ(6)=2\phi(6)=2ϕ(6)=2,1<21 < 21<2,直接算得 222。
- 如果强行用公式:2(1 mod 2)+2=23=8≡2(mod6)2^{(1 \bmod 2) + 2} = 2^{3} = 8 \equiv 2 \pmod{6}2(1mod2)+2=23=8≡2(mod6),竟然巧合相等,这是因为 bbb 很小,加上 ϕ(m)\phi(m)ϕ(m) 后指数变大,但结果不一定对,所以不能依赖巧合。一定要按条件判断。
情况2:指数 b≥ϕ(m)b \ge \phi(m)b≥ϕ(m)
用公式:先计算 r=b mod ϕ(m)r = b \bmod \phi(m)r=bmodϕ(m),然后新指数为 r+ϕ(m)r + \phi(m)r+ϕ(m),再算 ar+ϕ(m) mod ma^{r+\phi(m)} \bmod mar+ϕ(m)modm。
例1:2100 mod 62^{100} \bmod 62100mod6
- ϕ(6)=2\phi(6)=2ϕ(6)=2,100≥2100 \ge 2100≥2,r=100 mod 2=0r = 100 \bmod 2 = 0r=100mod2=0,新指数 0+2=20+2=20+2=2,22=42^2=422=4,结果4。✔️
例2:31000000000 mod 103^{1000000000} \bmod 1031000000000mod10
- ϕ(10)=4\phi(10)=4ϕ(10)=4,bbb 很大,1000000000 mod 4=01000000000 \bmod 4 = 01000000000mod4=0,新指数 0+4=40+4=40+4=4,34=81≡1(mod10)3^4=81 \equiv 1 \pmod{10}34=81≡1(mod10)。验证:3的幂模10周期是4(循环:3,9,7,1),正好整除,结果1。✔️
例3:5100 mod 125^{100} \bmod 125100mod12
- ϕ(12)=ϕ(22×3)=12×(1−12)×(1−13)=4\phi(12)=\phi(2^2 \times 3) = 12 \times (1-\frac12)\times(1-\frac13)=4ϕ(12)=ϕ(22×3)=12×(1−21)×(1−31)=4。
- b=100≥4b=100 \ge 4b=100≥4,100 mod 4=0100 \bmod 4 = 0100mod4=0,新指数 0+4=40+4=40+4=4,54=6255^4=62554=625,625 mod 12=1625 \bmod 12 = 1625mod12=1。
- 验证:直接计算 51=55^1=551=5,52=25≡15^2=25\equiv152=25≡1,53=55^3=553=5,周期2,100是偶数,结果确实1。✔️
新手最容易犯的错误 ?
错误1:忘记判断 bbb 是否 ≥ϕ(m)\ge \phi(m)≥ϕ(m),不论大小直接降幂
比如计算 21 mod 62^1 \bmod 621mod6,如果直接套用公式:1 mod 2=11 \bmod 2 = 11mod2=1,指数变为 1+2=31+2=31+2=3,得 23=8≡22^3=8\equiv223=8≡2,结果碰巧对了。但如果是 22 mod 62^2 \bmod 622mod6:b=2≥ϕ(6)=2b=2 \ge \phi(6)=2b=2≥ϕ(6)=2,公式正确:2 mod 2=02 \bmod 2 =02mod2=0,指数 0+2=20+2=20+2=2,得 444。 但假如换一个例子:41 mod 94^1 \bmod 941mod9,ϕ(9)=6\phi(9)=6ϕ(9)=6,1<61 < 61<6,应该直接算 4≡44\equiv44≡4。如果错误降幂:1 mod 6=11\bmod6=11mod6=1,指数 1+6=71+6=71+6=7,47≡41⋅46≡4×46(mod9)4^7 \equiv 4^1 \cdot 4^6 \equiv 4 \times 4^6 \pmod{9}47≡41⋅46≡4×46(mod9),464^646 用欧拉定理?但4和9互质(gcd=1),46≡14^6 \equiv 146≡1,所以 47≡44^7 \equiv 447≡4,竟然又对了?注意:这里底数和模数互质,欧拉定理成立,指数加 ϕ(m)\phi(m)ϕ(m) 不影响结果,所以碰巧正确。但如果不互质且指数很小时,就会出错。例如 21 mod 82^1 \bmod 821mod8:ϕ(8)=4\phi(8)=4ϕ(8)=4,直接算 21=22^1=221=2;若错误用公式:1 mod 4=11\bmod4=11mod4=1,指数 1+4=51+4=51+4=5,25=32≡0(mod8)2^5=32\equiv0 \pmod{8}25=32≡0(mod8),但正确答案是2!所以必须严格判断。
错误2:认为公式对所有 bbb 都成立,不加 ϕ(m)\phi(m)ϕ(m)
有人觉得直接取模就行了:ab≡ab mod ϕ(m)(modm)a^b \equiv a^{b \bmod \phi(m)} \pmod{m}ab≡abmodϕ(m)(modm)。这在互质时是对的(因为 aϕ(m)≡1a^{\phi(m)} \equiv 1aϕ(m)≡1),但不互质时错误。比如 2100 mod 62^{100} \bmod 62100mod6,直接取模 100 mod 2=0100\bmod2=0100mod2=0,得 20=12^0=120=1,但实际是4。所以必须加 ϕ(m)\phi(m)ϕ(m)。
错误3:计算 ϕ(m)\phi(m)ϕ(m) 时搞错
欧拉函数计算要分解质因数,注意公式:ϕ(n)=n∏(1−1p)\phi(n) = n \prod (1 - \frac{1}{p})ϕ(n)=n∏(1−p1)。例如 m=8=23m=8=2^3m=8=23,ϕ(8)=8×(1−1/2)=4\phi(8)=8 \times (1-1/2)=4ϕ(8)=8×(1−1/2)=4,不是 8/2=48/2=48/2=4 这么简单,但结果一样。对于 m=12m=12m=12,分解 22×32^2 \times 322×3,ϕ(12)=12×(1−1/2)×(1−1/3)=12×1/2×2/3=4\phi(12)=12 \times (1-1/2) \times (1-1/3)=12 \times 1/2 \times 2/3 = 4ϕ(12)=12×(1−1/2)×(1−1/3)=12×1/2×2/3=4。可以用程序计算,但手动时容易漏掉质因数。
错误4:处理超大指数 bbb 时,直接读入整数溢出
当 bbb 有几百位时,C++ 的 long long 放不下。正确做法是读入字符串,判断 bbb 是否小于 ϕ(m)\phi(m)ϕ(m)。如果 bbb 很长,可以先用字符串长度比较,或逐位比较;然后如果需要取模,也要用大数取模方法。
完整可运行的代码示例
下面给出两个语言的完整实现,都包含了判断条件和大指数处理。
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。如果长度相等,直接用字符串比较(因为数字长度一样,字典序等同于数值大小)。这里做了一个简单的判断,实际上还可以更严谨(比如先去除前导零),但对于一般输入足够。
扩展欧拉定理在竞赛中的应用
信息学竞赛中,经常出现求超大指数模的问题,比如计算 abc mod ma^{b^c} \bmod mabcmodm(幂塔)。这时需要递归地使用扩展欧拉定理:先对最外层指数用公式,内层又要处理指数上的指数,每次递归模数变为 ϕ(m),ϕ(ϕ(m)),…\phi(m), \phi(\phi(m)), \dotsϕ(m),ϕ(ϕ(m)),…,直到模数为1。因为 ϕ(1)=0\phi(1)=0ϕ(1)=0,此时任何数 mod 1 = 0,递归结束。这个过程称为 欧拉降幂递归。因为 ϕ(n)\phi(n)ϕ(n) 缩小得很快(至少减半),深度是 O(logn)O(\log n)O(logn),非常高效。
例如:计算 2345 mod 102^{3^{4^5}} \bmod 102345mod10,需要递归两次(模10→φ(10)=4→φ(4)=2→φ(2)=1)。如果你学会了单层降幂,多层只是重复使用而已。
相关知识点指引
- 欧拉函数:计算 ϕ(n)\phi(n)ϕ(n) 的方法是基础,需要掌握质因数分解。
- 欧拉定理:当 gcd(a,m)=1\gcd(a,m)=1gcd(a,m)=1 时,aϕ(m)≡1(modm)a^{\phi(m)} \equiv 1 \pmod{m}aϕ(m)≡1(modm)。
- 快速幂:用二分法在 O(logb)O(\log b)O(logb) 内计算 abmod ma^b \mod mabmodm。
- 中国剩余定理:扩展欧拉定理的证明有时会用到它,但不需要深入。
- RSA 加密:欧拉定理是 RSA 的理论支柱,扩展欧拉定理则用于解密过程中大指数的计算。
- 模运算的性质:例如 (a⋅b) mod m=((a mod m)⋅(b mod m)) mod m(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m(a⋅b)modm=((amodm)⋅(bmodm))modm。
掌握了这些,你就能游刃有余地处理各种指数爆炸的计算问题。数论就像搭积木,把每个小定理理解透彻,组合起来就能解决复杂问题。继续加油,你正在成为数学与编程小达人!