费马小定理 & 欧拉定理

本文讨论费马小定理、欧拉定理及其扩展．这些定理解决了任意模数下任意大指数的幂的计算问题．

费马小定理

费马小定理（Fermat's little theorem）是数论中最基础的定理之一．它也是 Fermat 素性测试的理论基础．

费马小定理

设 $p$ 是素数．对于任意整数 $a$ 且 $p ∤ a$ ，都成立 $a^{p - 1} \equiv 1 (\mod p)$ .

定理

设 $p$ 是素数．对于任意整数 $a$ ，都成立 $a^{p} \equiv a (\mod p)$ .

这两个同余关系在 $p ∤ a$ 时是等价的；而在 $p ∣ a$ 时， $a^{p} \equiv 0 \equiv a (\mod p)$ 平凡地成立．因此，这两个命题是等价的．这两个命题常常都称作费马小定理．

证明一

设 $p$ 是素数，且 $p ∤ a$ ．首先证明：对于 $i = 1, 2, \dots, p - 1$ ，余数 $i a mod p$ 各不相同．反证法．如果有 $1 \leq i < j < p$ 使得

i a mod p = j a mod p . ⟺ (j - i) a \equiv 0. (\mod p)

但是， $(j - i)$ 和 $a$ 都不是 $p$ 的倍数，这显然矛盾．

换句话说，这些余数是 ${1, 2, \dots, p - 1}$ 的一个排列．因此，有

\prod_{i = 1}^{p - 1} i = \prod_{i = 1}^{p - 1} (i a mod p) \equiv \prod_{i = 1}^{p - 1} i a = a^{p - 1} \prod_{i = 1}^{p - 1} i . (\mod p)

这说明

(a^{p - 1} - 1) \prod_{i = 1}^{p - 1} i \equiv 0. (\mod p)

也就是说，等式左侧是 $p$ 的倍数，但是 $i = 1, 2, \dots, p - 1$ 都不是 $p$ 的倍数，所以，只能有 $p ∣ (a^{p - 1} - 1)$ ，亦即费马小定理成立．

证明二

注意到费马小定理的第二种表述对于所有 $a \in N$ 都成立，因此，可以考虑使用数学归纳法．负整数的情形容易转化为非负整数的情形．

归纳起点为 $0^{p} \equiv 0 (\mod p)$ ，显然成立．假设它对于 $a \in N$ 成立，需要证明的是，它对于 $a + 1$ 也成立．由二项式定理可知

(a + 1)^{p} = a^{p} + (\binom{p}{1}) a^{p - 1} + (\binom{p}{2}) a^{p - 2} + \dots + (\binom{p}{p - 1}) a + 1.

除了首尾两项，组合数的表达式 $(\binom{p}{k}) = \frac{p!}{k! (p - k)!}$ 中， $p$ 都能整除分子，而不能整除分母，因此，这些系数对于 $k \neq 0, p$ 都是 $p$ 的倍数．因此，有

(a + 1)^{p} \equiv a^{p} + 1 \equiv a + 1. (\mod p)

其中，第二步应用了归纳假设．因此，利用数学归纳法可知，费马小定理成立．

费马小定理的逆命题并不成立．即使对于所有与 $n$ 互素的 $a$ ，都有 $a^{n - 1} \equiv 1 (\mod n)$ ，那么， $n$ 也未必是素数．相关讨论详见 Fermat 素性测试一节．

欧拉定理

欧拉定理（Euler's theorem）将费马小定理推广到了一般模数的情形，但仍然要求底数与指数互素．

欧拉定理

对于整数 $m > 0$ 和整数 $a$ ，且 $gcd (a, m) = 1$ ，有 $a^{φ (m)} \equiv 1 (\mod m)$ ，其中， $φ (\cdot)$ 为欧拉函数．

证明

与费马小定理的证明一类似，仍然是取一个与 $m$ 互质的数列，再进行操作．考虑集合

R = {r \in N : 0 < r < m, gcd (r, m) = 1} .

这是模 $m$ 的既约剩余系．根据欧拉函数的定义可知， $| R | = φ (m)$ ．类似上文，将它们乘以 $a$ 相当于对该集合重新排列：

R = {a r mod m : r \in R} .

这是因为，容易验证 $gcd (a r, m) = 1$ 且不同的 $r_{1}, r_{2} \in R$ 对应的 $a r_{1} mod m$ 和 $a r_{2} mod m$ 也一定不同．因此，有

\prod_{r \in R} r \equiv \prod_{r \in R} a r = a^{φ (m)} \prod_{r \in R} r . (\mod m)

再次重复之前的论证，消去 $\prod_{r \in R} r$ ，就得到 $a^{φ (m)} \equiv 1 (\mod m)$ ．

对于素数 $p$ ，有 $φ (p) = p - 1$ ，因此，费马小定理是欧拉定理的一个特例．另外，欧拉定理中的指数 $φ (m)$ 在一般情形下并非使得该式成立的最小指数．它可以改进到 $λ (m)$ ，其中， $λ (\cdot)$ 是 Carmichael 函数．关于相关结论的代数背景，可以参考整数同余类的乘法群一节．

扩展欧拉定理

扩展欧拉定理¹进一步将结论推广到了底数与指数不互素的情形．由此，它彻底解决了任意模数下任意底数的幂次计算问题，将它们转化为指数小于 $2 φ (m)$ 的情形，从而可以通过快速幂在 $O (\log φ (m))$ 时间内计算．

扩展欧拉定理

对于任意正整数 $m$ 、整数 $a$ 和非负整数 $k$ ，有

a^{k} \equiv {\begin{cases} a^{k mod φ (m)}, & gcd (a, m) = 1, \\ a^{k}, & gcd (a, m) \neq 1, k < φ (m), \\ a^{(k mod φ (m)) + φ (m)}, & gcd (a, m) \neq 1, k \geq φ (m) . \end{cases} (\mod m)

第二种情形是在说，如果 $k < φ (m)$ ，那么，就无需继续降幂，直接应用快速幂即可；而第三种和第一种情形的最大区别是，通过取余降幂之后，是否需要加上一项 $φ (m)$ ．当然，将第一种情形合并进入第二、三种情形也是正确的．

直观理解

在严格证明定理之前，可以首先直观理解定理的含义．

fermat1

考虑余数 $a^{k} mod m$ 随着 $b$ 增大而变化的情况．由于余数的取值一定在区间 $[0, m)$ 内，而 $k$ 有无限多个．将 $a^{k} mod m \mapsto a^{k + 1} mod m$ 看作这些余数结点之间的有向边．那么，一定可以构成如图所示的循环．

扩展欧拉定理说明，这些循环可能是纯循环（第一种情形）或者混循环（第二、三种情形）．纯循环中，没有结点存在两个前驱，而混循环中就会出现这样的情形．因此，对于一般的情况，只需要能够求出循环节的长度和进入循环节之前的长度，就可以利用这个性质进行降幂．

严格证明

本节给出扩展欧拉定理的严格证明．

证明

首先说明，存在 $k_{0} \in N$ ，使得整数 $a$ 和 $m^{'} := \frac{m}{gcd (a^{k_{0}}, m)}$ 互素．为此，设 $ν_{p} (n)$ 是整数 $n$ 的质因数分解中素数 $p$ 的幂次，那么，不妨取

k_{0} = max {⌈ \frac{ν_{p} (m)}{ν_{p} (a)} ⌉ : ν_{p} (a) > 0} .

因为 $m$ 中所有和 $a$ 的公共素因子的幂次都已经包含在 $a^{k_{0}}$ 中，所以， $a$ 就与 $m$ 中剩下的因子 $m^{'} = \frac{m}{gcd (a^{k_{0}}, m)}$ 互素．

进而，对 $k \geq k_{0}$ 考察同余关系

b \equiv a^{k} . (\mod m)

由于 $gcd (a^{k_{0}}, m) = gcd (a^{k}, m) ∣ b$ ，所以，将等式两侧（包括模数）同时除以 $gcd (a^{k_{0}}, m)$ ，就有

\frac{b}{gcd (a^{k_{0}}, m)} = \frac{a^{k_{0}}}{gcd (a^{k_{0}}, m)} \cdot a^{k - k_{0}} . (\mod m^{'})

此时，因为 $a$ 与模数 $m^{'}$ 互素，可以直接应用欧拉定理，得到

\frac{b}{gcd (a^{k_{0}}, m)} \equiv \frac{a^{k_{0}}}{gcd (a^{k_{0}}, m)} \cdot a^{(k - k_{0}) mod φ (m^{'})} . (\mod m^{'})

因此，再将因子 $gcd (a^{k_{0}}, m)$ 乘回去，就得到

b \equiv a^{k_{0}} \cdot a^{(k - k_{0}) mod φ (m^{'})} = a^{k_{0} + (k - k_{0}) mod φ (m^{'})} . (\mod m)

这就得到了扩展欧拉定理的形式．式子说明，循环节的长度是 $φ (m^{'})$ ，而进入循环节之前的长度为 $k_{0}$ ．

此处得到的参数比扩展欧拉定理中的更紧，但是相对来说，这些参数的计算并不容易．可以说明，这些参数可以放宽到扩展欧拉定理中的情形．首先，利用欧拉函数的表达式可知，因为 $m^{'} ∣ m$ ，所以 $φ (m^{'}) ∣ φ (m)$ ．也就是说， $φ (m)$ 也是它的循环节．其次， $k_{0}$ 也可以放宽到 $φ (m)$ ．这是因为对于所有 $m \in N_{+}$ 和任意 $p ∣ m$ ，都有

\begin{aligned} φ (m) & \geq φ (p^{ν_{p} (m)}) = (p - 1) p^{ν_{p} (m) - 1} \geq p^{ν_{p} (m) - 1} \\ = (1 + (p - 1))^{ν_{p} (m) - 1} \geq 1 + (p - 1) (ν_{p} (m) - 1) \\ \geq 1 + (ν_{p} (m) - 1) = ν_{p} (m) . \end{aligned}

其中，第二行的不等式利用了二项式展开，并只保留常数项和一次项．因此，有

k_{0} \leq max {ν_{p} (m) : p \in P} \leq φ (m) .

这就完全证明了所述结论．

例题

本节通过一道例题展示扩展欧拉定理的一个经典应用——计算任意模数下的幂塔．幂塔（power tower）指形如 $A ↑ (B ↑ (C ↑ (D ↑ \dots)))$ 的式子，其中， $↑$ 是 Knuth 箭头记号，而 $A, B, C, D, \dots$ 是一系列非负整数．

Library Checker - Tetration Mod

$T$ 组测试．每组测试中，给定 $A, B, M$ ，求 $(A ↑↑ B) mod M$ ．其中， $A ↑↑ B$ 表示由 $B$ 个 $A$ 组成的幂塔．或者，形式化地，定义

A ↑↑ B = {\begin{cases} 1, & B = 0, \\ A ↑ (A ↑↑ (B - 1)), & B > 0. \end{cases}

规定 $0^{0} = 1$ ．

解答

利用 $A ↑↑ B$ 的定义，递归计算即可．要计算 $(A ↑↑ B) mod M$ ，只需要应用扩展欧拉定理，计算 $(A ↑↑ (B - 1)) mod φ (M)$ ．由于 $φ (φ (n)) \leq n / 2$ 对所有 $n \geq 2$ 都成立，所以，递归过程一定在 $O (\log M)$ 步内完成．由于需要应用扩展欧拉定理，所以需要区分当前的计算结果是否严格小于当前模数．为此，只需要在取余的时候多判断一步即可．另外，需要注意边界情况的处理．

参考代码

#include <iostream>

// Calculate Euler's 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;
  }
}

取模技巧正确性证明

本实现利用

r_{m} (v) = {\begin{cases} v mod m, & if v < m, \\ v mod m + m, & if v \geq m \end{cases}

代替取模，相当于同时记录了余数信息 $v mod m$ 和越界信息 $v \geq m$ ．扩展欧拉定理只能说明，当指数的余数信息和越界信息都正确时，取幂能够得到正确的余数信息；但是，越界信息的正确性无法保证．例如，在计算 $r_{6} (2^{4})$ 时，指数需要对 $φ (6) = 2$ 取模，而 $r_{2} (4) = 2$ （即余数为 $0$ 且越界），进行取幂后将得到 $r_{6} (2^{2}) = 4$ ；与正确答案 $r_{6} (2^{4}) = 10$ 相比，模 $6$ 的余数正确，但是越界信息丢失．但可以证明，尽管越界信息可能丢失，余数信息却总是正确的．因此，基于这一取模技巧的取幂算法也总是正确的．

考虑算法的迭代过程．假设从最内层开始向外层函数回溯，第一次越界信息错误发生在计算 $r_{m} (a^{k})$ 时． $k < φ (m)$ 时指数精确，不会出错，故设 $k \geq φ (m)$ ；此时 $k \geq k mod φ (m) + φ (m)$ ，即取模只会低估指数，越界信息不会凭空产生，出错的唯一可能是本应记录越界而实际未记录，即

a^{k mod φ (m) + φ (m)} < m \leq a^{k} .

该不等式只能在 $a \geq 2$ 时成立，所以左侧表达式不小于 $2^{φ (m)}$ ．但是， $2^{φ (m)} < m$ 只会发生在 $m = 6$ 时．²代入上式，就得到 $a^{k mod 2 + 2} < 6 \leq a^{k}$ ．左侧表达式中，若 $k$ 是偶数，则指数是 $2$ ，有 $a = 2$ 且 $k \geq 4$ ；若 $k$ 是奇数，则指数是 $3$ ，无解．综上，丢失越界信息只发生在 $m = 6, a = 2$ 且 $k \geq 4$ 是偶数时．

下面说明，这一情形下丢失越界信息并不影响后续计算．只考虑 $a_{i} \geq 2$ 的非平凡情形（ $a_{i} \leq 1$ 时幂值不超过 $1$ ，不会越界）．内层模数为 $6$ ，故回溯一层后的模数 $m_{1}$ 满足 $φ (m_{1}) = 6$ ，只能是 $7, 9, 14, 18$ 之一．回溯到该层时，需要计算 $r_{m_{1}} (a_{1}^{k_{1}})$ ，而 $k_{1}$ 本应为 $10$ ，实际为 $4$ ．但对所有 $a_{1}$ 和这些 $m_{1}$ ，都有 $a_{1}^{4} \equiv a_{1}^{10} (\mod m_{1})$ ．为说明这一点，注意到前文扩展欧拉定理的证明中已经得到：对任何 $a$ 和 $m$ ，幂次余数 $a^{k} mod m$ 进入循环节之前的长度 $k_{0}$ 都不超过 $ν_{+} (m) := max {ν_{p} (m) : p ∣ m}$ ，且循环节长度整除 $φ (m)$ ．而 $ν_{+} (m_{1}) \leq 2$ ，故 $k_{1} = 4$ 已进入循环节，且它与 $10$ 相差 $φ (m_{1}) = 6$ ，亦即上式总成立．所以余数信息正确．再看越界信息．由于内层真实值为 $2^{k} \geq 16 > 10$ ，故 $a_{1}^{2^{k}} \geq a_{1}^{10} \geq m_{1}$ ，本层总应该标记越界．但本层只会返回 $a_{1}^{4}$ 是否越界；唯一出错的可能是 $a_{1}^{4} < m_{1}$ ，即只能有 $a_{1} = 2, m_{1} = 18$ ．其余情形的越界信息已正确标记，继续回溯自然正确．而 $a_{1} = 2, m_{1} = 18$ 时，本应返回 $34$ ，实际返回 $16$ ，需再回溯一层，此时 $m_{2}$ 只能是 $19, 27, 38, 54$ 之一．此时总有 $ν_{+} (m_{2}) \leq 3 < 16$ 且 $34 - 16 = φ (m_{2})$ ，余数信息正确；且 $a_{2}^{16} \geq m_{2}$ 恒成立，越界信息也正确．所以此时结果正确，后续回溯也必然正确．

由于各层模数严格递减， $m = 6$ 至多出现一次．综上，利用该取模技巧计算多层幂次时，每一层的余数信息都是正确的，至多只有两层的越界信息是错误的．注意，证明中没有假定各层取幂的底数相同，故结论对不同底数的情形也成立．

习题

参考资料与注释

Fermat's little theorem - Wikipedia
Euler's theorem - Wikipedia
Hardy, Godfrey Harold, and Edward Maitland Wright. An introduction to the theory of numbers. Oxford university press, 1979.

这一名字主要出现在算法竞赛圈中，而并非该结论的通用名称． ↩
根据 Kendall, R. and Osborn, R. (1965) Two Simple Lower Bounds for the Euler ϕ-Function. Texas Journal of Science, 17, 324-326 一文，对于 $m > 6$ 总有 $φ (m) \geq \sqrt{m}$ ．直接计算可知，对于 $m \geq 16$ ，总有 $\sqrt{m} \geq \log_{2} m$ ．因此，不等式 $φ (m) \geq \log_{2} m$ 对 $m \geq 16$ 都成立．其余可逐一验证． ↩

本页面最近更新：2026/9/4 12:45:16，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：guodong2005, Ir1d, mgt, Tiphereth-A, sshwy, c-forrest, Enter-tainer, MegaOwIer, Dev-XYS, Great-designer, PeterlitsZo, stevebraveman, tth37, Xeonacid, Acfboy, gi-b716, H-J-Granger, HeRaNO, hjsjhn, hly1204, iamtwz, ImpleLee, Menci, qz-cqy, StudyingFather, WineChord, yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用