费马小定理(Fermat Theory)是数论中一个重要定理,内容为:假如p是质数,且,那么。即:假如是整数,是质数,且互质(即两者只有一个公约数1),那么的次方除以的余数恒等于1。该定理是1636年皮埃尔·德·费马发现的。
中文名费马小定理
外文名Fermat's little theorem
提出者皮埃尔·德·费马
提出时间适用领域数论
应用学科数学
发展简史皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求,但是这个要求实际上是不必要的。[1]
1736年,欧拉出版了一本名为“一些与素数有关的定理的证明”(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)的论文中第一次提出证明,但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。
有些学家独立制作相关的假说(有时也被错误地称为中国的假说),当成立时,是素数。这是费马小定理的一个特殊情况。然而,这一假说的前设是错的:例如,341,而341=11×31是一个伪素数。所有的伪素数都是此假说的反例。
如上所述,中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。
更极端的反例是卡迈克尔数:假设与561互质,则560被561除都余1。这样的数被称为卡迈克尔数数,561是最小的卡迈克尔数。Korlt在1899年就给出了卡迈克尔数的等价定义,但直到1910年才由卡迈克尔(Robert Daniel Carmichael)发现第一个卡迈克尔数:561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。
定理定义简称费马定理.初等数论的重要定理之一.该定理断言:若为素数,则.该定理是数论中欧拉定理的一个特殊情况,因为在欧拉定理中当是素数时[2],就得到费马定理。
验证推导引理1
若为任意3个整数为正整数,且,则当时,有。
证明:可得可得。因为即互质,可以约去,可得。
引理2
设是一个整数且是一个整数且。如果是模的一个完全剩余系,则也构成模的一个完全剩余系。
证明:若存在2个整数和同余即,根据引理1则有。根据完全剩余系的定义可知这是不可能的,因此不存在2个整数和同余。
所以构成模的一个完全剩余系。
构造素数的完全剩余系
因为,由引理2可得
也是的一个完全剩余系。由完全剩余系的性质,
即
易知,同余式两边可约去,得到
这样就证明了费马小定理。
定理意义费马小定理是初等数论四大定理(威尔逊定理,欧拉定理(数论中的欧拉定理),中国剩余定理(又称孙子定理),费马小定理)之一,在初等数论中有着非常广泛和重要的应用。实际上,它是欧拉定理的一个特殊情况(即
Python程式码>>> n =221
>>>a = 38
>>>pow(a ,n -1,n)
1
"""221 may be a prime number."""
import random
def isprime(n,k=128):
if n<2:
return Fal
for _ in range(k):
a = random.randrange(1,n)
if pow(a,n-1,n)!=1:
return Fal
return True
参考资料本文发布于:2023-06-03 20:10:52,感谢您对本站的认可!
本文链接:https://www.wtabcd.cn/zhishi/a/92/191083.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文word下载地址:费马小定理(数学定理).doc
本文 PDF 下载地址:费马小定理(数学定理).pdf
留言与评论(共有 0 条评论) |