OI-wiki 数论专题费马小定理、欧拉定理与扩展欧拉定理的证明与应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki费马小定理、欧拉定理及其扩展是 OI-wiki 数论板块docs/math/number-theory中处理任意模数下大指数幂次计算问题的核心工具。本文以 fermat.md 为主线完整覆盖三条定理的表述、证明、直观理解与复杂度分析并结合仓库内的 tetration.cpp 参考代码给出幂塔取模问题的可运行实现与逐行讲解。读完本文你将掌握费马小定理两种表述及其等价性论证、欧拉定理与 Carmichael 函数的联系、扩展欧拉定理三情形公式的由来以及它在「任意模数、任意底数、任意大指数」求幂场景下的完整降幂套路。费马小定理费马小定理Fermats little theorem是数论中最基础的定理之一。它是 Fermat 素性测试 的理论基础。费马小定理设 $p$ 是素数对于任意整数 $a$ 且 $p\nmid a$都成立 $a^{p-1}\equiv 1\pmod p$.定理设 $p$ 是素数对于任意整数 $a$都成立 $a^{p}\equiv a\pmod p$.这两个同余关系在 $p\nmid a$ 时是等价的而在 $p\mid a$ 时$a^p\equiv 0\equiv a\pmod p$ 平凡地成立。因此这两个命题是等价的。这两个命题常常都称作费马小定理。第一条表述直接服务于取模意义下的快速幂当模数 $p$ 为素数且底数 $a$ 不被 $p$ 整除时指数可以模 $p-1$ 约简第二条表述则对所有整数 $a$ 成立包括 $a$ 为 $p$ 的倍数时形式更统一。二者各有用武之地。证明一剩余系排列设 $p$ 是素数且 $p\nmid a$。首先证明对于 $i1,2,\cdots,p-1$余数 $ia \bmod p$ 各不相同。反证法。如果有 $1\le i j p$ 使得$$ ia \bmod p ja \bmod p \iff (j-i)a\equiv 0 \pmod p, $$但是$(j-i)$ 和 $a$ 都不是 $p$ 的倍数这显然矛盾$1\le j-i p$故 $p\nmid (j-i)$$p\nmid a$ 是前提。换句话说这些余数是 ${1,2,\cdots,p-1}$ 的一个排列。因此有$$ \prod_{i1}^{p-1}i \prod_{i1}^{p-1}(ia\bmod p) \equiv \prod_{i1}^{p-1}ia a^{p-1}\prod_{i1}^{p-1}i \pmod p. $$这说明$$ (a^{p-1}-1)\prod_{i1}^{p-1}i \equiv 0 \pmod{p}. $$等式左侧是 $p$ 的倍数但 $i1,2,\cdots, p-1$ 都不是 $p$ 的倍数所以只能有 $p\mid (a^{p-1}-1)$亦即费马小定理成立。这一定理在 prime.md 中被直接转化为概率性素性检验反复随机选取基底 $a\in[2,n-1]$ 并检验 $a^{n-1}\equiv 1\pmod n$一旦不成立即可断定 $n$ 是合数见该文档 Fermat 素性测试 一节的参考实现C/Python 两个版本。证明二二项式定理与数学归纳注意到费马小定理的第二种表述对于所有 $a\in\mathbf N$ 都成立因此可以考虑使用数学归纳法。负整数的情形容易转化为非负整数的情形利用 $(-a)^p\equiv -a^p$ 与模 $p$ 的符号处理可将负底数归结为正底数。归纳起点为 $0^p\equiv 0\pmod p$显然成立。假设它对于 $a\in\mathbf N$ 成立需要证明它对于 $a1$ 也成立。由二项式定理可知$$ (a1)^pa^p\binom{p}{1}a^{p-1}\binom{p}{2}a^{p-2}\cdots \binom{p}{p-1}a1. $$除了首尾两项组合数的表达式 $\dbinom{p}{k} \dfrac{p!}{k!(p-k)!}$ 中$p$ 都能整除分子而不能整除分母因此这些系数对于 $k\neq 0,p$ 都是 $p$ 的倍数这是「素数 $p$ 整除 $p!$ 但不整除 $k!$ 与 $(p-k)!$」的直接推论。因此有$$ (a1)^p \equiv a^p 1\equiv a 1 \pmod{p}, $$其中第二步应用了归纳假设。利用数学归纳法可知费马小定理成立。逆命题并不成立伪素数现象费马小定理的逆命题并不成立。即使对于所有与 $n$ 互素的 $a$ 都有 $a^{n-1}\equiv 1\pmod n$$n$ 也未必是素数。prime.md 给出了具体反例对于 $n341$、$a2$虽然有 $2^{340}\equiv 1\pmod{341}$但 $34111\cdot 31$ 是合数称 $n$ 为以 $a$ 为底的Fermat 伪素数事实上对于任何固定的基底 $a$这样的反例都有无穷多个。更严重的是存在Carmichael 数卡迈克尔数它让所有与其互素的基底 $a$ 都通过检验且有无穷多个详见 primitive-root.md 的 Carmichael 函数与 Carmichael 数 一节。这正解释了为什么实际工程中要用更强的 Miller–Rabin 素性测试。欧拉定理欧拉定理Eulers theorem将费马小定理推广到了一般模数的情形但仍然要求底数与指数互素。欧拉定理对于整数 $m0$ 和整数 $a$且 $\gcd(a,m)1$有 $a^{\varphi(m)}\equiv 1\pmod{m}$其中 $\varphi(\cdot)$ 为 欧拉函数。证明既约剩余系与费马小定理的证明一类似仍然是取一个与 $m$ 互质的数列再进行操作。考虑集合$$ R {r\in\mathbf N : 0 r m,~\gcd(r,m)1}. $$这是模 $m$ 的 既约剩余系。根据欧拉函数的定义可知 $|R|\varphi(m)$。类似上文将它们乘以 $a$ 相当于对该集合重新排列$$ R {ar\bmod m: r\in R}. $$这是因为容易验证 $\gcd(ar,m)1$$a$、$r$ 均与 $m$ 互素乘积亦然且不同的 $r_1,r_2\in R$ 对应的 $ar_1\bmod m$ 和 $ar_2\bmod m$ 也一定不同否则 $(r_1-r_2)a\equiv 0\pmod m$结合 $\gcd(a,m)1$ 可得 $m\mid (r_1-r_2)$与 $0r_1,r_2m$ 矛盾。因此有$$ \prod_{r\in R}r \equiv \prod_{r\in R}ar a^{\varphi(m)}\prod_{r\in R}r \pmod{m}. $$再次重复之前的论证消去 $\prod_{r\in R}r$它是与 $m$ 互素的整数的乘积模 $m$ 可逆就得到 $a^{\varphi(m)}\equiv 1\pmod m$。与费马小定理、Carmichael 函数的关系对于素数 $p$有 $\varphi(p)p-1$因此费马小定理是欧拉定理的一个特例模数从素数放宽到任意与底数互素的 $m$指数从 $p-1$ 推广到 $\varphi(m)$。关于欧拉函数的计算可参考 euler-totient.md 中的实现利用公式 $\varphi(n)n\times\prod_{p\mid n}(1-\frac1p)$在 $O(\sqrt n)$ 的试除过程中同步求出参见 docs/math/number-theory/euler-totient.md。另外欧拉定理中的指数 $\varphi(m)$ 在一般情形下并非使得该式成立的最小指数。它可以改进到 $\lambda(m)$其中 $\lambda(\cdot)$ 是 Carmichael 函数——即所有与 $m$ 互素的整数 $a$ 的阶 $\delta_m(a)$ 的最小公倍数。关于相关结论的代数背景可以参考 整数同余类的乘法群 一节模 $m$ 的既约剩余系配上乘法构成 Abel 群欧拉定理不过是在说该群中每个元素的幂次整除群阶 $\varphi(m)$而 Carmichael 函数给出的是该群的最小公共指数。扩展欧拉定理扩展欧拉定理1进一步将结论推广到了底数与指数不互素的情形。由此它彻底解决了任意模数下任意底数的幂次计算问题将它们转化为指数小于 $2\varphi(m)$ 的情形从而可以通过 快速幂 在 $O(\log\varphi(m))$ 时间内计算。扩展欧拉定理对于任意正整数 $m$、整数 $a$ 和非负整数 $k$有$$ a^k \equiv \begin{cases} a^{k \bmod \varphi(m)}, \gcd(a,m) 1, \ a^k, \gcd(a,m)\ne 1, k \varphi(m), \ a^{(k \bmod \varphi(m)) \varphi(m)}, \gcd(a,m)\ne 1, k \ge \varphi(m). \end{cases} \pmod m $$第二种情形是说如果 $k \varphi(m)$就无需继续降幂直接应用快速幂即可而第三种和第一种情形的最大区别是通过取余降幂之后是否需要加上一项 $\varphi(m)$。当然将第一种情形合并进入第二、三种情形也是正确的——即对 $\gcd(a,m)1$ 的情形无论 $k$ 与 $\varphi(m)$ 的大小关系如何加上 $\varphi(m)$ 也不会改变结果因为 $a^{\varphi(m)}\equiv 1$。因此在工程实现中往往可以只写成一个统一的取余规则见下文幂塔例题中的mod函数。直观理解幂次余数的循环结构在严格证明定理之前可以首先直观理解定理的含义。考虑余数 $a^k\bmod m$ 随着 $k$ 增大而变化的情况。由于余数的取值一定在区间 $[0,m)$ 内而 $k$ 有无限多个。将 $a^k\bmod m \mapsto a^{k1}\bmod m$ 看作这些余数结点之间的有向边那么一定可以构成如图所示的循环。扩展欧拉定理说明这些循环可能是纯循环第一种情形或者混循环第二、三种情形。纯循环中没有结点存在两个前驱即映射是双射对应 $\gcd(a,m)1$ 时每个结点恰好进入唯一后继整个图分解为若干互不相交的圈而混循环中就会出现这样的情形若干条「尾巴」汇入同一个圈。因此对于一般的情况只需要能够求出循环节的长度和进入循环节之前的长度就可以利用这个性质进行降幂。严格证明本节给出扩展欧拉定理的严格证明。首先说明存在 $k_0\in\mathbf N$使得整数 $a$ 和 $m:\dfrac{m}{\gcd(a^{k_0},m)}$ 互素。为此设 $\nu_p(n)$ 是整数 $n$ 的质因数分解中素数 $p$ 的幂次那么不妨取$$ k_0 \max\left{\left\lceil\dfrac{\nu_p(m)}{\nu_p(a)}\right\rceil : \nu_p(a)0\right}. $$因为 $m$ 中所有和 $a$ 的公共素因子的幂次都已经包含在 $a^{k_0}$ 中所以 $a$ 就与 $m$ 中剩下的因子 $m\dfrac{m}{\gcd(a^{k_0},m)}$ 互素。直观地说$k_0$ 是让 $a^k$ 把「与 $m$ 共有的质因子」全部吃够所需的次数。进而对 $k\ge k_0$ 考察同余关系$$ b\equiv a^k \pmod m. $$由于 $\gcd(a^{k_0},m)\gcd(a^k,m)\mid b$当 $k\ge k_0$ 时 $a^k$ 中公共质因子的幂次不低于 $a^{k_0}$故 $\gcd(a^k,m)\gcd(a^{k_0},m)$所以将等式两侧包括模数同时除以 $\gcd(a^{k_0},m)$就有$$ \dfrac{b}{\gcd(a^{k_0},m)} \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{k-k_0} \pmod{m}. $$此时因为 $a$ 与模数 $m$ 互素可以直接应用欧拉定理得到$$ \dfrac{b}{\gcd(a^{k_0},m)} \equiv \dfrac{a^{k_0}}{\gcd(a^{k_0},m)}\cdot a^{(k-k_0)\bmod\varphi(m)} \pmod{m}. $$因此再将因子 $\gcd(a^{k_0},m)$ 乘回去就得到$$ b \equiv a^{k_0}\cdot a^{(k-k_0)\bmod\varphi(m)} a^{k_0 (k-k_0)\bmod\varphi(m)} \pmod{m}. $$这就得到了扩展欧拉定理的形式。式子说明循环节的长度是 $\varphi(m)$而进入循环节之前的长度为 $k_0$。这正是上文直观图中「尾巴长度」与「圈长」的严格表述。此处得到的参数比扩展欧拉定理中的更紧更精确但是相对来说这些参数的计算并不容易需要对 $m$、$a$ 做质因数分解并逐素因子求上取整。可以说明这些参数可以放宽到扩展欧拉定理中的情形。首先利用 欧拉函数的表达式 可知因为 $m\mid m$所以 $\varphi(m)\mid\varphi(m)$。也就是说$\varphi(m)$ 也是它的循环节。其次$k_0$ 也可以放宽到 $\varphi(m)$这是因为对于所有 $m\in\mathbf N_$ 和任意 $p\mid m$都有$$ \begin{aligned} \varphi(m) \ge \varphi(p^{\nu_p(m)}) (p-1)p^{\nu_p(m)-1} \ge p^{\nu_p(m)-1} \ (1(p-1))^{\nu_p(m)-1} \ge 1 (p-1)(\nu_p(m)-1) \ \ge 1 (\nu_p(m)-1) \nu_p(m). \end{aligned} $$其中第二行的不等式利用了二项式展开并只保留常数项和一次项$(1x)^n \ge 1nx$ 对 $x\ge 0$ 成立。因此有$$ k_0 \le \max{\nu_p(m):p\in\mathbf P}\le \varphi(m). $$这就完全证明了所述结论用 $\varphi(m)$ 同时替代 $k_0$ 与 $\varphi(m)$既不会漏掉「尾巴」也不会破坏循环节的性质代价仅是得到一个稍宽松但仍正确的降幂公式。例题幂塔取模Tetration Mod本节通过一道例题展示扩展欧拉定理的一个经典应用——计算任意模数下的幂塔。幂塔power tower指形如 $A\uparrow(B\uparrow(C\uparrow(D\uparrow\cdots)))$ 的式子其中 $\uparrow$ 是 Knuth 箭头记号而 $A,B,C,D,\cdots$ 是一系列非负整数。当指数本身也是巨大幂时普通快速幂完全无法处理这正是扩展欧拉定理降幂的用武之地。例题[Library Checker - Tetration Mod]$T$ 组测试。每组测试中给定 $A,B,M$求 $(A\uparrow\uparrow B)\bmod M$。其中 $A\uparrow\uparrow B$ 表示由 $B$ 个 $A$ 组成的幂塔。形式化地定义$$ A \uparrow\uparrow B \begin{cases} 1, B 0,\ A\uparrow(A\uparrow\uparrow(B-1)), B 0. \end{cases} $$规定 $0^01$。解题思路利用 $A\uparrow\uparrow B$ 的定义递归计算即可。要计算 $(A\uparrow\uparrow B)\bmod M$只需要应用扩展欧拉定理计算 $(A\uparrow\uparrow(B-1))\bmod\varphi(M)$。由于 $\varphi(\varphi(n)) \le n/2$ 对所有 $n\ge 2$ 都成立每一层模数至少减半所以递归过程一定在 $O(\log M)$ 步内完成。由于需要应用扩展欧拉定理所以需要区分当前的计算结果是否严格小于当前模数只有当前层结果 $\ge\varphi(M)$ 时指数才需要「取余后加 $\varphi(M)$」否则直接返回原值。为此只需要在取余的时候多判断一步即可见下文mod函数。另外需要注意边界情况的处理$B0$ 时幂塔定义为 $1$$M1$ 时任何数模 $1$ 均为 $0$底数 $a0$ 时 $0\uparrow\uparrow B$ 在 $0^01$ 约定下等于 $B$ 为偶数时的 $1$ 与 $B$ 为奇数时的 $0$。参考代码逐行分析仓库 docs/math/code/fermat/tetration.cpp 给出了完整实现全部代码共约 45 行#include iostream // Calculate Eulers totient for n. int phi(int n) { int res n; for (int i 2; i * i n; i) { if (n % i 0) { res res / i * (i - 1); while (n % i 0) n / i; } } if (n 1) res res / n * (n - 1); return res; } // Find remainder as in the exponent of extended Euler theorem. int mod(long long v, int m) { return v m ? v % m m : v; } // Modular power. int pow(int a, int b, int m) { long long res 1, po a; for (; b; b 1) { if (b 1) res mod(res * po, m); po mod(po * po, m); } return res; } // Modular tetration. int tetra(int a, int b, int m) { if (a 0) return !(b 1); if (b 0 || m 1) return 1; if (b 1) return mod(a, m); return pow(a, tetra(a, b - 1, phi(m)), m); } int main() { int t; std::cin t; for (; t; --t) { int a, b, m; std::cin a b m; std::cout (tetra(a, b, m) % m) std::endl; } }逐函数解读phi(int n)在 $O(\sqrt n)$ 的试除中同步计算欧拉函数核心公式是 $\varphi(n)n\prod_{p\mid n}\frac{p-1}{p}$。注意写法res res / i * (i - 1)先除后乘避免中间结果溢出while (n % i 0) n / i用于剥除重复素因子。该实现与 euler-totient.md 中的参考实现结构一致。mod(long long v, int m)扩展欧拉定理实现的核心技巧。它返回「值 $v$ 对模数 $m$ 的带标记余数」若 $v m$ 直接返回 $v$表示结果严格小于模数否则返回 $v\bmod m m$。返回值一旦 $\ge m$就携带了「真实值超过模数」的信息供上一层判断是否需要应用定理第三分支。返回值仍按模 $m$ 等价因此可安全地作为后续快速幂的指数。pow(int a, int b, int m)二进制快速幂binary-exponentiation 的迭代版本。与普通快速幂的唯一区别是乘法结果用mod处理使得返回的「指数」同时携带大小标记保证递归过程中标记信息不丢失。复杂度 $O(\log b)$。tetra(int a, int b, int m)递归计算 $(A\uparrow\uparrow B)\bmod M$对应递推式 $A\uparrow\uparrow B A^{A\uparrow\uparrow(B-1)}$a 0时返回!(b 1)$0\uparrow\uparrow B$ 在 $0^01$ 约定下偶数层为 $1$、奇数层为 $0$b 0时幂塔为空定义为 $1$m 1时任何结果模 $1$ 均为 $0$直接返回 $1$随后被% m化为 $0$b 1时只有一层直接返回mod(a, m)一般情形递归地计算指数 $e\texttt{tetra}(a, b-1, \varphi(m))$再套用pow(a, e, m)。由于模数沿递归链按 $\varphi$ 递减每次至少减半递归深度为 $O(\log M)$。主函数处理 $T$ 组数据并输出tetra(a, b, m) % m。整体复杂度为 $O(\log M \cdot \sqrt{M_0})$其中 $\sqrt{M_0}$ 来自首层求 $\varphi$ 的试除且各层模数迅速衰减实际运行非常快。习题以下习题可用于巩固扩展欧拉定理的降幂思想与边界处理能力Luogu P5091【模板】扩展欧拉定理直接考察三情形公式的模板题Codeforces 906 D. Power Tower一般化的幂塔取模需注意 $\varphi$ 降至 $1$ 时的截断Luogu P3747 [六省联考 2017] 相逢是问候扩展欧拉定理与线段树结合的进阶题Luogu P4139 上帝与集合的正确用法经典「无限幂塔」取模$B\to\infty$ 时如何收敛Luogu P3934 [Ynoi Easy Round 2016] 炸脖龙 I扩展欧拉定理与区间操作的组合Luogu P6736「Wdsr-2」白泽教育进一步考察降幂与取余标记的综合运用。参考资料与注释prime.mdFermat 素性测试与 Miller–Rabin 素性测试的完整讨论euler-totient.md欧拉函数的定义、性质与实现primitive-root.mdCarmichael 函数与 Carmichael 数ring-theory.md整数同余类的乘法群的代数背景binary-exponentiation.md快速幂的迭代与递归实现tetration.cpp幂塔取模的参考实现Hardy, Godfrey Harold, and Edward Maitland Wright.An introduction to the theory of numbers. Oxford university press, 1979.数论经典教材费马小定理与欧拉定理的标准参考文献。这一名字主要出现在算法竞赛圈中而并非该结论的通用名称在数学文献中通常将 $a^{\varphi(m)}\equiv 1\pmod m$ 对不互素情形的推广归入 Euler 定理的完整表述考虑 $a^k$ 在 $k\ge\varphi(m)$ 时落入循环算法竞赛中习惯单列「扩展欧拉定理」以便于记忆与实现↩【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考