逆元、费马小定理、欧拉定理 · 取模幂次方专项练习
适用场景：模运算中的降幂、求逆元、指数套娃。
核心前提：使用费马/欧拉定理前，务必确认底数与模数互质（否则需找规律或另寻他法）。
一、基础降幂（模数为质数，费马小定理）
定理：若 p 为质数，且 gcd(a, p) = 1，则
$
a^{p-1} \equiv 1 \pmod{p}
$
降幂时指数对 p-1 取模。
第 1 题（热身）
计算
$
3^{100} \bmod 11 = ?
$
第 2 题（指数较大）
计算
$
7^{2026} \bmod 13 = ?
$
第 3 题（底数较大）
计算
$
10^{50} \bmod 17 = ?
$
二、模数为合数（欧拉定理）
定理：若 gcd(a, n) = 1，则
$
a^{\varphi(n)} \equiv 1 \pmod{n}
$
降幂时指数对 φ(n) 取模。
第 4 题（模数 9，φ(9)=6）
计算
$
2^{100} \bmod 9 = ?
$
第 5 题（模数 14）
计算
$
5^{2025} \bmod 14 = ?
$
（先求 φ(14)）
三、指数套娃（外层指数降幂）
当指数本身是幂次时，如 a^{b^c}，需先将外层指数 b^c 对 φ(m) 取模（若模数为质数则对 p-1 取模）。
第 6 题
计算
$
2^{3^5} \bmod 7 = ?
$
第 7 题
计算
$
4^{2^{10}} \bmod 11 = ?
$
四、求逆元（除法转乘法）
若 m 为质数，则
$
a^{-1} \equiv a^{m-2} \pmod{m}
$
若 m 为合数且互质，则
$
a^{-1} \equiv a^{\varphi(m)-1} \pmod{m}
$
第 8 题
求 3 在模 10 下的乘法逆元。
第 9 题（综合）
计算
$
\frac{2}{3} \pmod{7}
$
即 2 × 3^{-1} mod 7。
五、陷阱题（不满足互质条件）
第 10 题
计算
$
6^{100} \bmod 8 = ?
$
注意：
gcd(6,8)=2，不能直接使用费马/欧拉定理。
详细答案解析
第 1 题解析
$
3^{100} \bmod 11
$
- 11 是质数，由费马小定理：
$
3^{10} \equiv 1 \pmod{11}
$
- 指数降幂：100 ≡ 0 (mod 10)，所以
$
3^{100} \equiv 3^0 = 1 \pmod{11}
$
答案：1
第 2 题解析
$
7^{2026} \bmod 13
$
- 13 是质数，
$
7^{12} \equiv 1 \pmod{13}
$
- 2026 ÷ 12 余 10（因为 12×168=2016），所以
$
7^{2026} \equiv 7^{10} \pmod{13}
$
- 计算：
$
7^2 = 49 \equiv 10 \pmod{13}
$
$
7^4 \equiv 10^2 = 100 \equiv 9 \pmod{13}
$
$
7^8 \equiv 9^2 = 81 \equiv 3 \pmod{13}
$
$
7^{10} = 7^8 \times 7^2 \equiv 3 \times 10 = 30 \equiv 4 \pmod{13}
$
答案：4
第 3 题解析
$
10^{50} \bmod 17
$
- 17 是质数，
$
10^{16} \equiv 1 \pmod{17}
$
- 50 ÷ 16 余 2，所以
$
10^{50} \equiv 10^2 = 100 \equiv 15 \pmod{17}
$
答案：15
第 4 题解析
$
2^{100} \bmod 9
$
- gcd(2,9)=1，且 φ(9)=6，由欧拉定理：
$
2^6 \equiv 1 \pmod{9}
$
- 100 ÷ 6 余 4，所以
$
2^{100} \equiv 2^4 = 16 \equiv 7 \pmod{9}
$
答案：7
第 5 题解析
$
5^{2025} \bmod 14
$
- 14 = 2 × 7，
$
\varphi(14) = 14 \times (1 - \frac12) \times (1 - \frac17) = 6
$
- gcd(5,14)=1，所以
$
5^6 \equiv 1 \pmod{14}
$
- 2025 ÷ 6 余 3，所以
$
5^{2025} \equiv 5^3 = 125 \equiv 13 \pmod{14}
$
答案：13
第 6 题解析
$
2^{3^5} \bmod 7
$
- 7 是质数，外层指数 3^5 需对 6 取模。
- 计算 3^5 mod 6：
$
3^1 = 3,\quad 3^2 = 9 \equiv 3 \pmod{6}
$
所以 3^5 ≡ 3 (mod 6)。
- 原式变为
$
2^3 \bmod 7 = 8 \bmod 7 = 1
$
答案：1
第 7 题解析
$
4^{2^{10}} \bmod 11
$
- 11 是质数，4^10 ≡ 1 (mod 11)，外层指数 2^10 对 10 取模。
- 2^10 = 1024，1024 ÷ 10 余 4。
- 原式变为
$
4^4 \bmod 11
$
计算：
$
4^2 = 16 \equiv 5 \pmod{11},\quad 4^4 = (4^2)^2 \equiv 5^2 = 25 \equiv 3 \pmod{11}
$
答案：3
第 8 题解析
求 3 关于模 10 的逆元。
- gcd(3,10)=1，φ(10)=4，由欧拉定理：
$
3^4 \equiv 1 \pmod{10}
$
- 逆元公式：
$
a^{-1} \equiv a^{\varphi(m)-1} \pmod{m}
$
所以
$
3^{-1} \equiv 3^{4-1} = 3^3 = 27 \equiv 7 \pmod{10}
$
- 验证：3 × 7 = 21 ≡ 1 (mod 10)，正确。
答案：7
第 9 题解析
计算
$
\frac{2}{3} \pmod{7}
$
- 7 是质数，求 3 的逆元：
$
3^{-1} \equiv 3^{7-2} = 3^5 \pmod{7}
$
- 计算：
$
3^2 = 9 \equiv 2,\quad 3^4 \equiv 4,\quad 3^5 = 3^4 \times 3 \equiv 4 \times 3 = 12 \equiv 5 \pmod{7}
$
- 所以
$
2 \times 3^{-1} \equiv 2 \times 5 = 10 \equiv 3 \pmod{7}
$
答案：3
第 10 题解析（陷阱）
计算
$
6^{100} \bmod 8
$
- gcd(6,8)=2 ≠ 1，不可使用欧拉定理。
- 找规律：
$
6^1 = 6 \pmod{8},\quad 6^2 = 36 \equiv 4 \pmod{8},\quad 6^3 = 216 \equiv 0 \pmod{8}
$
当指数 ≥ 3 时，结果恒为 0。
- 因为 100 ≥ 3，所以答案是 0。
答案：0
总结口诀
| 条件 | 方法 |
|---|---|
| 底数与模数互质 | 才可用费马（质数）或欧拉（合数） |
模数为质数 p |
指数对 p-1 取模 |
模数为合数 n |
指数对 φ(n) 取模 |
| 求逆元（质数） | a^{p-2} |
| 求逆元（合数互质） | a^{φ(n)-1} |
| 不互质 | 找规律或分解后使用中国剩余定理 |
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
