字典大全

首页 汉语字典 词语字典 成语字典 诗词 中草药 中药名方 民间偏方 民间验方 酒方 粥谱 歇后语 汽车时刻表 五笔编码
旅游 动物 植物 微生物 自然天文 金融 数理化 电脑网络 健康 饮食 交通 体育 公交线路 火车时刻表 汉字转拼音
费马小定理
目录 ·费马小定理
·关于费马定理的历史
·关于费马定理证明
·费马定理的推广
·费马定理的实际应用


费马小定理
费马小定理是数论中的一个定理,其内容为:假如a是一个整数,p是一个质数的话,那么               <math>a^p \equiv a \p mod</math>

假如a不是p的倍数的话,那么这个定理也可以写成                <math>a^ \equiv 1 \p mod</math> 。(符号的应用请参见模运算)


关于费马定理的历史

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

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


关于费马定理证明
   假如a 差不能被p整除的话 , 那么假如x>0和x和p的最 大 公约数为1的话(a,p互素) , 则x•a与x•a 的差也不能被n整除(也就是说x.a,x.a,.....(p-1).a 不是模n同余的)。取a为所有小于p 的整数的集(a中的数都不能被p整除),

b为a中所有元素除以a所获得的数集。任何两个a 的元素的差都不能被p整除而又有相同的余数,由此任何两个b中的元素的差也无法被p整除。由此 可得

            而试图在p-1个元素里取p-1个不同的元素,则必定是相同的
则a集合中元素的乘积,和b集合中元素的乘积一定是模p同余的

即          1.a ×2.a x×3.a......(p-1).a=1×2×3×4......×(p-1)(mod p)
(p-1)!=ap-1(p-1)!(mod p)
在这里w=1•2•3•...•(p-1)。(威尔逊定理)
由于gcd((p-1),p)=1,两边同除以(p-1)!,即可得到费马小定理

                     


费马定理的推广


费马小定理是欧拉定理的一个特殊情况:假如n和a的最大公约数是1的话,那么

                             <math>a^{\varphi (n)} \equiv 1 \pmod</math>

在这里φ(n)是“欧拉商数”。“欧拉商数”的值是所有小于n的自然数中与n没有公约数的数的量。假如n是一个质数,则φ(n) = n-1,即费马小定理。 在费马小定理的基础上费马提出了一

种测试质数的算法。


费马定理的实际应用

如上所述,中国猜测只有一半是正确的,符合中国猜测但不是质数的数被称为“伪质数”。

假如所有符合1 < b < p的b p都满足下列条件的话:

                    <math>b^ \equiv b \mod p</math>

则p必定是一个质数。

实际上没有必要测试所有的小于p的自然数,只要测试所有的小于p的质数就可以了。

这个算法的缺点是它非常慢,运算率高。
费马大定理←←←上一条 下一条→→→哥德尔定理

本站信息均由互联网搜集而来,本站不对信息的正确性负责,仅供大家参考研讨,有不妥之处还请来信指出,谢谢!
Copyright©2006-2017 网上字典大全  All Rights Reserved mail: