费马小定理费马小定理是数论中的一个定理：假如a是一个整数，p是一个质数，那么是p的倍数，可以表示为如果a不是p的倍数，这个定理也可以写成这个书写方式更加常用。

（符号的应用请参见同余。

）证明若n不能整除a - b，x>0，(x,n)=1，则n也不能整除x(a-b)。

取整数集A为所有小于p的集（A构成p的完全剩余系,即A 中不存在两个数同余p），B是A中所有的元素乘以a组成的集合。

因为A中的任何两个元素之差都不能被p整除，所以B 中的任何两个元素之差也不能被p整除。

因此即在这里W=1·2·3·...·(p-1)，且(W, p) = 1，因此将整个公式除以W即得到：广义费马小定理是欧拉定理的一个特殊情况：如果n和a的最大公约数是1，那么这里φ(n)是欧拉商数。

欧拉商数的值是所有小于n的自然数中与n没有公约数的数的个数。

假如n是一个素数，则φ(n) = n-1，即费马小定理。

在费马小定理的基础上，费马提出了一种测试素数的算法；尽管它是错误。

神奇的费马小定理(1)——从实验、观察、发现到猜想和证明谢国芳（Roy Xie）Email: **************章节目录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, a5, a6, a7, .....费马断言，给定任何一个质数p ，在上述数列中一定能找到一个数a n，它减去1后是p 的倍数，并且n 是p - 1的因子。

2.我们的探索之旅——从实验、观察、发现到猜想和证明下面，让我们先用实验的方法来检验费马的断言, 同时切身感受一下费马所揭示的神奇规律的魔力。

作为好消息提前预告一声，在接下来我们的实验和探索中，我们将会发现比费马陈述的更多的东西，最终将导出一个“升级版的”或者说“加强版的费马小定理”，它比通常大家所说的费马小定理内容更丰富、更深刻，威力更强大。

2.1费马指数和最小费马指数为了方便记录我们的观察结果，我们先引入一个定义：定义1（费马指数）给定质数p和整数a，若a n- 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 = 322 - 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 = 524 - 1 = 15 = 5×3, 28 - 1 = 255 = 5×51, 212 - 1 = 4095 = 5×819, 216- 1 = 65535 = 5×13107, ...费马指数：4，8，12，16, ......☆p = 723 - 1 = 7 = 7×1, 26 - 1 = 63 = 7×9, 29 - 1 = 511 = 7×73, 212 - 1 =4095 = 7×585, ...费马指数：3，6，9，12, ......☆p = 11210 - 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，若a n- 1 能被p整除，则a mn- 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，若a m- 1 和a n- 1 能被p整除，则a m+n- 1 也能被p整除。

引理3若m, n 为费马指数且m > n ，则m - n 也是费马指数。

换言之，若a m- 1 和a n- 1 都能被p整除（m > n），则a m - n- 1 也能被p整除。

有了上面这三个引理，我们已经扫清了通向猜想Ⅱ的所有外围障碍，将它左右夹击，前后包抄，团团围住，可以发起最后的总攻了。

思考题试利用引理1-3证明猜想Ⅱ，证明了之后它就同样晋升为引理，它是上面我们得到的所有结果的结晶：引理4 所有的费马指数都是某个最小费马指数的倍数。

有了引理4，全部的问题就归结为确定最小费马指数，鉴于其重要性，下面我们再重申一下它的定义，并引入相应的记号：定义2（最小费马指数）给定质数p和整数a，称使得a n- 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 的因子。