数论四大定理之二：费马小定理——大数取模的“降维打击”

这是数论四大定理系列的第二篇。费马小定理（Fermat’s Little Theorem）在初等数论中极为重要，它是简化大数幂运算的“核武器”。

在数论的浩瀚星空中，皮埃尔·德·费马（Pierre de Fermat）无疑是最耀眼的明星之一。他提出的“费马大定理”困扰了人类三百多年，而我们今天要讲的“费马小定理”，虽然名字带个“小”字，却是打开同余运算大门的金钥匙。

对于初学者来说，面对像 $2^{100}$ 这样巨大的数字除以 $13$ 余几的问题，硬算是不可能的。而费马小定理告诉我们：在模运算的世界里，指数是有周期的。

一、 定理内容

通俗解读： 只要 $p$ 是质数，任何一个不被 $p$ 整除的数 $a$，它的 $p-1$ 次方除以 $p$ 的余数恒为 $1$。这意味着，不管指数多大，每过 $p-1$ 次方，余数就会“归一”。

二、 见微知著：从特例出发

为了理解这个定理，我们先以 $p=7$，$a=2$ 为例。此时 $p-1=6$。我们要验证的是：$2^6 \equiv 1 \pmod 7$。

我们考察一组数 $S = \{1, 2, 3, 4, 5, 6\}$，这是除以 $7$ 的非零余数集合。将集合中的每个数都乘以 $2$，得到新的一组数：$\{2, 4, 6, 8, 10, 12\}$

计算它们除以 $7$ 的余数：

$1 \times 2 \equiv 2 \pmod 7$
$2 \times 2 \equiv 4 \pmod 7$
$3 \times 2 \equiv 6 \pmod 7$
$4 \times 2 = 8 \equiv 1 \pmod 7$
$5 \times 2 = 10 \equiv 3 \pmod 7$
$6 \times 2 = 12 \equiv 5 \pmod 7$

得到的新余数是 $\{2, 4, 6, 1, 3, 5\}$。对比原来的 $\{1, 2, 3, 4, 5, 6\}$，我们发现：原来的数一个都没少，只是顺序被打乱了！

既然两组数的乘积应该在模 $7$ 意义下相等，我们可以列出等式：
$$ (1\times 2) \times (2\times 2) \times (3\times 2) \times \dots \times (6\times 2) \equiv 1 \times 2 \times 3 \times \dots \times 6 \pmod 7 $$

提取左边的公因数 $2$（一共有 $6$ 个 $2$）：
$$ 2^6 \times (1 \times 2 \times 3 \times \dots \times 6) \equiv (1 \times 2 \times 3 \times \dots \times 6) \pmod 7 $$

令 $K = 1 \times 2 \times \dots \times 6 = 6!$。
$$ 2^6 \times K \equiv K \pmod 7 $$

关键一步：
因为 $7$ 是质数，且 $1$ 到 $6$ 都比 $7$ 小，所以 $K$ ($6!$) 与 $7$ 互质。根据同余性质，我们可以两边同时“约去” $K$。
$$ \therefore 2^6 \equiv 1 \pmod 7 $$

三、 严谨证明：一般情况

理解了上面的特例，我们就可以推广到一般情况。

证明： 设 $p$ 为质数，$(a, p) = 1$。
取模 $p$ 的非零余数（即 $1$ 到 $p-1$ 的整数）：
$$ S = \{1, 2, 3, \dots, p-1\} $$

将 $S$ 中各项同时乘以 $a$，得到新序列：
$$ S’ = \{a, 2a, 3a, \dots, (p-1)a\} $$

第一步：证明 $S’$ 中的数模 $p$ 互不相同且不为 0。
采用反证法：假设 $S’$ 中有两个不同的元素 $ma$ 和 $na$（其中 $1 \le m < n \le p-1$）模 $p$ 同余。
$$ \begin{aligned}
ma &\equiv na \pmod p \\
(n-m)a &\equiv 0 \pmod p
\end{aligned} $$
这意味着 $p$ 整除 $(n-m)a$。
因为已知 $(a, p)=1$，所以 $p$ 必须整除 $(n-m)$。
但 $n$ 和 $m$ 都是小于 $p$ 的正整数，它们的差 $n-m$ 必然小于 $p$ 且大于 $0$，不可能被 $p$ 整除。
矛盾！
所以，假设不成立。$S’$ 中的 $p-1$ 个数除以 $p$ 的余数互不相同，且都不为 $0$。

第二步：对应相等。
既然 $S’$ 的余数互不相同且不为 $0$，那么它们一定是 $1, 2, \dots, p-1$ 的某种重新排列。
所以，两组数的乘积模 $p$ 相等：
$$ a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod p $$

第三步：化简。
左边提取出 $p-1$ 个 $a$：
$$ a^{p-1} \cdot [1 \cdot 2 \cdots (p-1)] \equiv [1 \cdot 2 \cdots (p-1)] \pmod p $$
令 $W = (p-1)!$。
$$ a^{p-1} \cdot W \equiv W \pmod p $$
因为 $p$ 是质数，$W$ 与 $p$ 互质，可以两边消去 $W$。
$$ \therefore a^{p-1} \equiv 1 \pmod p $$
证毕。

四、 降维打击：习题实战

费马小定理最大的作用就是降幂。当指数很大时，我们可以利用 $a^{p-1} \equiv 1$ 将指数大幅减小。

核心技巧： 计算 $a^b \pmod p$ 时，先将指数 $b$ 除以 $p-1$，取余数。
即：若 $b = k(p-1) + r$，则 $a^b \equiv (a^{p-1})^k \cdot a^r \equiv 1^k \cdot a^r \equiv a^r \pmod p$。

基础题

题目 1： 求 $2^{35} \pmod 7$。
解析：
模数 $p=7$，由费马小定理知 $2^6 \equiv 1 \pmod 7$。
指数 $35 = 6 \times 5 + 5$。
$$ 2^{35} = (2^6)^5 \times 2^5 \equiv 1^5 \times 32 \equiv 4 \pmod 7 $$
答案： 4

进阶题

题目 2： 求 $2222^{5555} \pmod 7$。
解析：
这道题需要两步走：先化简底数，再化简指数。

1. 化简底数：
   $2222 \div 7 = 317 \dots 3$，所以 $2222 \equiv 3 \pmod 7$。
   原式转化为求 $3^{5555} \pmod 7$。
2. 化简指数：
   由费马小定理，$3^6 \equiv 1 \pmod 7$。
   $5555 \div 6 = 925 \dots 5$。
   所以 $3^{5555} \equiv 3^5 \pmod 7$。
3. 计算：
   $3^5 = 243$。
   $243 \div 7 = 34 \dots 5$。
   答案： 5

题目 3： 求 $5555^{2222} \pmod 7$。
解析：

1. 化简底数：$5555 \div 7 = 793 \dots 4$。原式 $\equiv 4^{2222} \pmod 7$。
2. 化简指数：$2222 \div 6 = 370 \dots 2$。
   原式 $\equiv 4^2 \pmod 7$。
3. 计算：$4^2 = 16 \equiv 2 \pmod 7$。
   答案： 2

挑战题（递归使用定理）

题目 4： 求 $8888^{2222} \pmod{37}$。
解析：
注意模数是 $37$，它是质数。由定理知 $a^{36} \equiv 1 \pmod{37}$。

1. 底数化小：
   $8888 \div 37 = 240 \dots 8$。
   原式 $\equiv 8^{2222} \pmod{37}$。
2. 指数化小：
   利用循环周期 $36$。
   $2222 \div 36 = 61 \dots 26$。
   原式 $\equiv 8^{26} \pmod{37}$。
   （此时数字依然很大，直接算 $8^{26}$ 很困难，我们需要技巧）
3. 底数变形：
   $8 = 2^3$。
   所以 $8^{26} = (2^3)^{26} = 2^{78}$。
4. 再次利用定理：
   现在问题变成了求 $2^{78} \pmod{37}$。
   再次利用周期 $36$。
   $78 = 36 \times 2 + 6$。
   所以 $2^{78} \equiv 2^6 \pmod{37}$。
5. 最终计算：
   $2^6 = 64$。
   $64 \div 37 = 1 \dots 27$。
   答案： 27