一则 400 年数论定理的简单证明

luyuanhong

一则 400 年数论定理的简单证明

原创  围城里的猫  MathSpark  2025 年 03 月 25 日

有时候，最简单的证明能最深刻地展现数学家的思维方式。


图注：费马

费马小定理是一个优美的数论结果，它指出：对于任意整数 a 和任意素数 p ，表达式 a^p-a 总是能被 p 整除。

例如，当  a=4 、p=3 时，a^p-a=4^3-4=64-4=60 ，而 60 正好可以被 3 整除。

费马最早在 1640 年的一封信中提出了这一结果，但他表示自己不会给出证明，因为证明太长，无法写进这封信中。

众所周知，费马常以“我已有证明，但纸太小写不下”而著称。他曾经用类似理由声称自己证明了另一个著名命题，结果那个问题最终宕机了解决长达 350 年，并花费了超过 100 页的复杂数学推理才得以证明。

不过这次没那么久。大约在一个世纪后，欧拉首次发表了该定理的证明（实际上是欧拉定理的推论）。


图注：欧拉

有证据表明，莱布尼茨在欧拉之前约 50 年就已经通过类似方法完成了证明，只是他从未将其发表。


图注：莱布尼茨

如今，关于费马小定理的证明已有很多种方法，比如多项式、幂积或群论等。但在这篇文章中，我想展示一种非常简洁的证明。我认为它不仅很好地体现了如何从基本原理出发解决问题，同时也很好地展示了纯数学家在思考离散对象时的方式。

1. 有序集合上的排列

定义 1.1 ：

设你有一个有限的有序对象集合 S 。我们定义在 S 上的简单排列为：将集合最后一个元素移除，并将其放置到集合的最前端。

例子 1.2 ：

若 S={a,b,d,g,r,k} ，而 T={g,r,k,a,b,d} ，那么 T 可由 S 进行三次简单排列得到。

注意：一系列简单排列最终会将集合恢复为其原始顺序。在极端情况下，这将在 m 次简单排列后发生，其中 m 为集合的大小。

当然，在某些情况下也可能更早发生，例如集合 {b,a,b,a} 在两次简单排列后就会恢复原状。然而，我们现在来探讨当集合大小为质数时会发生什么。

引理 1.3：

若 S 是一个大小为质数 p 的有序集合，且 S 中至少包含两个不同的元素，那么要使 S 通过简单排列恢复为原始状态，所需的最少排列次数正好为 p 。

证明：

设 k 是使 S 恢复为原始顺序所需的最小简单排列次数。那么，S 必须由一个长度为 k 的重复有序子集构成。因此 k 必须整除 p 。由于 p 是质数，因此 k=1（此时 S 中所有元素相同）或 k=p 。

2. 证明费马小定理

定理 2.1（费马小定理）：对于任意整数 a 和素数 p ，a^p-a 能被 p 整除。

证明：

设 A 是包含 a 个不同元素的集合，考虑从中选出长度为 p 的所有有序集合。这样的集合共有 a^p 个，其中有 a 个是平凡集合（即所有元素都相同）。因此，有 a^p-a 个集合至少包含两个不同元素（我们称之为非平凡集合）。

根据引理 1.3 ，如果我们选取一个任意的非平凡集合，对其进行一系列简单排列，将会生成 p 个不同的非平凡集合。进一步地，若 m 和 n 是两个不同的非平凡集合，且 n 不能通过对 m 进行一系列简单排列得到，那么以 m 和 n 为起点所生成的两个集合族 M 和 N 必然互不相交（否则若 N 中的某个元素 n* 也在 M 中，由于 n 可由 n* 排列而得，进而 n 也应在 M 中，矛盾）。因此我们证明了这些非平凡集合可以被划分为互不重叠的大小为 p 的子集，因此 a^p-a 一定能被 p 整除。

例子 2.2 ：

若 A={a,b,c,d} 且 p=2 ，那么有 4 个平凡集合 {a,a}、{b,b}、{c,c} 和 {d,d} ，以及 12 个非平凡集合，它们来自以下 6 个有序集合 {a,b}、{a,c}、{a,d}、{b,c}、{b,d} 和 {c,d} 对它们做一次简单排列（即反转）的集合。这使非平凡集合被划分为 6 个不重叠的子集，每个子集包含相同元素的不同排列。

例子2.3：

若 A={1,2,3,4,5} 且 p=5 ，考虑两个非平凡的有序集合 {1,2,1,2,1} 和 {2,2,1,1,1} 。后者无法通过对前者进行简单排列得到。前者通过简单排列生成以下 5 个集合：{1,2,1,2,1}、{1,1,2,1,2,}、{2,1,1,2,1}、{1,2,1,1,2}、{2,1,2,1,1} 。后者生成：{2,2,1,1,1}、{1,2,2,1,1}、{1,1,2,2,1}、{1,1,1,2,2}、{2,1,1,1,2} 。这两组集合彼此不相交。

当然如果你学过一点抽象代数，可以把证明写的更短。



围城里的猫