网站首页 (Homepage) 欢   迎   访   问  谢  国  芳 (Roy  Xie) 的  个  人  主  页
Welcome to Roy Xie's Homepage
返回 (Return)

 

神奇的费马小定理 (1)

 ——从实验、观察、发现到猜想和证明

      谢国芳(Roy Xie)                               Email:  roixie@163.com   

章节目录

1. 费马的惊人断言——费马小定理的原始表述

2. 我们的探索之旅——从实验、观察、发现到猜想和证明

  2.1 费马指数和最小费马指数

  2.2 “普通版费马小定理”和“加强版费马小定理”

  2.3 对最小费马指数更深入的探究

3. 费马小定理的证明 

 

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, a5a6, a7,  .....

费马断言,给定任何一个质数 p ,在上述数列中一定能找到一个数 an,它减去 1 后是 p 的倍数,并且 n p - 1 的因子。

 

2.  我们的探索之旅——从实验、观察、发现到猜想和证明

下面,让我们先用实验的方法来检验费马的断言, 同时切身感受一下费马所揭示的神奇规律的魔力。作为好消息提前预告一声,在接下来我们的实验和探索中,我们将会发现比费马陈述的更多的东西,最终将导出一个“升级版的”或者说“加强版的费马小定理”,它比通常大家所说的费马小定理内容更丰富、更深刻,威力更强大。

2.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, 2= 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 整除 。

[ 注5 ]

另一个证明参见注[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 所有的费马指数都是某个最小费马指数的倍数。

证明



Lemma 4 Lemma 1 Lemma 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 的因子。

 

思考题

请思考如何证明猜想Ⅲ和它的推广——猜想Ⅳ。

 

 

2.2  “普通版费马小定理”和“加强版费马小定理”

要直接证明猜想Ⅳ(甚至它的特殊情形猜想Ⅲ)是相当困难的,在正面进攻无从下手,或者找不到“突破口”的时候,希望你能想起下面这个解决数学问题的基本策略(在《从勾股定理到费马大定理》一文中,我们讲过同样的策略)

倘若你对原问题无计可施,尝试改变问题的形式,将它转化成等价的新问题,直到能找到“突破口”或“切入点”为止。

思考题

请思考怎么样改变猜想Ⅳ的形式,将它转化成一个等价的新命题。


 

 

 

如果猜想Ⅳ成立,根据引理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)的倍数。

显然,从命题Ⅱ——“加强版的费马小定理”很容易推导出命题Ⅰ——“普通版的费马小定理”,但反过来,要想从后者推导前者,却必须依靠我们前面建立的引理,所以前者是更强的命题,这就是为什么我们称它为“加强版”。在后面我们讲到费马小定理的应用时,我们更能从很多实际例子体会到它的威力。

 

2.3  对最小费马指数更深入的探究

命题Ⅱ——“加强版的费马小定理”是我们目前得到的最好的结果,但它并不是我们探索之旅的终点,还有一个很大的未解之谜留待我们进一步的探索(不知道你想到了没有)

那就是我们只知道最小费马指数 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 一定是质数。

证明

 

[注4] 注意当 a = 2 时,质数 p 不能取 2。 参见上面的注[1]

[注5] 该恒等式是大家熟悉的平方差公式 x2 -1 = (x-1)(x+1) 的推广,要证明它是很容易的,只要把左边乘出来就行了:

[注6] 引理1只确立了费马指数的乘法性质——整数的乘法归根结底只是同一个元素的累加,而引理2引理3是关于两个不同(当然也可以相同)元素的加法和减法的,所以更基本。

实际上从引理2很容易推导出引理1(只要将同一个费马指数相加 N 次就行了)。

[注8] 用群论的术语讲,最小费马指数 F(a, p)等于 a 在 Zp 的乘法群中的阶(order)。