质数查看源代码讨论查看历史
| 质数 | |
|---|---|
质数，又称素数，有无限个。 数学家把自然数按照乘法性质划分为： 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公里。
质数个数
质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的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的偶数都可写成两个素数之和？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）质数的个数是无限的。
（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）。
著名难题
歌德巴赫猜想
梅森质数
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]
应用领域
质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。
在汽车的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。
以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。
多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。