不可思议的素数（上）

数学算法俱乐部

日期：2020年03月20日

正文共：4658字5图

预计阅读时间：12分钟

来源：算法与数学之美

序 

素数研究是纯粹数学的精华，也是支撑现代网络经济的基础。我们在网购时，会发送信用卡账号等个人信息。为了防止在此过程中个人信息被盗，必须对这些信息进行加密处理。接下来我们会讲到，加密处理正是运用了费马和欧拉等数学家所发现的素数的性质。

1 埃拉托斯特尼筛法与素数的发现 

把一个整数表示分解成其他整数的乘积，这叫作因数分解。乘积中的整数称为原来整数的因数。例如，因为6 = 2 × 3 = 1 × 6，所以 6 的因数是 1、2、3、6。另外，7 的因数只有 1 和 7。 

素数指的是“只有 2 个因数的整数。”例如，7 是素数，而 6 就不是。而且，1 的因数只有 1，即“只有 1 个因数”，所以不是素数。实际上， 1 不属于素数还有另外一个重要的原因，不过我们到后面再解释这个原 因 。此 外 ， 既 不 是 素 数 也 不 是 1 的 数 统 称 为 “ 合 数 ”。 

接下来我们试着从2 到 99 的整数中找出素数。首先列出所有的整数: 

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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 

第1 个素数是 2，那么把 2 圈起来。再按顺序排除 2 乘以 2、3、4 的倍数。 

在剩余的数字中，2 后面出现的是3。没有排除3 说明3 不是2 的倍数，所以3 的因数只有1 和3。从而可以推出，3 是素数。那么接下来把3 圈起来，再排除3 的倍数。在剩余的数字中，3 后面出现的是5，所以5 也是素数。然后把5 圈起来，再排除5 的倍数。反复进行以上操作，得出了以下结果。

最后我们发现剩下的2、3、5、· · · 都是素数。这种筛选素数的方法叫作“埃拉托斯特尼筛法”。因为是按顺序筛去合数。埃拉托斯特尼是公元前3 世纪活跃在埃及亚历山大的研究者，他还会出现在第6 章的“测量地球周长”章节中。直到现在，我们改良了埃拉托尼特尼筛法，并将其运用于制作素数表。

2素数有无穷个

古埃及《莱因德纸草书》中曾记载着素数。不过，据说到了古希腊时期，人们明确认识到素数是数的基本。特别是在公元前300 年左右欧几里得编写的《几何原本》中详细研究了素数的性质。

与欧几里得同时期的德谟克利特提出了“原子论”，认为万物都是由基本单位“ 原子”( a t o m ) 所构成。在古希腊语中，“ a t o m ” 的“ t o m ” 是“ 切割、分割” 的意思，“ a ” 是表示否定的接头词。也就是说，“ a t o m ” 是“无法分割”的意思。因为整数可以被因数分解成素数，却不能继续分解，所以也可以认为素数是“ 数的原子” 。有趣的是，“ 原子论” 和“ 素数”在同一个时期被发现。虽然无法考证哪一个更早出现，不过也许二者是相互影响、相互发展。

在欧几里得《几何原本》记载的多个素数性质中，最重要的定理是素数有无穷个。其实，是公元前5 世纪左右毕达哥拉斯学派的人证明了这条定理。

毕达哥拉斯学派的人发明了从已知素数找出新素数的方法。例如从2 个素数2 和3 开始，首先将这两项相乘后加1，即

2×3+1=7 

7不管是除2还是除3都会余1，所以2和3都不是7的因数，即7是素数。证明2、3、7 是素数后，在将这三项相乘后加1，得到的数除以上述三项中的任何一个数都会余1。

2 × 3 × 7 + 1 = 43 

所以43 也是素数。继续验算。

2 × 3 × 7 × 43 + 1 = 1807这个数除以2、3、7、43 其中的任何一个数都会余1。然而，1807 并不是素数。其实，1807 = 13 × 139 可以用2 个质素即13 和39 的乘积表示。1807 用2、3、7、43 其中的任何一个数都无法整除，因此其分别得到的13 和39 是素数2、3、7、43 之外新发现的素数。那么将最小的13 和上述四个素数相乘后加1，得到

2 × 3 × 7 × 43 × 13 + 1 = 23479 = 53 × 443 

这样一来，又出现了53 和443 这两个新的素数。将已知素数相乘后加1，得到的数都用已知素数无法乘整除。如果这个数是素数的话，就出现了新的素数。如果是合数，其因数中会包含新的素数。然后把其中较小的素数与原来的几个素数相乘，从而又发现新的素数。于是会源源不断地发现新的素数，所以素数有无穷个。这就是毕达哥拉斯学派的人所使用的证明方法。

这个方法虽然可以不断发现素数，但是却无法证明是否适用于所有素数。因为素数的世界存在太多的未解之谜。

用素数的乘积表示自然数称作“分解质因数”。欧几里得的《几何原本》中提到了素数的另一个重要性质，即分解质因数只有一种分解方法。例如210 可以分解成2 × 3 × 5 × 7，除此之外没有其他分解方法。

既然素数是“数的原子”，那么如果某些分解方法可以解出不同素数的话，就有点不可思议了。所以绝对不会发生这种事，也就是说，分解质因数只存在唯一一种分解方法，这被称作“算术基本定理”。可能会有人认为这看起来是理所当然之事，却被冠以“基本定理”如此隆重的名号。然而，我们同样可以想象如果这条定理不成立的话，数学世界又是一番怎样的景象。感兴趣的读者请参考我个人主页的补充知识。

值得庆幸的是，在我们的自然数世界里，已经证明了“算术基本定理”，即将自然数分解成素数的方法具有唯一性。这也是为什么素数作为“数的原子”具有特殊的意义。

在上一节中，我们曾经讲过1 不是素数。如此定义的理由也来自“算术基本定理”。假设1 是素数，那么210 除了分解成2 × 3 × 5 × 7 以外，还可以分解成1 × 2 × 3 × 5 × 7 或者1 × 1 × 1 × 2 × 3 × 5 × 7 等。如果1 是素数，那么基本定理的定义也变得有些繁琐，例如“自然数因数分解成1 以外的素数的方法只有1 种”。其实，把1 排除在素数以外的根本原因在于为了尽可能简洁明了地表达这个重要的定理。

数学家研究素数性质就如同物理学家努力研究物质的基本要素“基本粒子”的性质一样。分解质因数的方法只有一种，这个定理同时也证明了素数是自然数的最小单位。“算术基本定理”的名号也是当之无愧。

3素数的分布存在规律了解素数有无穷个后

如果将素数排成一行

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,··· 

能发现存在什么规律呢?从古希腊时期开始，直到现在这个问题依然吸引着数学家的兴趣。

发现素数的规律就像是发现元素周期表。19世纪的化学家德米特里·门捷列夫依照原子量排列已发现的原子时，发现其性质中存在周期性规律，并且运用这个规律预言了新的原子的存在。而且，门捷列夫的元素周期表对阐明20 世纪的原子构造发挥了巨大的作用。与此相同，如果能发现数的原子即素数的规律，就能更深入地阐明数的秘密。

在第1 节中，使用埃拉托斯特尼筛法确定了小于99 的素数。一位数的素数共有4 个，分别是2, 3, 5, 7 两位数的素数共有21, 个，分别是

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47，53, 59, 61, 67, 71, 73, 79, 83, 89, 97 

而且，3 位数的素数有143 个，4 位数的素数有1061 个。

1 位数的自然数有9 个，所以9/4 ≈ 2.3 个数中就有一个数是素数。2 位数的话就是4.3 个数中有一个是素数。3 位数的话就是6.3 个数中有一个是素数。

4 位数的话就是8.5 个数中有一个是素数。

如上所示，素数的间隔与位数成正比。因此，根据这个数据计算比例系数的话，可以推出如果是N 位数的数，那么N × 2.3 个数中有一个是素数。

其实，2.3 这个比例系数就是使用第3 章中出现的自然对数所表示的ln 10 = 2.302585093 · · · 的近似值。因为对数有一个性质

所以N 位数的数量N × ln 10 ≈ N × 2.3 中有一个数是素数，那么也可以说中有一个数是素数。第3 章中出现的自然常数e 在此处也发挥了作用。

数学家高斯在15 岁时，就像我们刚才那样寻找素数分布的规律，猜想小于 n 的素数的个数为n/ln n 个。高斯的猜想和我们观察结果“N 位数的话，差不多中就有一个数是素数”具有相同的意义。随着位数的增加，高斯的预测也越准确。1896 年，普森和雅克· 阿达马分别证明了高斯的预测，这也是广为人知的“ 素数定理”。虽然欧几里得证明了素数有无穷个，但是素数定理更加精确地表示了素数增加的速度。

除了素数定理以外，自古以来就存在许多有关素数规律的猜想，其中只有一小部分得到证明。其中最有名的当属孪生素数有无穷个的猜想。最近有研究在很大程度上推进了该猜想的发展，请参照我个人主页的补充知识。

4用素数判定“帕斯卡三角形”

有关素数的另一个重要问题是开发判断某个自然数是否是素数的方法。后面我们还会提到，互联网交易时所使用的密码需要用到300 位数左右的大素数。发现大量的大素数在保护通信秘密中具有实用意义。

判断某个自然数是否属于素数最简单的方法是依次除以小自然数，研究是否能够分解成因数。例如给定一个数是4187，依次除以2、3、4··· 如果可以整数的话就是合数，即判断不是素数。实际上，不需要除到4187，只要到平方根左右即可。例如4187 = 53 × 79，小的因数53 小于。

但是，如果使用这个方法判定300 位数是否是素数，因为的平方根是，所以必须一一验证是否能够被个数整除。所谓的“京速计算机”可以在1 秒内进行次的演算。宇宙的年龄有138 亿年，差不多 秒，那么，即使用京速计算机从宇宙诞生起计算到

现在，也只能进行 次。这样还是无法判断300 位数是否是素数。在判断素数的方法中，有一个方法使用了帕斯卡三角形。什么是帕斯卡三角形?如下所示: 

帕斯卡三角形从最顶端的1 开始，按照以下规律排列。(1)各行的两端都是1。(2)各行的相邻数字相加后等于下一行的数字。

例如我们看一下第2、3、4 行，

很明显，从第2行向第3行推移时，1 + 1 = 2。从第3行向第4行推移时，1 + 2 = 3。

帕斯卡三角形第(n + 1) 行排列的数字同时也是(x + 1)n 展开成x 的乘方时所出现的系数。例如: 

右边的系数与帕斯卡三角形中排列的数字之间的关系也一目了然。

观察(x + 1)n 展开式的系数，发现n 是素数时，存在特殊的规律。

例如，n = 3、5、7 等素数时，

第一项的1 和最后一项的xn 的系数都是1，除了这两项以外，其余的系数等于n 的倍数。例如在(x + 1)7 的展开式中出现的系数7、21、35 都是7的倍数。

不过，当n 是合数时，部分系数不是n 的倍数。例如在n = 4 = 

2 × 2 中，

 的系数6 就不是n 的倍数。接下来我们来思考一下关于一般的n。按照帕斯卡三角形的规律(1) 

和(2)进行计算，的展开式应该为

除第一项和最后一项以外，分子中都带有n。假设n 是素数，素数除了1 和它本身外，不能被其他自然数整除。因为分母都小于n，所以分母中的数都无法除以n。因此，系数n 被保留下来。也就是说，系数都是n 的倍数。

然而，如果n 是合数的话，结果就不一样了。例如n = 2 × k，假设k 是奇数。将n = 2 × k 代入刚才的展开式，得到

观察的系数， 

因为k 是奇数，所以k(2k − 1) 也是奇数。不过又因为n = 2k 是偶数，所以这个数无法被n 整除。分子中的n = 2k 刚好被分母中的2 整除。这同样适用于其他合数。

也就是说，展开成x的乘方时，除和1以外的系数如果能被n 整除的话，n 是素数，否则n 就是合数。

这看起来是判断大数字n 是否是素数的一个好方法，但是仅靠这个方法还远远不够。因为的展开会有(n + 1) 项，如果一一确认所有系数是否为n 的倍数即分别用2、3、4 · · · 除以n 的话，方法虽然简单却十分费时。那么有没有一种高效的方法呢？请听下次分享…

本文来源《用数学的语言看世界》，本书由人民邮电出版社图灵新知出版。

本书阐述了求解微积分的技巧，详细讲解了微积分基础、极限、连续、微分、导数的应用、积分、无穷级数、泰勒级数与幂级数等内容，旨在教会读者如何思考问题从而找到解题所需的知识点，着重训练大家自己解答问题的能力。

本书适用于大学低年级学生、高中高年级学生、想学习微积分的数学爱好者以及广大数 学教师。本书既可作为教材、习题集，也可作为学习指南，同时还有利于教师备课。

— THE END —