费马小定理 & 欧拉定理

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

费马小定理

费马小定理（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;
  }
}

习题

参考资料与注释

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.

这一名字主要出现在算法竞赛圈中，而并非该结论的通用名称。 ↩

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