取数字 2，不断提高它的幂次。把每个结果除以 7，记下余数：

幂 $2^1$ $2^2$ $2^3$ $2^4$ $2^5$ $2^6$
值 2 4 8 16 32 64
除以 7 的余数 2 4 1 2 4 1

到 $2^6$，余数是 1。再试试 3 和质数 5：$3^4=81$，除以 5 余 1。再试 10 和质数 13：$10^{12}=1\,000\,000\,000\,000$，除以 13 也余 1。

是巧合吗？不是。这就是费马小定理。

定理内容

如果 $p$ 是质数，$a$ 是不被 $p$ 整除的整数，那么 $a^{p-1}$ 除以 $p$ 余 1。用高斯 1801 年创立的同余记号写作：

$$a^{p-1}\equiv1\pmod p.$$

“小”字只是为了与大定理区分。实际上，小定理要有用得多。

选择底数和一个质数。当底数是该质数的倍数时，指数为 p − 1 的版本的前提条件不成立。

一封没有证明的信

费马在 1640 年 10 月 18 日写给数学家贝尔纳·弗雷尼克·德贝西的信中宣布了这个定理。和往常一样，他没有给出证明：

我本想把证明寄给你，只怕它太长。

— 费马致弗雷尼克·德贝西的信（1640）

第一个发表的证明出自莱昂哈德·欧拉之手，时间是 1736 年，几乎晚了一百年。后来人们才知道，莱布尼茨在 1683 年左右也有一个证明，但从未发表。

一个“洗牌”证明

我们对 $p=7$、$a=3$ 证明这个定理；一般情形的论证完全相同。

写下 $1,2,3,4,5,6$。把每个数乘以 3，再取除以 7 的余数：

$$3,\ 6,\ 9\to2,\ 12\to5,\ 15\to1,\ 18\to4.$$

余数是 $3,6,2,5,1,4$：与原来的数相同，只是顺序打乱了。这种情况总会发生。没有余数会是 0，因为 $p$ 既不整除 $a$ 也不整除 $k$。也不会有重复的余数：如果 $ai$ 与 $aj$ 余数相同，$p$ 就整除 $a(i-j)$，从而整除 $i-j$，而对于 1 到 $p-1$ 之间两个不同的数，这是不可能的。

既然两组数相同，它们的乘积除以 7 的余数也相同：

$$(3\cdot1)(3\cdot2)\cdots(3\cdot6)\equiv1\cdot2\cdots6\pmod7,$$

即 $3^6\cdot6!\equiv6!\pmod7$。由于 7 是质数且不整除 $6!$，可以约去 $6!$，得到 $3^6\equiv1\pmod7$。验证：$3^6=729=7\cdot104+1$。

不费力地算巨大的数

$3^{100}$ 除以 7 的余数是多少？没有这个定理，就得算出一个 48 位的数。有了它：$3^6\equiv1$，而 $100=6\cdot16+4$。所以

$$3^{100}=\left(3^6\right)^{16}\cdot3^4\equiv1^{16}\cdot81\equiv4\pmod7.$$

这种化简巨大幂次的能力，正是保护网上购物和密码的 RSA 系统的基础。RSA 使用的是欧拉对这个定理的推广，详见欧拉专题。

小心逆命题

如果 $p$ 是质数，那么 $a^{p-1}\equiv1$。但逆命题不成立：一个数可能通过检验却不是质数。最小的“骗子”是 $561=3\cdot11\cdot17$，对于每个与 561 没有公因数的 $a$，都有 $a^{560}\equiv1\pmod{561}$。这样的数叫作卡迈克尔数。因此，这个定理可以证明一个数不是质数，但单靠它不能证明一个数是质数。

练习：3¹⁰ 除以 11 的余数是多少？

11 是质数且不整除 3，所以 $3^{10}\equiv1\pmod{11}$，余数为 1。验证：$3^{10}=59\,049=11\cdot5368+1$。

练习：2¹⁰⁰ 除以 13 的余数是多少？

$2^{12}\equiv1\pmod{13}$，而 $100=12\cdot8+4$。所以 $2^{100}\equiv2^4=16\equiv3\pmod{13}$，余数为 3。

资料来源： 费马传记，MacTutor。

费马的全部主题 · ← 极大值与极小值：面积最大的矩形 · 费马数：一个猜想和一个反例 →

图片来源.