质数查看源代码讨论查看历史
| 质数 | |
|---|---|
质数，又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。
根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积;而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是2。
目前为止，人们未找到一个公式可求出所有质数。[1] 2016年1月，发现世界上迄今为止最大的质数，长达2233万位，如果用普通字号将它打印出来长度将超过65公里。
质数个数
质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，N+1是素数或者不是素数。[2] 如果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]中）必存在至少一个素数。 存在任意长度的素数等差数列。（格林和陶哲轩，2004年） 一个偶数可以写成两个数字之和，其中每一个数字都最多只有9个质因数。（挪威布朗，1920年） 一个偶数必定可以写成一个质数加上一个合成数，其中的因子个数有上界。（瑞尼，1948年） 一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 (1 + 5) (中国，1968年) 一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2) (中国陈景润)
著名猜想
哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？
孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
斐波那契数列内是否存在无穷多的素数？是否有无穷多个的梅森素数？在n2与（n+1）2之间是否每隔n就有一个素数？是否存在无穷个形式如X2+1素数？
性质介绍
质数具有许多独特的性质：
（1）质数p的约数只有两个：1和p。
（2）初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。
（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和它本身的数。
素性测试通常是概率测试（不能给出100%正确结果）。这些测试使用除输入数之外，从一些样本空间随机出去的数；通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小；对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到2^{-k}，可以通过增加k来使得误差尽量小。
随机素性测试的基本结构：
1.随机选取一个数字a。
2.检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。
3.从1步骤重复整个过程直到达到所设定的精确程度。
在几次或多次测试之后，如果n没有被判断为合数，那么我们可以说n可能是素数。
常见的检测算法：费马素性检验（Fermat primality test），米勒拉宾测试（Miller–Rabin primality test） ，Solovay–Strassen测试（Solovay–Strassen primality test），卢卡斯-莱默检验法（英语：Lucas–Lehmer primality test）。
著名难题
歌德巴赫猜想
在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成三个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"。 今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。
从关于偶数的哥德巴赫猜想，可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。
若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”。
黎曼猜想
黎曼猜想是关于黎曼ζ函数ζ(s)的零点分布的猜想，由数学家波恩哈德·黎曼（1826～1866）于1859年提出。德国数学家希尔伯特列出23个数学问题。其中第8问题中便有黎曼假设。素数在自然数中的分布并没有简单的规律。黎曼发现素数出现的频率与黎曼ζ函数紧密相关。黎曼猜想提出：黎曼ζ函数ζ(s)非平凡零点（在此情况下是指s不为-2、-4、-6等点的值）的实数部份是1/2。即所有非平凡零点都应该位于直线1/2 + ti（“临界线”（critical line））上。t为一实数，而i为虚数的基本单位。至今尚无人给出一个令人信服的关于黎曼猜想的合理证明。
在黎曼猜想的研究中，数学家们把复平面上 Re(s)=1/2 的直线称为 critical line。 运用这一术语，黎曼猜想也可以表述为：黎曼ζ 函数的所有非平凡零点都位于 critical line 上。
黎曼猜想是黎曼在 1859 年提出的。在证明素数定理的过程中，黎曼提出了一个论断：Zeta函数的零点都在直线Res(s) = 1/2上。他在作了一番努力而未能证明后便放弃了，因为这对他证明素数定理影响不大。但这一问题至今仍然未能解决，甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设，则可带动许多问题的解决。
孪生质数
1849年，波林那克提出孪生质数猜想（the conjecture of twin primes），即猜测存在无穷多对孪生质数。猜想中的“孪生”是指一对质数，它们之间相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孪生质数。
例如3和5 ，5和7，11和13，…，10016957和10016959等等都是孪生质数。孪生质数有一个十分精确的普遍公式，是根据一个定理：“若自然数Q与Q+2都不能被不大于根号Q+2的任何质数整除，则Q与Q+2是一对质数，称为相差2的孪生质数。这一句话可以用公式表达：Q=p1m1+a1=p2m2+a2=....=pkmk+ak其中p1，p2，...，pk表示顺序质数2，3，5，....。an≠0，an≠pn-2。若Q<P(k+1)的平方减2，则Q与Q+2是一对孪生质数。 所以，只要按着公式计算，理论上有无数个孪生质数。
英国数学家戈弗雷·哈代和约翰·李特尔伍德曾提出一个“强孪生素数猜想”。这一猜想不仅提出孪生素数有无穷多对，而且还给出其渐近分布形式。2013年5月，华人数学家张益唐在孪生素数研究方面所取得的突破性进展，他证明了孪生素数猜想的一个弱化形式。在最新研究中，张益唐在不依赖未经证明推论的前提下，发现存在无穷多个之差小于7000万的素数对，从而在孪生素数猜想这个重要问题的道路上前进了一大步。
梅森质数
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个梅森数是合数。质数排列得杂乱无章，也给人们寻找质数规律造成了困难。
迄今为止，人类仅发现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]
应用领域
质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。
在汽车的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。
以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。
多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。