一分钟数学——费马小定理

在正式讲费马小定理之前，我们先来做一个热身运动。什么是同余≡？如果a÷b余d，我们称amod...



在正式讲费马小定理之前，我们先来做一个热身运动。

如果 a ÷ b 余 d，我们称 a mod b = d，这是一个在算法领域中经常运用的一个运算，也称模运算。同时也引出了同余：a ≡ d（mod b），意为 a mod b 和 d mod b 结果相等。试试关于同余的简单题目吧：13 ≡ 3（mod N），其中 N 为大于 1 的正整数，问N 最小是多少呢？13 = aN+p，3 = bN+p，两者相减以消去 p，得到 10 = N(a-b)，也就是 N 为 10 的约数，N 最小为 2。先来看一下费马小定理的具体内容：已知 p 为质数且整数 a 与 p 互质，那么必有：a ^ (p-1) ≡ 1 ( mod p )。这个同余式也就意味着，a ^ (p-1) mod p = 1。真神奇，为什么呢？证明如下：将 a 分别 × 1，2，……，p -1，得到 a，2a，3a，……，(p-1) a，再分别对 p 取余。如果其中有两个余数相同，不妨设为 ba 和 ca，则 ba ≡ ca（mod p），b 和 ｃ不相同。ba = p × m + d，ca = p × n + d，两者相减得到：(b-c)a = (m-n)p，d 就消去了。因为ｂ和ｃ不同，所以 (b-c) × a 不为 0，且 b 和 c 均小于 p，则 (b-c) < p，(a,p)=1。因此 a 和 (b-c) 都不是 p 的倍数，原等式不成立，b-c = 0。所以 a，2a，3a，……，(p-1) a 中 mod p 的结果互不相同，由于 a 和 p 互质，余数也都不为 0。那么这 p-1 个余数分别是 1 ~ p-1，但并不一定按照这个顺序。现在将 a，2a，3a，……，(p-1)a 相乘，得到 (p-1)! × （a ^ (p-1)）。这还能够表示成 (p × b1 + 1) × (p × b2 + 2) × (p × b3 + 3) × …… × (p × b(p-1) + p - 1)，因为必有一个积 mod p = 1，必有一个积 mod p = 2，……，可以一个不漏地写成上述连乘算式。将其分解开来，可以写成：p × q1 + (p-1)!。设（a ^ (p-1)）= p × q2 + D，那么总乘积为 (p-1)! × （p × q2 + D）= p × q2 × (p-1)! + (p-1)! × D，同时与 p × q1 + (p-1)!相等。接着等式两边移项：p ×（(p-1)! × q2 - q1）= (p-1)! ×（1-D），D < p。那么 (p-1)! 和 (1-D) 的约数中都没有 p，因此等式两边都为 0。(p-1)! 一定不为 0，所以 (1-D) = 0，D = 1。D 就是之前假设的 a ^ (p-1) mod p，得证。在理解了费马小定理之后，我们来讲讲费马小定理的历史背景吧。1636年，费马发现了这个有趣的定理，在 1640 年的一封信中第一次表示了 a ^ (p-1) ≡ 1 ( mod p ) 的书写方式。他在信中还提出了 a 是质数的条件，但现在我们都很清楚这是不必要的。

可是，费马并没有给出证明过程。直到 1736 年，欧拉出版的一篇名为“一些与素数有关的定理的证明”的论文中第一次提出证明，但人们从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。表面很简单的一个同余式，竟能引起许多数学家的关注，还是和费马小定理在数论中的作用息息相关。

其实，关于费马，我之前曾经介绍过他的另一个著名的定理：费马大定理。也非常有意思。有兴趣的朋友们可以去看看以下链接：

数学小故事 －－费马大定理

    关注 无忧公主的数学时间