费马小定理

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

费马小定律(Fermat's Little Theorem)

目录

什么是费马小定律

  费马小定理是数论中的一个定理。其内容为假如a是一个整数,p是一个质数的话,那么:

  ap = a(mod p)

  假如a不是p的倍数的话,那么这个定理也可以写成:

  ap − 1 = 1(mod p)

  这个书写方式更加常用些。

费马小定律的广义

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

  a^{\varphi (n)} = 1 \pmod{n}

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

  在费马小定理的基础上费马提出了一种测试质数的算法。

费马小定律的历史

  皮埃尔·德·费马于1636年发现了这个定理,在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个质数的要求。这个要求实际上不存在。

  与费马无关的有一个中国猜想。这个猜想是中国数学家提出来的。其内容为如果,而且只有当2p = 2(modp)成立时p才是一个质数。

  假如p是一个质数的话,则2p = 2(modp)成立(这是费马小定理的一个特殊情况)是对的。但反过来,假如2p = 2(modp)成立那么p是一个质数是不成立的(比如341符合上述条件但不是一个质数)。因此整个来说这个猜想是错误的。

  一般认为中国数学家在费马前2000年的时候就已经认识中国猜测了。但也有人认为实际上中国猜测是1872年提出的,认为它早就为人所知是出于一个误解。

费马小定律的证明

  若n不整除a-b,x>0,(x,n)=1,則n也不整除x(a-b)。取整數A为所有小於p的集(p不整除A),B为A中所有元素乘以a的集合。因任何两个A中的元素差都不能被p整除,所以任何两个B中的元素差也无法被p整除。因此:

  1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) = (1 \cdot a)\cdot(2 \cdot a)\cdot\dots\cdot ((p-1) \cdot a) \pmod{ p},

  即:

  W = W\cdot a^{p-1} \pmod{p},

  在这里W=1·2·3·...·(p-1)。将整个公式除以W即得到:

  ap − 1 = 1(mod p)

费马小定律的的实际应用

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

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

  b^{p} = b \mod p

  则p必定是一个质数。

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

  这个算法的缺点是它非常慢,运算率高。

相关条目

本条目对我有帮助28
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

Fghj372,Cabbage,Vulture,Mis铭.

评论(共3条)

提示:评论内容为网友针对条目"费马小定理"展开的讨论,与本站观点立场无关。
121.28.12.* 在 2014年4月3日 11:48 发表

回复评论
111.81.97.* 在 2016年8月6日 17:56 发表

回复评论
111.197.116.* 在 2017年11月27日 21:57 发表

回复评论

发表评论请文明上网,理性发言并遵守有关规定。

MBA智库
打开APP

以上内容根据网友推荐自动排序生成