费马小定理 费马小定理的证明

(选自《数论妙趣——数学女王的盛情款待》第六章 开门咒)

数论中充斥着许多易于观察到的事实,诱使人们用普通归纳推理的办法去进行推广。对此,必须慎之又慎,以免误入陷阱。

设想你偶而把2自乘7次,再减去2,得27-2=126,随后发现,126恰好能被2的幂指数7整除。接着又发现,25-2=30,30也能被2的幂指数5整除;211-2=2048,2048也能被2的幂指数11整除。从7,5,11都是奇数产生一个想法,把2的幂指数换成偶数会怎么样?于是,又去试验24-2=14,发现14不能被2的幂指数4整除;26-2=62,62也不能被2的幂指数6整除;28-2=254,254也不能被2的幂指数8整除。

这时,你或许会产生一个感觉:2的幂指数p为奇数时,2p-2似乎能被p整除;2的幂指数p为偶数时,2p-2似乎不能被p整除。为了慎重起见,你可能会测试一下29-2=510,并惊讶地发现,9虽然是奇数,510却不能被2的幂指数9整除;还有,215-2=32766,15虽然是奇数,32766也不能被2的幂指数15整除。于是感到,不能总在奇数和偶数上兜圈子,索性扩大试验范围,并对数据进行系统整理。于是得到:

  P     2p-2        (2p-2)÷p

 2(质数)  22-2=4-2=2    2÷2=1

 3(质数)  23-2=8-2=6    6÷3=2

 4(合数)  24-2=16-2=14   14不能被4整除

 5(质数)  25-2=32-2=30   30÷5=6

 6(合数)  26-2=64-2=62   62不能被6整除

 7(质数)  27-2=128-2=126  126÷7=18。

8(合数)  28-2=256-2=254  254不能被8整除

 9(合数)  29-2=512-2=510  510不能被9整除

10(合数)210-2=1024-2=10221022不能被10整除

11(质数)211-2=2048-2=20462046÷11=186。

12(合数)212-2=4096-2=40944094不能被12整除

13(质数)213-2=8192-2=81908190÷13=630

14(合数)214-2=16384-2=1638216382不能被14整除

15(合数)215-2=32768-2=3276632766不能被15整除

 16(合数)216-2=65536-2=6553465534不能被16整除

 17(质数)217-2=131072-2=131070131070不能被17整除

 18(合数)217-2=262144-2=262142262142不能被18整除

 19(质数)217-2=524288-2=524286524286÷19=27594

 20(合数)217-2=1048576-2=10485741048574不能被20整除

 21(合数)217-2=2097152-2=20971502097150不能被21整除

 22(合数)217-2=4194304-2=41943024194302不能被22整除

 23(质数)217-2=8388608-2=83886068388606÷23=364722

 24(合数)217-2=16777216-2=1677721416777214不能被24整除

 25(合数)217-2=33554432-2=3355443033554430不能被25整除

至此,事情已经非常清楚,你很可能会按耐不住兴奋的心情,作出自以为绝对正确无误的结论:

当p为质数时,2p-2能被p整除。当p为合数时,2p-2不能被p整除。

其实,这个结果,我国的古代先哲,早在公元前500年就已经知道了。只是到了1819年,有人发现,当p=341时,2341-2也能被341整除,而341=31×11,却是个合数,才使上面的“结论”产生动摇。

费马小定理 费马小定理的证明

那么,真实情况又是怎样的呢?真实情况是:

p为质数时,2p-2恒能被p整除;p为合数时,2p-2有时也能被p整除。

通过这个事例,也使我们再一次认识到,仅仅靠归纳得出来的结论,往往是不可靠的。

后来,就是那位提出“xn+yn=zn,当n≥3时不成立”,而使无数数学大师为之绞尽脑汁苦思冥想了200多年,大名鼎鼎号称“业余数学王子”的费马,重新发现并证明了“p为质数时,2p-2恒能被p整除”,并且将其推广到:如果p为质数,xp-x(x是任意正整数)必能被p整除。

在提出公因子x后,xp-x=x(xp-1-1),并且设x不是p的倍数,这样,就得到著名的“费马小定理”:

若x是一个不能被质数p整除的整数,则xp-1-1必能被p整除。如果用同余式写法,就是xp-1≡1modp。

这种朴实无华的代数关系,似乎不会给人们留下什么深刻印象。然而它导致了众多的思维与奥妙的数学逻辑通道,因而被看成是数论大厦的一块基石。

费马小定理有着非常独特的作用,从下面这个例子,就可见一斑。

2134217826-1是一个非常非常大的数,有四千万位数字,需要40卷500页的大书,每页2000字,才能容纳得下。然而根据费马小定理,立即可以肯定它能被134217827整除。当然,先决条件是:134217827是质数。

费马小定理有多种证法,以同余证法最为简短而精致。

任意取一个质数,比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12,给这些数都乘上一个与13互质的数,比如3,得到3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说,这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12,只是顺序不同而已。

把1,2,3,…,12统统乘起来,乘积就是12的阶乘12!。把3,6,9,…,36也统统乘起来,并且提出公因子3,乘积就是312×12!。对于模13来说,这两个乘积都同余于1,2,3,…,12系列,尽管顺序不是一一对应,即312×12!≡12!mod13。两边同时除以12!得312≡1mod13。如果用p代替13,用x代替3,就得到费马小定理xp-1≡1modp。

需要提醒的是,不能把费马小定理理解为只是对质数成立。如果那样的话,就会得到一个判定质数的简单而实用准则:某数p能整除xp-1-1,则p必为质数。寻找简便易行的判定质数的方法,一直是人们梦寐以求的愿望。不幸的是,费马小定理对质数永远成立,对合数有时也成立,使得这一美好愿望落了空。不过,尽管如此,费马小定理仍然不失为数论大厦的一块基石。

  

爱华网本文地址 » http://www.aihuau.com/a/25101018/367944.html

更多阅读

win7激活方法全记录,小马无法激活的进来。 小马哥win7激活

win7激活方法全记录,小马无法激活的进来。——简介正对部分常规工具无法激活的电脑,请使用Oem7最新版KMS8V2.2进行激活,在改装台式机上测试过可用(2013年12月16日更新),如果有人还是无法激活请搜索最新版KMS8。请选择OEM/EFI模式激活,KMS

老妻少夫:李玉成和马玉琴的幸福生活之二辽视访谈

辽宁电视台对李玉成和马玉琴的访谈,录制地点就在他们家的小屋里...3日中午,李玉成打来电话,说辽宁电视台某专栏摄制组记者来采访他和他的妻子马玉琴.邀请我过去,顺便看一看他俩的新家.晚上6点后,我处理完私事后,按照李玉成说的那

法式马卡龙的做法 抹茶马卡龙的做法

下面来说说法式马卡龙制作中,打发蛋白的小妙招。不看文字的童鞋,你们失误了O(∩_∩)O哈哈~开始:对于马卡龙的历史众说纷纭,有的资料说源自法国,有的资料说源自意大利,不过到法国后发扬光大。无论那种说法,最后我看到最多的是,用意式马卡龙配

正弦定理的教学反思 垂径定理教学反思

在备课中有两个问题需要精心设计.一个是问题的引入,一个是定理的证明.课本通过一个实际问题引入,但没有深入展开下去;对正弦定理的证明是利用三角形的面积公式导出的,但不够自然.为了处理好这两个问题,我首先确定了一个基本原则,就是充分

激荡人心的《小马王》的背景音乐 激荡人心的纯音乐

《小马王》的背景音乐部分,动用了金牌音乐制作人汉斯·基墨()和著名歌手布莱恩·亚当斯(BryanAdams),使得这部影片的音乐充满了惊喜。前者七度获得奥斯卡最佳音乐提名,94年的《狮子王》获得奥斯卡及金球奖的两项最佳配乐大奖,还包括《角斗士

声明:《费马小定理 费马小定理的证明》为网友姐拽的有气质分享!如侵犯到您的合法权益请联系我们删除