|
|
 素数定理
（如图所示）
素数定理可以给出第n个素数p(n)的渐近估计： :p(n)sim nln,n. 它也给出从整数中抽到素数的概率。从不大于n的自然数随机选一个，它是素数的概率大约是1/ln n。 这定理的式子於1798年法国数学家勒让德提出。1896年法国数学家哈达玛(jacques hadamard)和比利时数学家普森(charles jean de la vallée-poussin)先後独立给出证明。证明用到了复分析，尤其是黎曼ζ函数。 因为黎曼ζ函数与π(x)关系密切，关於黎曼ζ函数的黎曼猜想对数论很重要。一旦猜想获证，便能大大改进素数定理误差的估计。1901年瑞典数学家helge von koch证明出，假设黎曼猜想成立，以上关系式误差项的估计可改进为 : pi(x) = (x) + oleft(sqrt x ln,x
ight) 至於大o项的常数则还未知道。 |
|
| 素数定理有些初等证明只需用数论的方法。第一个初等证明於1949年由匈牙利数学家保罗·艾狄胥（“爱尔多斯”，或“爱尔多希”）和挪威数学家阿特利·西尔伯格合作得出。 在此之前一些数学家不相信能找出不需借助艰深数学的初等证明。像英国数学家哈代便说过素数定理必须以复分析证明，显出定理结果的「深度」。他认为只用到实数不足以解决某些间题，必须引进复数来解决。这是凭感觉说出来的，觉得一些方法比别的更高等也更厉害，而素数定理的初等证明动摇了这论调。selberg－艾狄胥的证明正好表示，看似初等的组合数学，威力也可以很大。 category:数论 ja:素数定理 |
|
素数，又称质数，是只有两个正因数（1和自己）的自然数。 比1大但不是素数的数称之为合数，而1和0既非素数也非合数。素数的属性称为素性，素数在数论中有着非常重要的地位。
关於素数
最小的素数是2，而最大的素数并不存在，这一点欧几里德已在其《几何原本》中证明。 围绕素数存在很多的数学问题、数学猜想、数学定理，较为著名的有孪生素数猜想、哥德巴赫猜想等等。 素数序列的开头是这样： :2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，101，103，107，109，113 (oeis:a000040) 素数集合有时也被表示成粗体 mathbb。 在抽象代数的一个分支－环论中，素元素有特殊的含义，在这个含义下，任何素数的加法的逆转也是素数。换句话说，将整数z的集合看成是一个环，-7是一个素元素。不管怎样，数学领域内，提到素数通常是指正素数。 算术基本定理说明每个正整数都可以写成素数的乘积，因此素数也被称为自然数的“建筑的基石”例如： :23244 = 2^2 imes 3 imes 13 imes 149 关於分解的详细方法，可见於整数分解这条目。 这个定理的重要一点是，将1排斥在素数集合以外。如果1被认为是素数，那么这些严格的阐述就不得不加上一些限制条件了。 |
|
| 素数是无穷多的，对这个论断，现在所已知的最古老的检验方法是欧几里德在他的几何原本中提出来的。他的检验方法可以简单地总结如下： : 取有限个数的素数，因为要做自变量我们假设全部的素数都存在，将这些素数相乘然后加1，得到的数是不会被这些素数中的任何一个整除的，因为无论除哪个总会余1。因此这个数要么本身就是个素数，要么存在不在这个有限集合内的约数。因此我们开始用的集合不包含所有的素数。 别的数学家也给出了他们自己的证明。欧拉证明了全部素数的倒数和发散到无穷的。恩斯特·库默的证明尤其简洁，furstenberg用一般拓扑证明。 尽管整个素数是无穷的，仍然有人会问“100000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以此问题。 |
|
寻找在给定限度内的素数排列，埃拉托斯特尼筛法法是个很好的方法。然而在实际中，我们往往是想知道一个给定数是否是素数，而不是生成一个素数排列。进而，知道答案是很高的概率就是已经很满意的了，用素性测试迅速地检查一个给定数（例如，有几千位数的长度）是否是素数是可能的。典型的方法是随机选取一个数，然后围绕着这个数和可能的素数n检查一些方程式。几个整数后，它宣布这个数是明显的和数或者可能是素数。这种方法是不完美的，一些测试，不论是否选取一个随机数都有可能将一些合数判断成可能的素数，这就引出了另一种数伪素数。 目前最大的已知素数是2^-1（此数字位长度是7,816,230），它是在2005年2月18日由gimps计划发现。这计划也在2004年5月15日发现了第二大的已知素数2^-1（此数字位长度是7,235,733）。 数学家一直努力找寻产生素数的公式，但截至目前为止，并没有一个函数或是多项式可以正确产生所有的素数。历史上有许多试验的例子：17世纪初法国数学家梅森(mersenne)在他的一个著作当中讨论了这样一种我们现在称之为梅森素数的素数，mp=2^p-1，本来以为只要p是一个素数，n=2^-1就会是一个素数，这在p=3，p=5，p=7都是正确的，但是p=11时 2^-1=2047=23 imes 89就不是素数了。
检验素数
检查一个正整数n是否为素数，最简单的方法就是试除法，将该数n用小于等于sqrt的所有素数去试除，若均无法整除，则n为素数。 |
|
- 哥德巴赫猜想：是否每个大於2的双数均可写成两个质数之和？
- 孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
- 斐波那契数列是否存在无穷多的素数？
- 是否存在无穷多梅森素数？
- 在n^2与(n+1)^2之间每隔n就有一个素数？
- 是否存在无穷个形式如n^2+1的素数？
- 黎曼猜想
- 是否存在不定长的素数算术级数？
素数的应用
素数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入素数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找素数的过程（分解质因数）过久而无法解读信息。 |
|
互素，又称互质，最早是初等数论中的概念：
若n个整数a1,a2,…,an的最大公因数为1，就称这n个整数互素．
需要注意n个整数素数和n个整数两两互素是不同的概念．
两互素整数之商必为有理数，同时，任意有理数都可以表示为两互素整数之商。
其实在互素的概念不限于初等数论，与它有密切关系的也绝不仅有有理数的表示有关。 可以这样来看互素与有理数之间的关系：任意有理数都可以表示为两整数之商a / b（其中b为不0）。这种表示方法并不唯一。如果a1 / b1和a2 / b2是两个有理数的表示法，当且仅当a1 * b2 = a2 * b1时，说这两种表示方法表示的是同一个有理数（等价）。事实上，这是有理数的形式化定义（的一种通俗说法）。在同一有理数的不同等价表示法中，若取定a为任意整数（包括0），b为正整数，且a与b互素，则可以证明，当a不为0时，这种表示法唯一。我们可以用这种表示法做为有理数不同表示法的一个代表，即约化的表示（对于0，不妨约定约化表示为0 / 1）。
质数的概念
所谓质数或称素数，就是一个正整数，除了本身和 1 以外并没有任何其他因子。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数或合数。从这个观点可将整数分为两种，一种叫质数，一种叫合成数。（有人认为数目字 1 不该称为质数）著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。
寻找在给定限度内的素数排列，埃拉托斯特尼筛法法是个很好的方法。然而在实际中，我们往往是想知道一个给定数是否是素数，而不是生成一个素数排列。进而，知道答案是很高的概率就是已经很满意的了，用素性测试迅速地检查一个给定数（例如，有几千位数的长度）是否是素数是可能的。典型的方法是随机选取一个数，然后围绕着这个数和可能的素数N检查一些方程式。几个整数后，它宣布这个数是明显的和数或者可能是素数。这种方法是不完美的，一些测试，不论是否选取一个随机数都有可能将一些合数判断成可能的素数，这就引出了另一种数伪素数。 目前最大的已知素数是2^-1（此数字位长度是7,816,230），它是在2005年2月18日由GIMPS计划发现。这计划也在2004年5月15日发现了第二大的已知素数2^-1（此数字位长度是7,235,733）。 数学家一直努力找寻产生素数的公式，(请点击百度网页“素数普遍公式”和“孪生素数普遍公式”）这个公式可以正确产生所有的素数。历史上有许多试验的例子：17世纪初法国数学家梅森(Mersenne)在他的一个著作当中讨论了这样一种我们现在称之为梅森素数的素数，Mp=2^p-1，本来以为只要p是一个素数，n=2^-1就会是一个素数，这在p=3，p=5，p=7都是正确的，但是p=11时 2^-1=2047=23times 89就不是素数了。
检验素数
检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于sqrt的所有素数去试除，若均无法整除，则N为素数。 |
|
- 哥德巴赫猜想：是否每个足够大的偶数均可写成两个质数之和？
- 孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
- 斐波那契数列是否存在无穷多的素数？
- 是否存在无穷多梅森素数？
- 在n^2与(n+1)^2之间每隔n就有一个素数？
- 是否存在无穷个形式如n^2+1的素数？
- 黎曼猜想
- 是否存在不定长的素数算术级数？ |
|
| 素数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入素数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找素数的过程（分解质因数）过久而无法解读信息。 |
|
|
|
|