费马小定理_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
费马小定理
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
下载文档到电脑，查找使用更方便
还剩17页未读，继续阅读
你可能喜欢在学群论，虽然说证了拉格朗日定理之后费马小定理就很显然了，但是拉格朗日定理的证明很繁琐啊陪集什么的。。有没有办法绕开拉格朗日定理。。
如果我理解正确的话，题主的意思大概是，用群论但不用拉格朗日定理来证明费马小定理……既然费马小定理原是数论中的定理，那么若是把范围限定在有限交换群，我确有一个办法：对于有限交换群，令. 任取，注意到把中全部元素乘上之后，得到的依然是中的全部元素。也就是说，.于是，群里所有元素的乘积应该等于乘上之后的所有元素的乘积。然后把所有乘上的合并（因为是交换群），约去所有其他元素，即得证。题主满意否？那么就这样=w=
已有帐号？
无法登录？
社交帐号登录费马小定理的证明_列表网问答
费马小定理的证明
费马小定理的证明
『费马小定理的证明』相关搜索
(C) 列表网&京ICP证100421号&京ICP备号-1&琼公网安备08神奇的费马小定理 (1)
&——从实验、观察、发现到猜想和证明
&&&&& 谢国芳（Roy Xie）&&&&&&&&&&&&&&&&&&&& &&&& &
&&&Email:&
1.& 费马的惊人断言——费马小定理的原始表述
十七世纪的法国律师、历史上最伟大的业余数学家、近代数论的先驱费马(Pierre de
Fermat，）在 1640 年10 月 18 日给他的朋友、数迷小团体成员之一弗莱尼科·德·贝西（Frénicle
de Bessy, c. ）的信中，写下了这样一段话（原文是法语）：
& 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 是任意一个整数，考虑以它为底的几何级数即
a 的各次方幂构成的数列：
a, a2, a3, a4, a5,&a6, a7,& .....
费马断言，给定任何一个质数 p ，在上述数列中一定能找到一个数 an，它减去 1 后是
p 的倍数，并且
p - 1 的因子。
我们的探索之旅——从实验、观察、发现到猜想和证明
下面，让我们先用实验的方法来检验费马的断言,
同时切身感受一下费马所揭示的神奇规律的魔力。作为好消息提前预告一声，在接下来我们的实验和探索中，我们将会发现比费马陈述的更多的东西，最终将导出一个“升级版的”或者说“加强版的费马小定理”，它比通常大家所说的费马小定理内容更丰富、更深刻，威力更强大。
费马指数和最小费马指数
为了方便记录我们的观察结果，我们先引入一个定义：
定义1（费马指数） 给定质数 p
p 整除，称 n 为“费马指数”，更具体地说是“以
a 为底、关于
p 的费马指数”。
应该补充说明的是，我们定义的费马指数是正整数，不包括
n = 0 时，a0
= 0 恒能被
p 整除）。
费马的断言意味着对于任意的整数 a
p 都能找到费马指数，我们先来看 a =
的特殊情形，2 的几何级数即 2 的各次方幂是大家非常熟悉的：
21 = 2, 22& = 4, 23 = 8,&
24 =16,& 25 = 32, &26
= 64,& 27 = 128,& 28 =
256, 29 = 512,& 210 = 1024,&&& .....
现在，就让我们动手来寻找隐藏在上面数列中的费马指数，对于较小的质数来说，这是容易找到的，而且我们很快发现它还还不止一个，似乎有无穷多个：
&☆& p = 3&
15 = 3×5,&& 26
- 1 = 63 =
3×21,& 28
255 = 3×85,& 210
1023 = 3×341, ...
费马指数：2， 4， 6， 8， 10, ......
☆& p = 5&
15 = 5×3,&& 28
255 = 5×51,&& 212
- 1 = 4095 =
5×819,&& 216
65535 = 5×13107, ...
费马指数：4， 8， 12， 16, ......
7 = 7×1,&& 26
63 = 7×9,&& 29
- 1 = 511 =
7×73,&& 212
4095 = 7×585,& ...
费马指数：3， 6， 9， 12, ......
1023 = 11×93,&& 220
- 1 = 1048575 =
11×95325,&& 230
11×,&& ...
费马指数：10， 20， 30,& ......
观察上面的费马指数序列，你发现了什么规律？
规律是如此地明显，相信你一定看出来了，我们可以把它概括为下面这两个猜想（注意，在证明它们之前，我们所发现的“规律”只能称之为猜想）：
&猜想Ⅰ& 若 n 为费马指数，则 n 的任何倍数都是费马指数。
&猜想Ⅱ& 所有的费马指数都是某个最小费马指数的倍数。
1. 在上面这两个猜想中，哪一个更容易证明？
2. 试证明上面的猜想Ⅰ。
&&&&&&&&&&&&&&&&&&
提示（Hint）&&&&& &
&&&&联想因式分解公式 x^n - 1 = ( x -1 ) ......
稍加尝试你就会发现，猜想Ⅰ比猜想Ⅱ更容易证明，军事中的原则“避实击虚”、“先歼灭弱敌”也同样适用于数学，所以我们先来证明猜想Ⅰ，证明了之后它就升级为一个“引理”（lemma），因为它可以引导出某个更重要的更有价值的东西（它被称为“定理”）。
&引理1& 若 n 为费马指数，则 n 的任何倍数都是费马指数。换言之，对于给定的质数 p
p 整除，则 amn
（m 为正整数）也能被
→ 另一个证明参见.
如此轻松地证明了我们的第一个猜想（现在已经“升级”为引理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是不够的，我们还需要知道关于费马指数更多一点的信息，准确的说是加法方面的性质，我们可以把它归纳为下面这两个引理（是否和你料想的一样？）：
&引理2& 若 m, n 为费马指数，则
+ n& 也是费马指数。换言之，对于给定的质数 p
p 整除，则 am+n
&&&&&&&&&& 证明提示（Hint）
& 如何用a^m-1和a^n-1的组合表示a^(m+n)-1
&&&&&&&&&&&&
&引理3& 若 m, n 为费马指数且 m & n ，则
也是费马指数。换言之，若 am
p 整除（m & n），则 am - n
&&&& 证明提示（Hint）
& 考虑a^m-1和a^n-1的差
&&&&&&&&&&&&
有了上面这三个引理，我们已经扫清了通向的所有外围障碍，将它左右夹击，前后包抄，团团围住，可以发起最后的总攻了。
试利用-3证明，证明了之后它就同样晋升为引理，它是上面我们得到的所有结果的结晶：
引理4 所有的费马指数都是某个最小费马指数的倍数。
&&&&&&&&&&&&&&&&&&&&&&&
证明提示（Hint）&&&&& &
&&&&用反证法，设最小的费马指数为F, 假设有一个费马指数不是F的倍数，
&&&&则可构造出一个比F更小的费马指数 ......
有了引理4，全部的问题就归结为确定最小费马指数，鉴于其重要性，下面我们再重申一下它的定义，并引入相应的记号：
定义2（最小费马指数） 给定质数 p
a ，称使得 an
p 整除的最小的指数 n 为“最小费马指数”，更具体地说是“以
a 为底、关于
p 的最小费马指数”，用
前面我们已经找到了以 2 为底，
3, 5, 7, 11 时的各个最小费马指数：
☆& p = 3,&&&
22 - 1 = 3 =
最小费马指数 F (2, 3) = 2
☆& p = 5,&&&
24 - 1 = 15 =
最小费马指数 F (2, 5) = 4
☆& p = 7,&&&
7 = 7 × 1,&&
最小费马指数 F (2, 7) = 3
☆& p = 11,&&&
1023 = 11 × 93,&&
最小费马指数 F (2, 11) = 10
接下来让我们看更多的质数，考察其最小费马指数的规律：
☆& p = 13,&&&
4095 = 13 × 315,&&
最小费马指数 F (2, 13) = 12
p = 17,&&&&
255 = 17 × 15,&&
最小费马指数 F (2,17) = 8
☆& p = 19,&&&
262143& = 19 ×
最小费马指数 F (2, 19) = 18
☆& p = 23,&&&
2047 = 23 × 89,&&
最小费马指数 F (2, 23) = 11
☆& p = 29,&&&
29 × 9256395,&&
最小费马指数 F (2, 29) = 28
☆& p = 31,&&&
25 - 1 = 31 =
31 × 1,&&
最小费马指数 F (2, 31) = 5
☆& p = 37,&&&
最小费马指数 F (2, 37) = 36
☆& p = 41,&&&
1048575& =
41 × 25575,&&
最小费马指数 F (2, 41) = 20
☆& p = 43,&&&
43 × 381,&&
最小费马指数 F (2, 43) = 14
☆& p = 47,&&&
8388607& =
47 × 178481,&&
最小费马指数 F (2, 47) = 23
观察上面的各个最小费马指数，你发现了什么规律？
&&&&&&&&&&&&&&
提示（Hint）&&&&& &
&&&&观察最小费马指数和 p -1 之间的关系
相信目光锐利的读者一定发现了这个规律：有时候最小费马指数&
p - 1 ，而当它不等于
p - 1 的时候，它的某个倍数一定等于
p - 1 ，用更精炼的语言，我们可以把它概括为：
&猜想Ⅲ& 最小费马指数 F (2,
p - 1 的因子。
紧接着我们自然想到，这可以推广到以其他整数为底的最小费马指数，即我们马上又有下面的猜想：
&猜想Ⅳ& 任何最小费马指数 F (a,
p - 1 的因子。
请思考如何证明猜想Ⅲ和它的推广——猜想Ⅳ。
“普通版费马小定理”和“加强版费马小定理”
要直接证明（甚至它的特殊情形）是相当困难的，在正面进攻无从下手，或者找不到“突破口”的时候，希望你能想起下面这个解决数学问题的基本策略（在一文中，我们讲过同样的策略）：
倘若你对原问题无计可施，尝试改变问题的形式，将它转化成等价的新问题，直到能找到“突破口”或“切入点”为止。
请思考怎么样改变的形式，将它转化成一个等价的新命题。
&&&&&&&&&&&&&&
提示（Hint）&&&&& &
&&&&利用我们前面建立的几个引理
如果成立，根据，我们马上有下面的推论，它就是大家通常所说的、可以在教科书和网上查到的费马小定理，我们称之为“普通版的费马小定理”：
命题Ⅰ（普通版的费马小定理）
对于任意质数
p 的倍数的整数
反过来，如果我们证明了命题1，也就等于证明了。
因为命题Ⅰ意味着
是，根据，任何费马指数都是最小费马指数的倍数，所以
是最小费马指数的倍数，即最小费马指数是
基于我们前面的劳动，我们看出和命题Ⅰ即“普通版的费马小定理”是等价的，在下一节我们将讲述后者的证明（希望你能先独立自主地尝试证明它，当然这有相当的难度，毕竟连费马本人也没有能够给出一个证明）。
在此我们先总结一下迄今为止我们的探索和发现的成果，我们可以把它归纳为下面的命题：
命题Ⅱ（加强版的费马小定理）
p 的倍数的整数
a ，an&-1&能被p&整除的最小的指数为“最小费马指数”，用 F (a,
p) 记之，则
(1) 最小费马指数 F (a,
p - 1 的因子。
-1&能被p&整除 &=&
n 是最小费马指数 F (a,
p)的倍数。
显然，从命题Ⅱ——“加强版的费马小定理”很容易推导出，但反过来，要想从后者推导前者，却必须依靠我们前面建立的引理，所以前者是更强的命题，这就是为什么我们称它为“加强版”。在后面我们讲到费马小定理的应用时，我们更能从很多实际例子体会到它的威力。
2.3& 对最小费马指数更深入的探究
是我们目前得到的最好的结果，但它并不是我们探索之旅的终点，还有一个很大的未解之谜留待我们进一步的探索（不知道你想到了没有）：
那就是我们只知道最小费马指数 F (a,
p - 1 的因子，但对它究竟怎样依赖于
却一无所知……
这里隐藏着比费马发现的更深邃更难以窥测的秘密！
再次仔细观察前面，除了发现 F (2,
p - 1 的因子之外，你能发现更进一步的规律吗？
请试着给出你对下面这两个问题的猜想：
什么时候最小费马指数 F (2,
2. 什么时候最小费马指数 F (2,
p - 1 ，而等于它的一个真因子（即不等于1和它本身的因子）？
To be continued（à suivre）
p 的倍数除外，这是费马的疏漏（因为若 a 是
p 的倍数， an
- 1 除以 p 的余数恒等于 -1，故永远不可能被 p 整除）。
这是使费马的断言有意义的正整数 a 的最小取值（当 a = 1 时， an
- 1 恒等于 0，显然能被所有质数整除）。
注意从费马的断言可以推知：如果我们对数列 2n - 1（ n = 1,
2, 3, 4, ...）中的每项进行质因子分解，将得到所有的质数（除 2 外）! 这本身就是一个非凡的论断。
特别地，如果
- 1 本身是质数，那么它就是梅森质数或者说梅森素数（Mersenne prime）！
作为练习试证明：若 2n
- 1 是质数，那么 n 一定是质数。
&&&&&&&&& 提示（Hint）
&&& 1. 用反证法
&&& 2. 类同上面我们对引理1的证明
注意当 a = 2 时，质数 p 不能取 2。 参见上面的。
该恒等式是大家熟悉的平方差公式 x2 -1 = (x-1)(x+1)
的推广，要证明它是很容易的，只要把左边乘出来就行了：
只确立了费马指数的乘法性质——整数的乘法归根结底只是同一个元素的累加，而、是关于两个不同（当然也可以相同）元素的加法和减法的，所以更基本。
实际上从很容易推导出（只要将同一个费马指数相加 N 次就行了）。
用群论的术语讲，最小费马指数 F(a, p)等于
a 在 Zp 的乘法群中的阶（order）。