费马小定理 & 欧拉定理

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

费马小定理

费马小定理（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$ ，余数 $ia mod p$ 各不相同。反证法。如果有 $1 \leq i < j < p$ 使得
$ia mod p = ja mod p . ⟺ (j - i) a \equiv 0. (mod p)$
但是， $(j - i)$ 和 $a$ 都不是 $p$ 的倍数，这显然矛盾。

换句话说，这些余数是 ${1, 2, \dots, p - 1}$ 的一个排列。因此，有
$i = 1 \prod p - 1 i = i = 1 \prod p - 1 (ia mod p) \equiv i = 1 \prod p - 1 ia = a^{p - 1} i = 1 \prod p - 1 i . (mod p)$
这说明
$(a^{p - 1} - 1) i = 1 \prod 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} + (1 p) a^{p - 1} + (2 p) a^{p - 2} + \dots + (p - 1 p) a + 1.$
除了首尾两项，组合数的表达式 $(k p) = \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$ ，且 $g cd (a, m) = 1$ ，有 $a^{φ (m)} \equiv 1 (mod m)$ ，其中， $φ (\cdot)$ 为欧拉函数。

证明

与费马小定理的证明一类似，仍然是取一个与 $m$ 互质的数列，再进行操作。考虑集合
$R = {r \in N : 0 < r < m, g cd (r, m) = 1} .$
这是模 $m$ 的既约剩余系。根据欧拉函数的定义可知， $∣ R ∣ = φ (m)$ 。类似上文，将它们乘以 $a$ 相当于对该集合重新排列：
$R = {a r mod m : r \in R} .$
这是因为，容易验证 $g cd (a r, m) = 1$ 且不同的 $r_{1}, r_{2} \in R$ 对应的 $a r_{1} mod m$ 和 $a r_{2} mod m$ 也一定不同。因此，有
$r \in R \prod r \equiv r \in R \prod a r = a^{φ (m)} r \in R \prod 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 (lo g φ (m))$ 时间内计算。

扩展欧拉定理

对于任意正整数 $m$ 、整数 $a$ 和非负整数 $k$ ，有
$a^{k} \equiv ⎩ ⎨ ⎧ a^{k mod φ (m)}, a^{k}, a^{(k mod φ (m)) + φ (m)}, g cd (a, m) = 1, g cd (a, m) \neq = 1, k < φ (m), g cd (a, m) \neq = 1, k \geq φ (m) . (mod m)$

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

直观理解

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

考虑余数 $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}{g cd ( 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}{g cd ( a ^{k_{0}} , m )}$ 互素。

进而，对 $k \geq k_{0}$ 考察同余关系
$b \equiv a^{k} . (mod m)$
由于 $g cd (a^{k_{0}}, m) = g cd (a^{k}, m) ∣ b$ ，所以，将等式两侧（包括模数）同时除以 $g cd (a^{k_{0}}, m)$ ，就有
$\frac{b}{g cd ( a ^{k_{0}} , m )} = \frac{a ^{k_{0}}}{g cd ( a ^{k_{0}} , m )} \cdot a^{k - k_{0}} . (mod m^{'})$
此时，因为 $a$ 与模数 $m^{'}$ 互素，可以直接应用欧拉定理，得到
$\frac{b}{g cd ( a ^{k_{0}} , m )} \equiv \frac{a ^{k_{0}}}{g cd ( a ^{k_{0}} , m )} \cdot a^{(k - k_{0}) mod φ (m^{'})} . (mod m^{'})$
因此，再将因子 $g cd (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$ ，都有
$φ (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) .$
其中，第二行的不等式利用了二项式展开，并只保留常数项和一次项。因此，有
$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 = {1, A ↑ (A ↑↑ (B - 1)), B = 0, B > 0.$
规定 $0^{0} = 1$ 。

解答

利用 $A ↑↑ B$ 的定义，递归计算即可。要计算 $(A ↑↑ B) mod M$ ，只需要应用扩展欧拉定理，计算 $(A ↑↑ (B - 1)) mod φ (M)$ 。由于 $φ (φ (n)) \leq n /2$ 对所有 $n \geq 2$ 都成立，所以，递归过程一定在 $O (lo g 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.

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

Sean's Blog

探索

费马小定理 & 欧拉定理