注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

周靖国的博客

春蚕到死丝方尽 愿将余生蚕化春蚕

 
 
 

日志

 
 

费马小定理  

2013-06-29 06:01:59|  分类: 趣味数学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

设想你偶而把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=1022          1022不能被10整除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 25(合数)   217-2=33554432-2=33554430  33554430不能被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≡1 mod p。

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

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

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!mod 13。两边同时除以12!得312≡1 mod 13。如果用p代替13,用x代替3,就得到费马小定理xp-1≡1 mod p。

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

  评论这张
 
阅读(764)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017