1. 费马的惊人断言——费马小定理的原始表述 十七世纪的法国律师、历史上最伟大的业余数学家、近代数论的先驱费马(Pierre de Fermat,1601~1665)在 1640 年10 月 18 日给他的朋友、数迷小团体成员之一弗莱尼科·德·贝西(Frénicle de Bessy, c. 1605~1675)的信中,写下了这样一段话(原文是法语): ? Tout nombre premier mesure infailliblement une des puissances - 1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné - 1 ? [拙译]“任何一个质数总能除尽任何几何级数中的某一项减1,且该项的指数是这个给定的质数减1的因子。” 费马的原话有点晦涩难懂,把它翻译成“大白话”(通用的数学语言)是这样的: 设 a 是任意一个整数[1],考虑以它为底的几何级数即 a 的各次方幂构成的数列: a, a2, a3, a4, a5, a6, a7, ..... 费马断言,给定任何一个质数 p ,在上述数列中一定能找到一个数 an,它减去 1 后是 p 的倍数,并且 n 是 p - 1 的因子。
下面,让我们先用实验的方法来检验费马的断言, 同时切身感受一下费马所揭示的神奇规律的魔力。作为好消息提前预告一声,在接下来我们的实验和探索中,我们将会发现比费马陈述的更多的东西,最终将导出一个“升级版的”或者说“加强版的费马小定理”,它比通常大家所说的费马小定理内容更丰富、更深刻,威力更强大。 为了方便记录我们的观察结果,我们先引入一个定义: 定义1(费马指数) 给定质数 p 和整数 a ,若 an - 1 能被 p 整除,称 n 为“费马指数”,更具体地说是“以 a 为底、关于 p 的费马指数”。 应该补充说明的是,我们定义的费马指数是正整数,不包括 0(当 n = 0 时,a0 - 1 = 1-1 = 0 恒能被 p 整除)。 费马的断言意味着对于任意的整数 a [1] 和质数 p 都能找到费马指数,我们先来看 a = 2 的特殊情形[2],2 的几何级数即 2 的各次方幂是大家非常熟悉的[3]: 21 = 2, 22 = 4, 23 = 8, 24 =16, 25 = 32, 26 = 64, 27 = 128, 28 = 256, 29 = 512, 210 = 1024, ..... 现在,就让我们动手来寻找隐藏在上面数列中的费马指数,对于较小的质数来说[4],这是容易找到的,而且我们很快发现它还还不止一个,似乎有无穷多个: ☆ p = 3 22 - 1 = 3, 24 - 1 = 15 = 3×5, 26 - 1 = 63 = 3×21, 28 - 1 = 255 = 3×85, 210 - 1 = 1023 = 3×341, ... 费马指数:2, 4, 6, 8, 10, ...... ☆ p = 5 24 - 1 = 15 = 5×3, 28 - 1 = 255 = 5×51, 212 - 1 = 4095 = 5×819, 216 - 1 = 65535 = 5×13107, ... 费马指数:4, 8, 12, 16, ...... ☆ p = 7 23 - 1 = 7 = 7×1, 26 - 1 = 63 = 7×9, 29 - 1 = 511 = 7×73, 212 - 1 = 4095 = 7×585, ... 费马指数:3, 6, 9, 12, ...... ☆ p = 11 210 - 1 = 1023 = 11×93, 220 - 1 = 1048575 = 11×95325, 230 - 1 = 1073741823 = 11×797612893, ... 费马指数:10, 20, 30, ......
观察上面的费马指数序列,你发现了什么规律?
规律是如此地明显,相信你一定看出来了,我们可以把它概括为下面这两个猜想(注意,在证明它们之前,我们所发现的“规律”只能称之为猜想): 猜想Ⅰ 若 n 为费马指数,则 n 的任何倍数都是费马指数。 猜想Ⅱ 所有的费马指数都是某个最小费马指数的倍数。 思考题 1. 在上面这两个猜想中,哪一个更容易证明? 2. 试证明上面的猜想Ⅰ。
稍加尝试你就会发现,猜想Ⅰ比猜想Ⅱ更容易证明,军事中的原则“避实击虚”、“先歼灭弱敌”也同样适用于数学,所以我们先来证明猜想Ⅰ,证明了之后它就升级为一个“引理”(lemma),因为它可以引导出某个更重要的更有价值的东西(它被称为“定理”)。 引理1 若 n 为费马指数,则 n 的任何倍数都是费马指数。换言之,对于给定的质数 p 和整数 a ,若 an - 1 能被 p 整除,则 amn - 1 (m 为正整数)也能被 p 整除 。
→ 另一个证明参见注[6].
如此轻松地证明了我们的第一个猜想(现在已经“升级”为引理1)让我们欢欣鼓舞,士气大振,带着这一辉煌的战果“乘胜追击”,猜想Ⅱ 似乎也马上可以“拿下”了。 思考题 试问能否由引理1证明我们前面的猜想Ⅱ——“所有的费马指数都是某个最小费马指数的倍数”,若能请给出证明,若不能请给出一个反例,并思考还需要再加上什么样的条件才能证明猜想Ⅱ成立。
以为有了引理1就可以证明猜想Ⅱ成立是一种错觉,很容易构造出反例,比如考虑2的倍数和3的倍数合在一起构成的集合: {2, 4, 6, 8, 10, ...} ∪ {3, 6, 9, 12, 15, ...} = {2, 3, 4, 6, 8, 9, 10, 12, 15, ...} 显然,该集合中的每个数的倍数都在该集合中,但并不是该集合中的所有数都是某个最小的数(2)的倍数。 看来,要证明猜想Ⅱ光靠引理1是不够的,我们还需要知道关于费马指数更多一点的信息,准确的说是加法方面的性质[6],我们可以把它归纳为下面这两个引理(是否和你料想的一样?): 引理2 若 m, n 为费马指数,则 m + n 也是费马指数。换言之,对于给定的质数 p 和整数 a ,若 am - 1 和 an - 1 能被 p 整除,则 am+n - 1 也能被 p 整除 。
引理3 若 m, n 为费马指数且 m > n ,则 m - n 也是费马指数。换言之,若 am - 1 和 an - 1 都能被 p 整除(m > n),则 am - n - 1 也能被 p 整除。
有了上面这三个引理,我们已经扫清了通向猜想Ⅱ的所有外围障碍,将它左右夹击,前后包抄,团团围住,可以发起最后的总攻了。 思考题 试利用引理1-3证明猜想Ⅱ,证明了之后它就同样晋升为引理,它是上面我们得到的所有结果的结晶:
有了引理4,全部的问题就归结为确定最小费马指数,鉴于其重要性,下面我们再重申一下它的定义,并引入相应的记号: 定义2(最小费马指数) 给定质数 p 和整数 a ,称使得 an - 1 能被 p 整除的最小的指数 n 为“最小费马指数”,更具体地说是“以 a 为底、关于 p 的最小费马指数”,用 F (a, p) 记之。[8] 前面我们已经找到了以 2 为底, p = 3, 5, 7, 11 时的各个最小费马指数: ☆ p = 3, 22 - 1 = 3 = 3 ×1, 最小费马指数 F (2, 3) = 2 ☆ p = 5, 24 - 1 = 15 = 5 × 3, 最小费马指数 F (2, 5) = 4 ☆ p = 7, 23 - 1 = 7 = 7 × 1, 最小费马指数 F (2, 7) = 3 ☆ p = 11, 210 - 1 = 1023 = 11 × 93, 最小费马指数 F (2, 11) = 10
接下来让我们看更多的质数,考察其最小费马指数的规律: ☆ p = 13, 212 - 1 = 4095 = 13 × 315, 最小费马指数 F (2, 13) = 12 ☆ p = 17, 28 - 1 = 255 = 17 × 15, 最小费马指数 F (2,17) = 8 ☆ p = 19, 218 - 1 = 262143 = 19 × 13797, 最小费马指数 F (2, 19) = 18 ☆ p = 23, 211 - 1 = 2047 = 23 × 89, 最小费马指数 F (2, 23) = 11 ☆ p = 29, 228 - 1 = 268435455 = 29 × 9256395, 最小费马指数 F (2, 29) = 28 ☆ p = 31, 25 - 1 = 31 = 31 × 1, 最小费马指数 F (2, 31) = 5 ☆ p = 37, 236 - 1 = 68719476735 = 37 × 1857283155, 最小费马指数 F (2, 37) = 36 ☆ p = 41, 220 - 1 = 1048575 = 41 × 25575, 最小费马指数 F (2, 41) = 20 ☆ p = 43, 214 - 1 = 16383 = 43 × 381, 最小费马指数 F (2, 43) = 14 ☆ p = 47, 223 - 1 = 8388607 = 47 × 178481, 最小费马指数 F (2, 47) = 23 思考题 观察上面的各个最小费马指数,你发现了什么规律?
相信目光锐利的读者一定发现了这个规律:有时候最小费马指数 F (2, p) 就等于 p - 1 ,而当它不等于 p - 1 的时候,它的某个倍数一定等于 p - 1 ,用更精炼的语言,我们可以把它概括为: 猜想Ⅲ 最小费马指数 F (2, p) 是 p - 1 的因子。 紧接着我们自然想到,这可以推广到以其他整数为底的最小费马指数,即我们马上又有下面的猜想: 猜想Ⅳ 任何最小费马指数 F (a, p) 都是 p - 1 的因子。
思考题 请思考如何证明猜想Ⅲ和它的推广——猜想Ⅳ。
要直接证明猜想Ⅳ(甚至它的特殊情形猜想Ⅲ)是相当困难的,在正面进攻无从下手,或者找不到“突破口”的时候,希望你能想起下面这个解决数学问题的基本策略(在《从勾股定理到费马大定理》一文中,我们讲过同样的策略): 倘若你对原问题无计可施,尝试改变问题的形式,将它转化成等价的新问题,直到能找到“突破口”或“切入点”为止。 思考题 请思考怎么样改变猜想Ⅳ的形式,将它转化成一个等价的新命题。
如果猜想Ⅳ成立,根据引理1,我们马上有下面的推论,它就是大家通常所说的、可以在教科书和网上查到的费马小定理,我们称之为“普通版的费马小定理”: 对于任意质数 p 和不是 p 的倍数的整数 a , a p - 1 - 1 都能被 p 整除。 反过来,如果我们证明了命题1,也就等于证明了猜想Ⅳ。 因为命题Ⅰ意味着 p - 1 是费马指数,根据引理4,任何费马指数都是最小费马指数的倍数,所以 p - 1 是最小费马指数的倍数,即最小费马指数是 p - 1 的因子。 基于我们前面的劳动,我们看出猜想Ⅳ和命题Ⅰ即“普通版的费马小定理”是等价的,在下一节我们将讲述后者的证明(希望你能先独立自主地尝试证明它,当然这有相当的难度,毕竟连费马本人也没有能够给出一个证明)。 在此我们先总结一下迄今为止我们的探索和发现的成果,我们可以把它归纳为下面的命题: 给定质数 p 和不是 p 的倍数的整数 a ,称使得 an - 1 能被 p 整除的最小的指数 n 为“最小费马指数”,用 F (a, p) 记之,则 (1) 最小费马指数 F (a, p) 是 p - 1 的因子。 (2) an - 1 能被 p 整除 <=> n 是最小费马指数 F (a, p)的倍数。 显然,从命题Ⅱ——“加强版的费马小定理”很容易推导出命题Ⅰ——“普通版的费马小定理”,但反过来,要想从后者推导前者,却必须依靠我们前面建立的引理,所以前者是更强的命题,这就是为什么我们称它为“加强版”。在后面我们讲到费马小定理的应用时,我们更能从很多实际例子体会到它的威力。
命题Ⅱ——“加强版的费马小定理”是我们目前得到的最好的结果,但它并不是我们探索之旅的终点,还有一个很大的未解之谜留待我们进一步的探索(不知道你想到了没有): 那就是我们只知道最小费马指数 F (a, p) 是 p - 1 的因子,但对它究竟怎样依赖于 a 和 p 却一无所知…… 这里隐藏着比费马发现的更深邃更难以窥测的秘密!
思考题 再次仔细观察前面以 2 为底, p = 3, 5, 7, 11, 13, 17,...... 的各个最小费马指数,除了发现 F (2, p) 是 p - 1 的因子之外,你能发现更进一步的规律吗? 请试着给出你对下面这两个问题的猜想: 1. 什么时候最小费马指数 F (2, p) 等于 p - 1 ? 2. 什么时候最小费马指数 F (2, p) 不等于 p - 1 ,而等于它的一个真因子(即不等于1和它本身的因子)?
To be continued(à suivre) [注1] p 的倍数除外,这是费马的疏漏(因为若 a 是 p 的倍数, an - 1 除以 p 的余数恒等于 -1,故永远不可能被 p 整除)。
[注2] 这是使费马的断言有意义的正整数 a 的最小取值(当 a = 1 时, an
- 1 恒等于 0,显然能被所有质数整除)。 [注3] 注意从费马的断言可以推知:如果我们对数列 2n - 1( n = 1, 2, 3, 4, ...)中的每项进行质因子分解,将得到所有的质数(除 2 外)! 这本身就是一个非凡的论断。 特别地,如果 2n - 1 本身是质数,那么它就是梅森质数或者说梅森素数(Mersenne prime)! 作为练习试证明:若 2n - 1 是质数,那么 n 一定是质数。
[注5] 该恒等式是大家熟悉的平方差公式 x2 -1 = (x-1)(x+1) 的推广,要证明它是很容易的,只要把左边乘出来就行了:
[注8] 用群论的术语讲,最小费马指数 F(a, p)等于 a 在 Zp 的乘法群中的阶(order)。 |
|