王朝百科
分享
 
 
 

费马小定理

王朝百科·作者佚名  2009-10-24  
宽屏版  字体: |||超大  

费马小定理

费马小定理费马小定理是数论中的一个重要定理,其内容为:

假如p是质数,且(a,p)=1,那么 a^(p-1) ≡1(mod p)

费马小定理的历史皮埃尔•德•费马于1636年发现了这个定理,在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求,但是这个要求实际上是不存在的。与费马小定理相关的有一个中国猜想,这个猜想是中国数学家提出来的,其内容为:当且仅当2^(p-1)≡1(mod p),p是一个质数。

假如p是一个质数的话,则2^(p-1)≡1(mod p)成立(这是费马小定理的一个特殊情况)是对的。但反过来,假如2^(p-1)≡1(mod p)成立那么p是一个质数是不成立的(比如341符合上述条件但不是一个质数)。因此整个来说这个猜想是错误的。一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了,但也有人认为实际上中国猜测是1872年提出的,认为它早就为人所知是出于一个误解。

费马小定理的证明一、准备知识:

引理1.剩余系定理2

若a,b,c为任意3个整数,m为正整数,且(m,c)=1,则当ac≡bc(modm)时,有a≡b(modm)

证明:ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)因为(m,c)=1即m,c互质,c可以约去,a–b≡0(mod m)可得a≡b(mod m)

引理2.剩余系定理5

若m为整数且m>1,a[1],a[2],a[3],a[4],…a[m]为m个整数,若在这m个数中任取2个整数对m不同余,则这m个整数对m构成完全剩余系。

证明:构造m的完全剩余系(0,1,2,…m-1),所有的整数必然这些整数中的1个对模m同余。取r[1]=0,r[2]=1,r[3]=2,r[4]=3,…r=i-1,1<i<=m。令(1):a[1]≡r[1](mod m),a[2]≡r[2](mod m),a≡r(mod m)(顺序可以不同),因为只有在这种情况下才能保证集合{a1,a2,a3,a4,…am}中的任意2个数不同余,否则必然有2个数同余。由式(1)自然得到集合{a1,a2,a3,a4,…am}对m构成完全剩余系。

引理3.剩余系定理7

设m是一个整数,且m>1,b是一个整数且(m,b)=1。如果a1,a2,a3,a4,…am是模m的一个完全剩余系,则ba[1],ba[2],ba[3],ba[4],…ba[m]也构成模m的一个完全剩余系。

证明:若存在2个整数ba和ba[j]同余即ba≡ba[j](mod m),根据引理2则有a≡a[j](mod m)。根据完全剩余系的定义和引理4(完全剩余系中任意2个数之间不同余,易证明)可知这是不可能的,因此不存在2个整数ba和ba[j]同余。由引理5可知ba[1],ba[2],ba[3],ba[4],…ba[m]构成模m的一个完全剩余系。

引理4.同余定理6

如果a,b,c,d是四个整数,且a≡b(mod m),c≡d(mod m),则有ac≡bd(mod m)

证明:由题设得ac≡bc(mod m),bc≡bd(mod m),由模运算的传递性可得ac≡bc(mod m)

二、证明过程:

构造素数p的完全剩余系P={1,2,3,4…(p-1)},因为(a,p)=1,由引理3可得A={a,2a,3a,4a,…(p-1)a}也是p的一个完全剩余系。令W=1*2*3*4…*(p-1),显然W≡W(mod p)。令Y=a*2a*3a*4a*…(p-1)a,因为{a,2a,3a,4a,…(p-1)a}是p的完全剩余系,由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即W*a^(p-1)≡W(modp)。易知(W,p)=1,由引理1可知a^(p-1)≡1(modp)

费马小定理在数论中的地位费马小定理是数论四大定理(威尔逊定理,欧拉定理(数论中的欧拉定理,即欧拉函数),中国剩余定理和费马小定理)之一,在初等数论中有着非常广泛和重要的应用。实际上,它是欧拉定理的一个特殊情况(见于词条“欧拉函数”)。

费马小定理的实际应用如上所述,中国猜测只有一半是正确的,符合中国猜测但不是质数的数被称为“伪质数”。

对于中国猜测稍作改动,即得到判断一个数是否为质数的一个方法:

如果对于任意满足1 < b < p的b下式都成立:

b^(p-1)≡1(mod p)

则p必定是一个质数。

这个定理告诉我们,判定一个数是否为质数,没有必要测试所有的小于p的自然数,只要测试所有的小于p的质数就可以了。 事实上,测试小于p的平方根的所有质数就可以了。

这个算法的缺点是它非常慢,但是实现简单;很适合在计算机上面运行程序进行验算一个数是否是质数,不过这种方法并不是实际工程中采用的判定方法。

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
如何用java替换看不见的字符比如零宽空格&#8203;十六进制U+200B
 干货   2023-09-10
网页字号不能单数吗,网页字体大小为什么一般都是偶数
 干货   2023-09-06
java.lang.ArrayIndexOutOfBoundsException: 4096
 干货   2023-09-06
Noto Sans CJK SC字体下载地址
 干货   2023-08-30
window.navigator和navigator的区别是什么?
 干货   2023-08-23
js获取referer、useragent、浏览器语言
 干货   2023-08-23
oscache遇到404时会不会缓存?
 干货   2023-08-23
linux下用rm -rf *删除大量文件太慢怎么解决?
 干货   2023-08-08
刀郎新歌破世界纪录!
 娱乐   2023-08-01
js实现放大缩小页面
 干货   2023-07-31
生成式人工智能服务管理暂行办法
 百态   2023-07-31
英语学习:过去完成时The Past Perfect Tense举例说明
 干货   2023-07-31
Mysql常用sql命令语句整理
 干货   2023-07-30
科学家复活了46000年前的虫子
 探索   2023-07-29
英语学习:过去进行时The Past Continuous Tense举例说明
 干货   2023-07-28
meta name="applicable-device"告知页面适合哪种终端设备:PC端、移动端还是自适应
 干货   2023-07-28
只用css如何实现打字机特效?
 百态   2023-07-15
css怎么实现上下滚动
 干货   2023-06-28
canvas怎么画一个三角形?
 干货   2023-06-28
canvas怎么画一个椭圆形?
 干货   2023-06-28
canvas怎么画一个圆形?
 干货   2023-06-28
canvas怎么画一个正方形?
 干货   2023-06-28
中国河南省郑州市金水区蜘蛛爬虫ip大全
 干货   2023-06-22
javascript简易动态时间代码
 干货   2023-06-20
感谢员工的付出和激励的话怎么说?
 干货   2023-06-18
 
>>返回首页<<
 
 
静静地坐在废墟上,四周的荒凉一望无际,忽然觉得,凄凉也很美
© 2005- 王朝网络 版权所有