求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。

质数查看源代码讨论查看历史

跳转至: 导航搜索
质数

质数,又称素数,有无限个。 数学家把自然数按照乘法性质划分为: 1,自然数1; 2,素数,大于1只能被1和自身整除的自然数。例如,2,3,5,7,.....。 3,复合数,至少有两个素数因子。例如,4,6,8,9,10,....。


根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积;而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的。最小的质数是2。 按照埃拉特斯尼筛法,可以构造一个公式: 素数的埃拉特斯特尼筛法公式素数普遍公式

(清华大学出版社【品数学】第5页)

西元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法:

(一),“要得到不大于某个自然数N的所有素数,只要在2---N中将不大于√N的素数的倍数全部划去即可”。

(二),“如果自然数N是合数,则它有一个因子d满足1<d≤√N.。

(三),如果自然数N是素数,当且仅当N不能被不大于√N的任何素数整除”。

见(代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页)。

(四),对于(三)这句话的汉字可以等价转换成为用英文字母表达的公式:


公式形式:

N=P₁M₁+A₁=P₂M₂+A₂=.....=Pr Mr +Ar ......(1)。

其中P₁,P₂,....,Pr 表示顺序素数 2,3,5,......。Ai≠0。

这样解得的N,若N<P²r+1,则N是一个素数。

我们可以把(1)式内容等价转换同余式组表示:

N≡A₁(modP₁),N≡A₂(modP₂),.....N≡Ar(modPr)。。。。.(2)

由于(2)的模P₁,P₂,,.,Pr 都是素数,因此两两互素,根据孙子定理(中国剩余定理)知,对于给定的A₁,A₂,,,Ar,(2)式在P₁P₂....Pr范围内有唯一解。

范例

例如,r=1,N=2M₁+1,解得N=3,5,7。7﹤3²=9,求得了(3,3²)区间的全部素数。

r=2,

N=2M₁+1=3M₂+1,解得N=7,13,19;

N=2M₁+1=3M₂+2,解得N=5,11,17,23.

求得了(5,5²)区间的全部素数。

仿此下去,可以一个不漏地求得任意大的全部素数。

人类为了寻找这个公式,花费了2000多年


2016年1月,发现世界上迄今为止最大的质数,长达2233万位,如果用普通字号将它打印出来长度将超过65公里。

质数1.jpg

质数个数

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法:反证法。具体证明如下:假设质数只有有限的n个,从小到大依次排列为p1,p2,……,pn,设N=p1×p2×……×pn,那么,N+1是素数或者不是素数。[1] 如果N+1为素数,则N+1要大于p1,p2,……,pn,所以它不在那些假设的素数集合中。 如果N+1为合数,因为任何一个合数都可以分解为几个素数的积;而N和N+1的最大公约数是1,所以N+1不可能被p1,p2,……,pn整除,所以该合数分解得到的素因数肯定不在假设的素数集合中。 因此无论该数是素数还是合数,都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说,素数有无穷多个。

其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的,恩斯特·库默的证明更为简洁,HillelFurstenberg则用拓扑学加以证明。

对于一定范围内的素数数目的计算

尽管整个素数是无穷的,仍然有人会问“100,000以下有多少个素数?”,“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。

相关定理

在一个大于1的数a和它2倍之间(即区间(a, 2a]中)必存在至少一个素数。

质数2.jpg

著名猜想

哥德巴赫猜想:是否每个大于2的偶数都可写成两个素数之和?https://factpedia.org/wiki/%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3%E7%9C%9F%E7%9B%B8

孪生素数猜想:孪生素数就是差为2的素数对,例如11和13。是否存在无穷多的孪生素数?https://factpedia.org/wiki/%E5%AD%AA%E7%94%9F%E7%B4%A0%E6%95%B0%E7%8C%9C%E6%83%B3%E7%9C%9F%E7%9B%B8

斐波那契数列内是否存在无穷多的素数?是否有无穷多个的梅森素数?在n2与(n+1)2之间是否每隔n就有一个素数?是否存在无穷个形式如X2+1素数?

性质介绍

质数具有许多独特的性质:

(1)质数p的约数只有两个:1和p。

(2)初等数学基本定理:任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,且这种分解是唯一的。

质数3.jpg

(3)质数的个数是无限的。

(4)质数的个数公式π(n)是不减函数。

(5)若n为正整数,在n的2次方到(n+1)的2次方 之间至少有一个质数。

(6)若n为大于或等于2的正整数,在n到n!之间至少有一个质数。

(7)若质数p为不超过n(n大于等于4)的最大质数,则p>n/2 。

素性检测

素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解,素性测试一般不能得到输入数的素数因子,只说明输入数是否是素数。大整数的分解是一个计算难题,而素性测试是相对更为容易(其运行时间是输入数字大小的多项式关系)。有的素性测试证明输入数字是素数,而其他测试,比如米勒 - 拉宾(Miller–Rabin )则是证明一个数字是合数。因此,后者可以称为合性测试。质数是因数只有1和它本身的数。

质数4.jpg

素性测试通常是概率测试(不能给出100%正确结果)。这些测试使用除输入数之外,从一些样本空间随机出去的数;通常,随机素性测试绝不会把素数误判为合数,但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小;对于两种常用的测试中,对任何合数n,至少一半的a检测n的合性,所以k的重复可以减小误差概率最多到2^{-k},可以通过增加k来使得误差尽量小。

随机素性测试的基本结构:

1.随机选取一个数字a。

2.检测某个包含a和输入n的等式(与所使用的测试方法有关)。如果等式不成立,则n是合数,a作为n是合数的证据,测试完成。

3.从1步骤重复整个过程直到达到所设定的精确程度。

在几次或多次测试之后,如果n没有被判断为合数,那么我们可以说n可能是素数。

质数5.png

常见的检测算法:费马素性检验(Fermat primality test),米勒拉宾测试(Miller–Rabin primality test) ,Solovay–Strassen测试(Solovay–Strassen primality test),卢卡斯-莱默检验法(英语:Lucas–Lehmer primality test)。

著名难题

歌德巴赫猜想


梅森质数

17世纪还有位法国数学家叫梅森,他曾经做过一个猜想:当2p-1 中的p是质数时,2p-1是质数。他验算出:当p=2、3、5、7、17、19时,所得代数式的值都是质数,后来,欧拉证明p=31时,2p-1是质数。 p=2,3,5,7时,2p-1都是素数,但p=11时,所得2,047=23×89却不是素数。

梅森去世250年后,美国数学家科勒证明,267-1=193,707,721×761,838,257,287,是一个合数。这是第九个梅森数。20世纪,人们先后证明:第10个梅森数是质数,第11个梅森数是合数。质数排列得杂乱无章,也给人们寻找质数规律造成了困难。

质数8.jpg

迄今为止,人类仅发现48个梅森质数。中央密苏里大学在2013年1月25日协调世界时间23:30:26发现的质数,为迄今发现的最大质数,同时是一个梅森质数。由于这种质数珍奇而迷人,它被人们称为“数学珍宝”。值得一提的是,中国数学家和语言学家周海中根据已知的梅森质数及其排列,巧妙地运用联系观察法和不完全归纳法,于1992年正式提出了梅森素质分布的猜想,这一重要猜想被国际上称为“周氏猜测”。[1]

2016年1月7日,美国密苏里中央大学数学家柯蒂斯·库珀(Curtis Cooper)找到了目前人类一直的最大素数——“2的74,207,281次方减1”(2^74207281-1),数值高达22,338,618位数。

柯蒂斯·库珀是通过 Great Internet Mersenne Prime Search(GIMPS,互联网梅森素数大搜索)找到该素数,这是第49个梅森素数,这一重大发现无疑为互联网梅森素数大搜索诞生20周年献了厚礼。

这也是柯蒂斯·库珀第四次通过互联网梅森素数大搜索发现新的梅森素数,刷新了他自己的记录。[2]

质数9.jpg

应用领域

质数被利用在密码学上,所谓的公钥就是将想要传递的信息在编码时加入质数,编码之后传送给收信人,任何人收到此信息后,若没有此收信人所拥有的密钥,则解密的过程中(实为寻找素数的过程),将会因为找质数的过程(分解质因数)过久,使即使取得信息也会无意义。

在汽车的设计上,相邻的两个大小齿轮齿数最好设计成质数,以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数,可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上,杀虫剂的质数次数的使用也得到了证明。实验表明,质数次数地使用杀虫剂是最合理的:都是使用在害虫繁殖的高潮期,而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数(单位为年),这样可以最大程度地减少碰见天敌的机会。

參考來源