从“三七二十一”到“素数之无穷”

你不一定要点蓝字关注我的

        如果我只有一次机会给朋友讲数学，考虑到所讲的东西既要不失数学的重要性和趣味性（里子上过得去），同时也不能有损我在对方心目中的形象、我们的交情（面子上过得去），我想我会从“三七二十一”讲起。 林开亮

                它表达的是一个众所周知的事实，3×7＝21
        如果我们把这个等式换一个写法，21=3×7
        那么可以得到新的理解：21可以写成3和7的乘积。事实上，21=3×7＝7×3是21唯一的非平凡的因子分解。除此之外，21还有一个平凡的因子分解：21＝1×21＝21×1。
        聪明的读者大概猜到我要讲什么了。对了，就是初等数论。

                初等数论是研究整数的一门学问，其中一个极重要的概念是素数。对于一个大于1的整数，如果只存在平凡的因子分解（换言之，其因子只有1和它本身），那么就称为素数（或不可约数），否则称为合数（或可约数）。    （注意，1既不看成素数、也不看成合数，这种约定，只是为了让理论更简单。）
        例如，2, 3, 5, 7, 11…是素数；而6, 8, 9, 10,12…是合数。
        在某种意义下，你可以认为素数比合数更简单。事实上，素数是构造合数的基本积木。
        例如，21是合数，因为它有非平凡的因子分解21=3×7＝7×3，而其中的两个因子3和7都是素数。再如，12也是合数，它的素因子是2,2, 3，因为12＝2×2×3。

        数论中一个基本的结果是算术基本定理：任何一个合数都可以分解为素数的乘积，而且在不计因子的次序的意义下，其分解是唯一的。        这个定理有时也称为素因子的唯一分解定理。

        对于具体给定的合数，比如21或者12，这是很容易验证的。我们来看12的情况，虽然12还有两种非平凡的分解12＝3×4＝2×6，但是注意到，其中的因子4和6并不是素数。因此这两个分解都不是素因子分解。
        上述定理的威力在于，素因子分解的存在性与唯一性，对任意的合数都成立。
        我们不妨暂时先承认这个定理的正确性（事实上早在2000多年前，古希腊的数学家就证明了这个定理）。这样一个存在性定理立即会引出一个问题：对于任意给定的一个大于1的数，如何判定它是否为素数；如果它不是素数，那么作为合数，如何求出它的素因子分解？

        第一个问题又称素性检验问题，也许你会冒出一个天真的想法，可以一劳永逸地解决它：如果我们能够列举出所有的素数，那么对一个给定的数，判定它是否为素数就是小菜一碟了！
        然而，我们大概永远也无法做到这一点——比天空中星罗棋布的点点繁星，素数的分布更加令人难以捉摸！虽然目前尚不清楚，大大小小的星体是否有无限多个，但存在无穷多个素数这一点则是毫无疑问的！
        因此，素数序列“ 2,3, 5, 7, 11…”中的省略号，所表示的其实是一种无奈（而非偷懒）。
       “凡是我们不能言说的，我们必须保持沉默。”（引自奥地利哲学家维特根斯坦）
        原则上，你可以继续往下写出更大的素数，13,17,19,23… 然而迟早在某一步（比如，当你挂掉时），你会感叹，还是素数更永垂不朽。也许那时你会修改曹丕的话：“年寿有时而尽，荣乐止乎其身，未若素数之无穷”。（在曹丕的原文中，最后一句是“未若文章之无穷”。）

                尽管如此，我们还是有一个方法来处理素性检验问题。它是基于这样的想法，对给定的有待检验的数，如果它是合数，那么其素因子必定小于它（其实是不超过它的平方根），而我们有一个方法可以列出所有不超过某个给定数的素数，然而逐一判定这些素数是否是它的因子，如果发现了一个素因子，那么这个被检验的数就是合数，否则就是素数。这个方法是基于这样的想法：罗列出一定范围内的所有合数是相对容易的，于是剩下的就是素数了。
        比如说，我们要选出2到144之间的所有素数，那么就只需要去掉其中所有的合数，也就是那些是2,3,…144的倍数的数。
        然而事实上，真正需要考虑的数并没有那么多，这是因为如果一个介于2和144之间的数是合数，那么它一定有一个因子不超过（请思考为什么）。因此，我们只需要去掉2,3,…12的那些倍数。更进一步，我们只要考虑2,3,…12的中的素数，即2,3,5,7,11。现在我们就来做这件事。
        在2到144的这143个数中，首先去掉2的所有真倍数，即所有大于2的偶数。得到的数很容易看出来：

        因此，我们的任务化简为在3到143的所有奇数中依次去掉3,5,7,11的真倍数。例如，在去掉3的所有真倍数以后，我们得到

        接下来我们只需要依次去掉5,7,11的真倍数就可以得到所有小于等于144的素数了。5的所有真倍数很容易被识别（我们用方框把它们标记出来）：

        同样的，我们再去掉7和11的真倍数。最后，我们将得到不超过144的所有素数，共有34个：

        这个得到素数的方法被称为埃拉托色尼(Eratosthenes)筛法。之所以称为筛法，是因为它把不要的合数都筛掉了，剩下的正是所需的素数。

                埃拉托色尼（公元前276‐194年）是与阿基米德（Archimedes）同时代的古希腊人。他既是数学家，又是天文学家。埃拉托色尼的一个最有名的成就是，在大约2300年前，他对地球半径做出了一个非常精准的测量，误差在11%以内。考虑到当时科学测量所处的原始状态，这样的精度是引人注目的。
        这方法人工操作起来当然有点繁琐，也容易出差错，但交给计算机来做，完全可以放心。尽管如此，在寻找大素数和对较大的数求素因子分解方面，计算机的效率和能力也是有限的。正是这一固有的困难，确保了将素数应用于密码的安全可靠性。其想法是很简单的：如果我用了你不知道的超级大的素数，那么计算机在它有生之年破解的几率小得可怜。
        哪怕是对于比计算机算得还快的人，在对超级大的数求因子分解这个问题面前，也绝不可能显出其高明来。如果你碰到一个在数学方面自以为是、狂妄自大的人，想要打击他或者打发他，很容易——你随便写一个比较大的数，比如，12345678910111213（只要你乐意，还可以往下写，甚至写得更复杂），然后只需问他：这个数是不是素数，如果是，何以见得；如果不是，其素因子分解是怎样的。

        接下来，对于那些可能会问“为什么素数有无穷多个”的朋友，我想介绍一个经典的证明。在给出这个证明之前，我先要说明一下，证明在数学中的含义。
        在数学中，证明是一串逻辑推导（因为……所以……）的链，每一步推导（即给出从“因为……”到“所以……”的理由）所代表的，是一种无懈可击、唯一的逻辑必然。虽然数学家常常“言必称证明”，但正如英国著名的物理学家爱丁顿（Eddington）一针见血指出的：“证明是数学家自己折磨自己的幽灵。”
        在实际生活中，所发生的一切都只是选择，其选项往往很多，所谓逻辑上的必然性与数学上的正确性，在生活中根本不存在（请你不要绝望，这是好事）。这么说吧，生活被机遇和偶然所主宰（合情即可理解），而数学则听命于逻辑和必然（必须合理）。
        听起来好像生活比数学容易，因为数学需要讲道理，生活中的事情则未必。比如《大话西游》里头，至尊宝与菩提有段经典的对白：

                事实上，也许讲道理的数学更简单。20世纪著名的数学家冯·诺依曼（von Neumann）曾说：“如果有人不同意数学是简单的，那仅仅是因为，他们没有意识到生活是何等复杂。”
        也许你并不这么认为，那么接下来我就来介绍一下“素数之无穷”的证明，让你感受一下数学家是如何通过讲道理而让你明白隐藏的事实，让你领略一下数学中无懈可击的证明的威力。

1证明一

        这个证明基于反证法。假定只存在有限多个素数，比方说是所有的素数。我们将证明这一假定将导出矛盾。考虑自然数只有两种可能：第一种可能是N本身是素数；第二种可能N是是合数，从而含有一个素因子。第一种可能是不成立的，因为N大于中的任何一个，所以它不是素数（因为在“是所有的素数”的假定下，每一个素数必等于某个）。我们容易看出，每一个素数都不整除N，这说明N没有素因子，第二种可能也不成立。因此，假定不成立。从而素数有无限多个。

        反证法是基于这样的想法：一个命题与其否命题，有且仅有一个成立（势不两立）。因此要证明某个命题（素数有无穷多个）成立，只要证明其否命题（素数至多有有限多个）不成立。也许有人不喜欢反证法，认为它绕，不直接。在本例的情况，很容易把上述证明写成一个直接的证明。如下：

2证明二

        设我们已经有素数，我们将证明，存在一个新的素数。考虑自然数只有两种可能：第一种可能N是本身是素数，那么此时它就是新的素数；第二种可能N是是合数，从而含有一个素因子，而这个素因子一定不是之一，从而也是一个新的素数。将新得到的素数记为，考虑素数，重复之前的操作，我们继续得到新的素数，按照这种方式，我们可以列出无穷多个素数。

        原则上讲，数学中只需要一个证明。相比于第一个证明，第二个证明的好处在于，让你更容易理解、更心安。正是因为有了这种一劳永逸的证明，数学中的许多微妙事实（比如算术基本定理）才放之四海而皆准。
        为了避免让你误认为数学就是一堆证明，我要立即指出，数学最有活力的部分在于，猜出所要证明的东西，也就是猜想。本质上讲，数学家所做的事情，就是基于部分已知的事实，猜出一些美妙的一般事实，然后想办法证明。
        比起《大话西游》里紫霞仙子对理想的坚定追求，数学家对猜想的执着，有过之而无不及。

        在这里，我想借此机会介绍数论中的几个猜想（更多有趣的猜想，可见英国数学家盖伊所写的《数论中未解决的问题》），一个是哥德巴赫猜想，一个是孪生素数猜想。

哥德巴赫猜想

        哥德巴赫（Goldbach）是18世纪的德国数学家，他曾猜想，任意一个大于2的偶数（双数）都可以写成两个素数之和。        这个猜想至今未被证明，而取得的最好结果属于中国数学家陈景润，他在1973年证明了：每个充分大的偶数或者是两个素数之和，或者是一个素数与一个“半素数”之和。所谓“半素数”，就是可以写成两个素数之乘积的数，如6，它本身不是素数，不过可以写成两个素数2与3的乘积。

孪生素数猜想

        另一个著名的猜想叫孪生素数猜想。如果两个素数之间相差2（相差1的只有唯一可能：2与3），那么这样的一对素数称为孪生素数对，例如，5与7，11与13,17与19。        孪生素数猜想说，存在无穷多对孪生素数对。这个猜想至今也是悬而未决，不过几年前，华裔数学家张益唐对此作出了突破性进展，这是当代的数学传奇。对此有兴趣的读者，很容易从网上获得了解。

                最后我愿意补充一个猜想，它未必有意思，但与我们对“素数之无穷”的证明有关。我斗胆猜想：对任意的大于或等于2的整数k，形如的素数有无穷多个，其中是两两不同的素数。
        我们看最简单的情况时，这个猜想相当于说，形如的素数有无穷多个，其中p是素数。这其实是一个古老的猜想，与19世纪的一位名叫索菲·热尔曼（Sophie Germain）的法国女数学家的工作相联系。

        老实讲，对于这个猜想的正确性，我并没有多大把握，至于它是否重要、是否有趣，我就更没有信心了（不过有朋友告诉我，他们认为挺有趣）。毕竟，只是在准备写这篇文章时，我偶然想到这个问题。
        说不定，与此同时，你也想到了一些问题、做出了一些猜想，这就是数学的真正乐趣之一：数学是思维的体操，它能引发你思考。
        我想说，正是对那些未解决的问题的深入思考，引导着数学家在广袤无垠深不可测的数学天地中继续开拓，让他们最终能够确定地回答一些极其简单的问题，如“素数之无穷”。
        也许可以这么说，不论是在生活中还是数学中，都存在许许多多问起来简单而回答则不易的问题，数学家研究、发展数学，一个重要的动机，就是要回答那些问题。正如20世纪的德国大数学家希尔伯特（Hilbert）所说：我们必须知道，我们必将知道。
        如果你是第一次见到我的名字，并且“不管三七二十一”读完了这篇文章，那么此时我希望你的表情是这样的： 

本文作者：        林开亮，先后就读于天津大学和首都师范大学数学专业，现任教于西北农林科技大学。热衷数学科普的翻译与写作，曾主持翻译《当代大数学家画传》和《数学与人类思维》，参与翻译《数学家讲解小学数学》。发表的部分作品可见http://math.sjtu.edu.cn/conference/Bannai/2016/talk.php?20160612A转载自：超级数学建模（微信号supermodeling）

公众号ID：maths112358关注“数学爱好者俱乐部”，更多靠谱的数学科普知识，还有“牛娃路”，“烧脑趣题”，“教学分享”等。