You have no items in your shopping cart.
Blog archive
孤独而高冷的素数
Sunday, April 12, 2020
没有大胆的猜想，就做不出伟大的发现
——牛顿
引言
素数（又称质数）历来都是数学界的宠儿，有关素数的话题在数学界总能引起热议，其原因可能就在于它那孤独又高冷的一面，常常让人可望而不可及。
2018年伊始，隔壁的日本人就干了一件让国人匪夷所思的事。他们把2017年12月26日发现的迄今为止的最大素数——第50个梅森素数——印成了一本书，书名为《2017年最大的素数》，这本书厚32mm, 共719页。最重要的是整本书只印了一个数，即2^77232917-1，这个数一共23249425位，如果按照2个数字一个字来算，那就是1000多万字的巨著了。让人不可思议的是，这本售价约113人民币的书在发行两周后迅速登上日本亚马逊数学类畅销书的第一位，且卖到断货。
有关素数的著作多得像浩瀚宇宙中的星辰，但我眼中最亮的那颗当属《素数之恋》。从来没有哪本数学书像它这般让我着迷。它把深奥的数学阐述的如此浅显易懂又不乏严谨，它将历史人文与数学融为一体，相得益彰。从小学就能看懂的素数定义和求法，到简单的初等数论，最后到复杂的解析数论，它跨越了千年的时空，娓娓道来，一气呵成。它用毕达哥拉斯、欧几里得、牛顿、欧拉、高斯、伯努利、费马、黎曼、罗素、勒让德、希尔伯特这些闪亮的明珠串起了整个数学史。
为什么这本书如此吸引人？因为作者是学数学里最会写小说的，又是作家里数学学的最好的。
正是由于质数独特而神秘的气质，它甚至成为了小说的主角。《质数的孤独》是意大利80后作家、粒子物理学博士保罗·乔尔达诺的处女作。质数是只能被1和自身整除的数字，它们是所有整数中特殊又孤独的存在，作者形象地用质数这一数学概念来形容两人孤独的状态。2008年《质数的孤独》一经出版，即获得意大利最高文学奖斯特雷加奖，并迅速成为欧美超级畅销书，迄今在欧洲销量已超过500万册。
什么是素数？
我想以扎西拉姆·多多的一首歌曲《班扎古鲁白玛的沉默》开始，歌词的一部分是这样的：
你见，或者不见我，我就在那里，不悲不喜。
你念，或者不念我，情就在那里，不来不去。
你爱，或者不爱我，爱就在那里，不增不减。
为了说清楚什么是质数，我们先从自然数开始。
自然数，顾名思义，是大自然的一种客观存在。有些人可能不服，“自然数看不见摸不着，也能叫客观存在？” 但它确实自宇宙诞生起就存在着，等待智慧生物去发现它并表示它，正如上面的歌词所说“你见，或者不见我，我就在那里”。
数数是人类诞生起就面临的最基本任务，不论在地球的哪个角落，虽然人类对的数字的表示方式可能千差万别，但终究面临着要判断自己的早上放出去的牛羊晚上有没有全部归来的问题。
素数，也是这么一个存在，不管你念或者不念它，它就在那里。在数的历史发展过程中，人类“发明创造”了许多数，有的甚至连创造者本身都觉得不真实，所以被称为虚数。但至少素数，它是一种客观存在。
素数是什么？其实很好解释。有一堆苹果，想平均分给一群人，如果不管这群人有多少（不能是1个人或与苹果个数同样多的人），都无法平均分给每个人而不剩，那么这堆苹果的个数就是素数。用数学的语言就是：一个只能被1或它自身整除的数是素数。
下表给出了100以内的素数。
怎么判断一个数是否为素数？
给定一个数N，如何判断它是否为质数呢？ 让我们直接回归最初的定义。许多时候，从最原始的定义开始，反而能无往而不利。
最笨的办法：从2开始，逐个地去除N，如果一直到N-1，都除不尽N，那么N就是素数。
但显然，这个做法做的除法有点多。比如判断101是不是质数，既然被2不能整除，它也不能被2的倍数整除，不能被3整除，那也不能被3的倍数整除，等等…… 因此，看上去只需要用比101小的素数去除101即可。
那么比101的素数有多少呢? 还有不少呢。
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
是不是要一个个去除呢？答案是否定的。许多刚学素数的同学会说，大于50的就不用试了，因为2倍已经超过101了。
但实际上还能更小。假设N=a×b, a≤b, 那么a≤根号N，也就是说如果N能表示成两个数的乘积，那么N一定有一个因子不大于根号N。从而，如果挨个地拿不超过根号N的素数去除N，一定可以有某一个数能除的尽，否则N就是素数了。
对于101，我们只需拿不超过10的素数去除，也就是2、3、5、7，如果都不能除尽，那101就是素数了。这，是不是大大降低了除法的次数？遗憾的是，我们现在很多的判断素数的程序，用的还是最笨的办法。
当然，上面的方法只能判断一个数是否为素数。如果想批量生产素数，那可以用“埃拉托斯特尼筛”法，简称“筛选法”。顾名思义，这一方法好比一个筛子，把非素数逐个筛掉，剩下的就是素数。具体做法是：
先把N个自然数按次序排列起来；
1不是质数，也不是合数，要划去；
第二个数2是质数留下来，而把2后面所有能被2整除的数都划去；
2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去；
3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去；
这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。
实际上，只需要筛选到不大于根号N即可。以N=30为例，只需进行3次筛选（分别筛掉2、3、5的倍数）即可找出30以内的所有素数。
2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，25，26，27，28，29，30
2，3，5，7，9，11，13，15，17，19，21，23，25，27，29 （第1遍筛选）
2，3，5，7，11，13，17，19，23，25，29 （第2遍筛选）
2，3，5，7，11，13，17，19，23，29 （第3遍筛选）
不要小看这一筛法，欧拉用这一思想发现了下面被称为金钥匙的欧拉公式，建立了自然数序列和素数序列之间的某种联系。
稍微观察一下，你就会发现这个公式让人惊叹的地方：公式左边是对所有自然数的某个幂次求和，而右边则是对所有素数的某个幂次的运算求积。自然数和素数之间居然有这种联系，这难道不是上帝的安排？
有多少个素数？
一个经常问的问题是：质数有多少个？ 结论是有无穷多个。
欧几里得给出了非常漂亮的反证法，足以作为反证法的经典教案。
素数有多重要？
数学家对素数的痴迷程度为什么如此之高？可以毫不夸张地说，素数之于数的重要性就相当于原子之于物质的重要性。
和原子构成了物质一样，任何一个自然数都可以看成是某些素数组合而成，这就是著名的素数分解定理：
这一定理的要点在于分解的唯一性，很多人认为这是显然的共识，但实际上这一点是可以证明的，同样可以用反证法（篇幅限制，这里就略去）。质数分解定理是数论的最基本和最重要的定理。它把对自然数的研究转化为对其最基本的元素——素数——的研究。
有了这个公式，如果你要求两个数的最大公约数或最小公倍数，那只要找出相同的质因子，并对幂指数取两者的最小值或最大值即可。
欧拉关于此还有一个欧拉定理（怎么又是欧拉？），所解决的是一个给定自然数共有多少个因数的问题。比如，8有1，2，4，8这4个因子，而12有1，2，3，4，6，12这6个因子。
在质因数分解的基础上，辅以简单的乘法原理，就可以得到一个自然数所有因数的个数为(1+a1)(1+a2)+…(1+an) （把构造一个因数作为一项任务，这一任务可分成n步，第一步选择p1的因子，第二步选择p2的因子，…，第n步选择pn的因子；而以p1为例，因数中可以不包含p1, 包含1个p1, …, 直至包含a1个p1，即一共有1+a1种选法）。
历史上的许多著名数学问题都与素数有关，比如：
哥德巴赫猜想：是否每个大于2的偶数都可以写成两个素数之和？
孪生素数猜想：孪生素数就是差为2的素数对，例比如11和13。是否存在无穷多个孪生素数对？
梅森素数猜想：2^p -1的形式，p为素数。是否存在无穷多个梅森素数？
事实上，如果哥德巴赫猜想为真的话，我们就发现了素数作为自然数生成元的另一种能力，即任何一个数都可以由2个或3个素数相加而成。
让人魂牵梦绕的素数定理
几百年来，一个问题引发了许多数学家的思考：既然素数很重要，能不能有某种规则，来产生素数？遗憾的是，这样的规则一直未被发现。
当大家在寻找素数的时候，发现随着数越来越大，素数越来越少。比如100以内有25个素数，1000以内有168个素数，1000000以内只有78498个。为什么1000以内是168个素数，而不是158个或178个？有没有一个公式或规则，能告诉我们，小于一个给定数的素数有多少个？
这个问题正是黎曼在1859年被柏林科学院任命为通信院士后向科学院提交的一篇论文，题目为《论小于某给定值的素数的个数》。
事实上，关于素数分布的问题在更早些时候已经引起了数学大家如欧拉和高斯的关注。高斯就曾给出了素数分布规律的猜想。他认为：
这一发现可以被看作是探索未知的经典案例，需要有超凡的毅力（设想一下在没有计算机的年代求几千万以内的素数）和洞察力。不妨从下表的素数个数开始。看上去没有什么规律，只能看出随着N的增大，小于N的素数密度逐渐稀疏。
我们不妨尝试观察一下这个密度到底如何变化，不妨取密度的倒数N/π(N)，如下表。稍微有一点找规律经验的人大概就看出来随着N以指数速度递增，N/π(N)大致是以固定的步长递增。
指数函数和等差的关系，稍微学过一点中等数学的人就能知道，将指数函数取对数，那就变成线性函数了。下表给出了lnN和N/π(N)的对比。
看上去是不是很简单？确实，但如果你觉得这么简单的规律你也可以发现和总结，那就错了。仅靠一支笔和一张纸，求出1000000000以内的质数，要不你试试？ 据说当年15岁的高斯没事的时候就是算素数玩，你行吗？
这个被冠以“素数定理”的命题得到了高斯、勒让德、狄利克雷、黎曼、切比雪夫、塞尔贝格、爱尔特希(Paul Erdos)和阿达马(Hadmard)等众多数学大家的重视。据说无论谁证明了素数定理，都将得到永生。
时至今日，素数定理已被证明，小于N的素数个数的上限和下限都已经给出，但π(N)的确切值是多少，依然是一个悬而未决的问题，一批又一批的数学家们前赴后继想登上最高峰，但都以失败告终，但这并不妨碍后面还有一批又一批的攀登者。
注：本文转自网络
Leave your comment