从数论基础到现代密码学核心，深入理解这一改变世界的数学定理。本文提供详尽的证明、应用案例及计算技巧，助你彻底掌握 费马小定理。
费马小定理（Fermat's Little Theorem）是数论中的一个基本定理，描述了整数在模素数运算下的周期性性质。它在现代密码学、计算机科学以及纯数学领域都有着极其重要的地位。
若 p 是一个质数，a 是一个整数，且 a 不被 p 整除（即 gcd(a, p) = 1），则：
ap-1 ≡ 1 (mod p)
或者等价地写作：ap ≡ a (mod p)
让我们验证一下：设 p = 5, a = 2。
1. p = 5 是质数。
2. a = 2 与 5 互质。
3. 根据定理，25-1 = 24 = 16。
4. 16 除以 5 的余数是 1。即 16 ≡ 1 (mod 5)。
定理成立！
理解证明过程有助于深入掌握定理的本质。这里介绍两种最常见的证明方法：数学归纳法和群论证明。
我们要证明对于任意正整数 a，ap ≡ a (mod p) 成立。
基础步骤：当 a = 1 时，1p = 1 ≡ 1 (mod p)，显然成立。
归纳假设：假设当 a = k 时，kp ≡ k (mod p) 成立。
归纳步骤：考虑 a = k + 1 的情况。
根据二项式定理：
(k + 1)p = kp + C(p,1)kp-1 + ... + C(p,p-1)k + 1
其中 C(p,i) 是组合数。当 1 ≤ i ≤ p-1 时，C(p,i) 都能被 p 整除（因为 p 是质数）。
因此，在模 p 的意义下，中间的所有项都变为 0。
(k + 1)p ≡ kp + 1 (mod p)
由归纳假设 kp ≡ k (mod p)，所以：
(k + 1)p ≡ k + 1 (mod p)
证毕。若 gcd(a, p) = 1，则可在 ap ≡ a (mod p) 两边同除以 a，得到 ap-1 ≡ 1 (mod p)。
考虑模 p 的既约剩余系（即 1, 2, ..., p-1）。这些数在模 p 乘法下构成一个群 Zp，阶为 p-1。
对于任意 a，若 gcd(a, p) = 1，则 a 属于这个群。
根据拉格朗日定理（Lagrange's Theorem），群中任意元素的阶必须整除群的阶。
因此，ap-1 = e（单位元），即在模 p 下 ap-1 ≡ 1 (mod p)。
另一种直观解释：
考虑集合 S = {a, 2a, 3a, ..., (p-1)a}。
由于 a 与 p 互质，S 中的元素模 p 后互不相同，且都不为 0。因此 S 模 p 的余数集合就是 {1, 2, ..., p-1} 的一个排列。
将 S 中所有元素相乘：
a 2a ... (p-1)a ≡ 1 2 ... (p-1) (mod p)
ap-1 (p-1)! ≡ (p-1)! (mod p)
因为 (p-1)! 与 p 互质，可以约去：
ap-1 ≡ 1 (mod p)
证毕。
费马小定理不仅仅是纸面上的数学游戏，它是现代信息安全的基石之一。以下是其主要应用场景：
RSA 算法的安全性基于大数分解的困难性，但其密钥生成和加解密过程大量依赖欧拉定理（费马小定理的推广）。通过费马小定理，我们可以高效地进行模幂运算，确保数据在传输过程中的保密性。
在生成大质数（如 RSA 密钥对中的 p 和 q）时，需要快速判断一个数是否为质数。费马小定理提供了逆向思维：如果 an-1 ≢ 1 (mod n)，则 n 一定是合数。虽然存在卡迈克尔数等反例，但它是高效的初步筛选工具。
在某些哈希算法和循环冗余校验（CRC）的变种中，模运算的性质被用来检测数据完整性。费马小定理提供的模运算规律有助于设计更高效的校验机制。
在 RSA 中，我们需要计算 c = me mod n，其中 m, e, n 都是非常大的整数（数百位甚至数千位）。直接计算 me 会得到一个天文数字，内存无法存储。
利用费马小定理及其推广的欧拉定理，我们可以将指数对 φ(n) 取模，从而极大地减小指数的大小，配合“快速幂算法”（Square-and-Multiply），可以在极短时间内完成计算。
对于网民来说，最实用的技能是利用 费马小定理 来简化大指数的模运算。以下是详细步骤和示例。
| 问题 | 分析过程 | 简化计算 | 结果 |
|---|---|---|---|
| 计算 3100 mod 7 | p=7 是质数，gcd(3,7)=1。根据定理，36 ≡ 1 (mod 7)。 | 100 = 6 16 + 4。所以 3100 = (36)16 34 ≡ 116 34 ≡ 81 (mod 7)。 | 81 mod 7 = 4 |
| 计算 21000 mod 13 | p=13，指数对 12 取模。1000 = 12 83 + 4。 | 21000 ≡ 24 (mod 13) = 16 (mod 13)。 | 3 |
| 计算 5200 mod 11 | p=11，指数对 10 取模。200 是 10 的倍数。 | 5200 = (510)20 ≡ 120 (mod 11)。 | 1 |
def fermat_little_theorem_test(a, p):
"""
简单的费马素性测试
如果返回 False，则 p 一定是合数
如果返回 True，则 p 可能是质数（也可能是卡迈克尔数）
"""
if p == 2:
return True
if p % 2 == 0:
return False
# 计算 a^(p-1) mod p
result = pow(a, p - 1, p)
return result == 1
示例：测试 7 是否为质数
print(fermat_little_theorem_test(2, 7)) # 输出: True
print(fermat_little_theorem_test(2, 15)) # 输出: False (15是合数，2^14 mod 15 != 1)
费马小定理 以法国数学家皮埃尔·德·费马（Pierre de Fermat）的名字命名，但他并非第一个发现它的人。
有证据表明，印度数学家可能更早发现了这一定理的特例，但未形成通用理论。
费马在10月12日给法布尔·德·梅斯纳尔的信中首次明确陈述了该定理。他写道：“如果p是质数，且a不被p整除，则 a^(p-1) - 1 能被 p 整除。”
欧拉在《Commentarii academiae scientiarum Petropolitanae》中发表了该定理的第一个正式证明。他还将其推广到了欧拉定理，即 a^φ(n) ≡ 1 (mod n)。
Rivest, Shamir 和 Adleman 提出了 RSA 公钥加密算法，费马小定理及其推广成为其理论核心，使互联网安全成为可能。
在学习和应用 费马小定理 时，网民常犯以下错误：
A: 费马小定理 是欧拉定理在模数 n 为质数时的特例。欧拉定理形式为 a^φ(n) ≡ 1 (mod n)，其中 φ(n) 是欧拉函数。当 n=p（质数）时，φ(p)=p-1，即退化为费马小定理。
A: 它是公钥密码学 RSA 算法的基础之一，用于大数的模幂运算加速和素性测试（如费马素性测试）。它帮助计算机高效处理极大整数的加密解密过程。
A: 利用费马小定理可以将指数对 p-1 取模，从而大幅减小指数规模。例如计算 2^100 mod 7，因为 7 是质数，指数 100 对 6 取模得 4，故 2^100 ≡ 2^4 ≡ 16 ≡ 2 (mod 7)。
A: 卡迈克尔数是一类特殊的合数，它们满足费马小定理的结论，即对于所有与 n 互质的 a，都有 a^(n-1) ≡ 1 (mod n)。这使得费马素性测试对它们失效。最小的卡迈克尔数是 561 = 3 × 11 × 17。