是什么让素数如此特别？

luyuanhong

是什么让素数如此特别？

原创 慕容玖玖 数来数趣 2024 年 05 月 10 日 11:46 上海

“是什么让素数如此特别？”

这是 125 个新科学问题的第一问。2021 年，上海交通大学携手《科学》杂志发布“新 125 个科学问题”——《125 个科学问题：探索与发现》。其中三个数学问题被列在首位，第一个问题就是关于素数的。下面是这个问题描述的中文翻译：

是什么让素数如此特别？

素数：只能被 1 和其本身整除的数，有无限多个。对于数学家、计算机科学家和其他专家来说，其存在性和属性非常有趣。虽然所有的自然数都可以表示为素数的乘积，但将大数分解为素数的积却存在很大困难。由于素数具有与分解相关的独特属性，因此它们在密码学领域非常有用。想象一下，计算机加密依赖于一个非常大的数字，例如具有数十甚至数百位数字的多个因数的数字；即使是超级计算机在识别其素因数方面也会面临巨大的挑战，这使得素数在信息加密领域极有潜力。

素数被列在 125 个科学问题之首，可见素数的重要性。千百年来，数学家们一直在追寻素数的规律，挖掘它们隐藏的深层奥秘。本文将从素数的定义开始，介绍素数在数论中的重要地位，以及数学家为寻找素数和研究素数的分布提出的各种定理和猜想。

素数有无限多个

素数，又称质数，指在大于 1 的自然数中，除了 1 和它本身外，无法被其他自然数整除的数。

大于 1 的自然数若不是素数，则称之为合数。

例如，23 是个素数，因为其正约数只有 1 与 23 。而 22 则是个合数，因为除了 1 与 22 外，2 与 11 也是其正约数。对于比较小的数字，我们很容易判断是不是素数，一旦数字变大，这个工作就变得很困难。

一个很自然的问题是：素数有多少个？早在公元前 300 年，古希腊数学家欧几里得就已经研究过这个问题了，称素数有无穷多个，并用反证法给出了证明。

证明：

假设存在有限个素数，将他们写在一个集合里，用 { 2,3,…,p } 表示，其中 p 是集合里最大的素数。然后我们定义

      q = ( 2 × 3 × … × p ) + 1 。

根据假设，2,3,…,p 是素数，并且 q 不能被 2,3,…,p 整除。因此，q 不能被任何素数整除，根据素数的定义，q 是一个素数并且大于 p ，所以 { 2,3,…,p } 不是全部的素数，故与假设矛盾，“素数有有限个”这一假设应该被否定。

但要注意的是，此证明并不说明 n 个素数的乘积与 1 的和是素数。例如：

      2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509 。

“素数有无穷多个”这一命题简单却魅力无穷，2300 多年间，许多数学家都给出了数以百计的证明。但在众多证明中，英国数学家哈代 (G. H. Hardy) 在《一位数学家的辩白》 (A Mathematician's Apology) 一书中称欧几里得的证明历久弥新，依然如初发现时一样重要， 两千年的时光不曾刻下丝毫褶痕。如果你想了解更多的证明，可以阅读参考文献[1].

素数的重要性

要说素数在数论中的重要地位，一个定理便足以说明，那就是算术基本定理：

定理 1（算术基本定理 ）

任何大于 1 的整数要么本身就是素数，要么可以写为两个或以上的素数的乘积，如果将这些素因子按大小排列之后，写法唯一。

例如:

66 = 2 × 3 × 11 ，221 = 13 × 17 ，6936 = 2^3 × 3 × 17^2 ，1200 = 2^4 × 3 × 5^2 。

定理具体的证明如下：

证明

假设存在不能分解成有限个素数的乘积的合数，根据最小数原理，其中必有一个最小的数，设为 n 。根据合数的定义，存在小于 n 的自然数 a,b 使得 n = a b 。

如果 a,b 都是素数，与假设矛盾.

如果 a,b 至少有一个是合数，由于都比 n 小，所以这个合数一定可以被分解成有限个素数的乘积，用乘积替换这个数，可推出可以分解成有限个素数的乘积，与假设矛盾。

总之假设不成立，结论成立。

唯一性证明略。

从这个定理中我们可以理解，为什么要规定 1 不是素数，因为在因式分解中可以有任意多个 1 ，这样就破坏了分解的唯一性。算术基本定理又称为正整数的唯一分解定理，所以一些数学家将素数喻为构成数学大厦的砖块。

关于正整数的分解不得不提著名的哥德巴赫猜想。哥德巴赫猜想是德国数学家哥德巴赫（Christian Goldbach）于 1742 年提出的。

猜想 1（ 哥德巴赫猜想 ）

任何一个大于 2 的偶数都可以表示为两个素数的和。

例如：

4 = 2 + 2 ，6 = 3 + 3 ，8 = 3 + 5 ， 20 = 3 + 17 ，依此类推。

由于任何一个大于 5 的奇数减去 3 都是一个偶数，若哥德巴赫猜想成立，那么任一大于 3 的整数都可以表示为 2 个或 3 个素数的和。这是一个多么令人激动的结论啊。

虽然哥德巴赫猜想尚未被证明，但已经在计算机上通过枚举的方式验证了很大范围内的情况。但我们相信，这个难题一定能被攻克。而一旦猜想被证实，那么素数的地位将更加凸显。

寻找素数

自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，找到判定素数的方法。遗憾的是素数随机出现在数字当中，没有任何规律。到了高斯时代，基本上确认了简单的素数公式是不存在的。

缺少规律意味着只能通过一个一个的试验来寻找。其中一个常用的生成素数的筛法称为埃拉托斯特尼筛法（sieve of Eratosthenes），简称埃氏筛，得名于古希腊数学家埃拉托斯特尼.

埃氏筛基本步骤是从最小的素数 2 开始，将该素数的所有倍数标记成合数，而下一个尚未被标记的最小自然数 3 即是下一个素数。如此重复这一过程，将各个素数的倍数标记为合数并找出下一个素数，最终便可找出一定范围内所有素数。

这一过程的动图如下图所示：



前 20 位素数依次是：

2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71 。

尽管如此，素数本身还是有很多优美的内在规律的。

对整数 a ，如果 p 是素数，则 a^p - a 是的 p 倍数。这就是费马小定理。比如，a = 2 ，p = 31 ，则， 2^31 - 2 = 2147484646 是 31 的倍数。

在寻找素数时，欧几里得曾提出有少量素数可以写成 2^p - 1（其中指数 p 为素数）的形式。究竟有多少个素数可以写成这种形式？欧几里得把这个问题留给了后人。于是，费马、笛卡尔、哥德巴赫、欧拉、高斯……几乎所有大数学家都研究过这种特殊形式的素数，17 世纪的法国数学家马林·梅森是其中成果最为卓著的一位。

梅森学识渊博、才华横溢，是法兰西科学院的奠基人和当时欧洲科学界的中心人物。为了纪念他，数学界就把型的数称为“梅森数”，并以记之；如果为素数，则称之为“梅森素数”。然而，2300 多年来，人类仅发现 47 个梅森素数。这种素数新奇而迷人，因此有“数学珍宝”的美誉。梅森素数历来是数论研究的一项重要内容，也是当今科学探索的热点和难点之一[2].

另外在寻找素数时还有下面几个著名猜想。

孪生素数猜想：是否存在无穷多个素数 p ，使得 p+2 也是素数？

勒让德猜想：是否在所有连续的平方数之间至少存在一个素数？

未命名猜想：是否有无穷多个素数 p ，使得 p - 1 是一个平方数？换句话说：是否有无穷多个形式为 n^2 + 1 的素数？

在 1912 年国际数学家大会中，埃德蒙·兰道列出了关于素数的四个基本问题，就是上述 3 个猜想外加哥德巴赫猜想。这些问题在他认为是“在当前的数学认识下无法解决”，后人称之为兰道问题。到 2023 年为止，所有四个问题都未得到解决。

素数的应用

别以为研究素数只是数学家们的消遣和游戏，事实上素数的研究在当代具有十分丰富的理论意义和实用价值。

比如寻找梅森素数是发现已知最大素数的最有效途径，它的探究推动了数论的研究，促进了计算技术、程序设计技术、密码技术、网格技术的发展以及快速傅立叶变换的应用。另外，梅森素数的探究方法还可用来测试计算机硬件运算是否正确。

素数理论是 RSA 加密算法的基石。两个大素数相乘非常容易，但将它们的乘积分解回这两个素数则非常困难。正是基于此不对称性，MIT 的三位大咖在 1977 年发明了 RSA 算法。RSA 是他们三人姓名的首字母。这是一种公开密钥算法，这个算法广泛应用于数字通信和网络安全领域，为信息的加密和解密提供了高度的安全性。

此外，素数还在随机数生成、哈希函数设计、错误检测和分布式计算等领域发挥重要作用。

参考文献

[1] 卢昌海.素数有无穷多个之九类证明. https://www.changhai.org/articles/science/mathematics/IP.php

[2] 梅森素数为何这样重要. https://mathcubic.org/article/article/index/id/113.html

媒体报道

等你求解！上海交大携手《科学》杂志向全球发布 125 个科学问题 https://news.sjtu.edu.cn/mtjj/20210412/145693.html

图片来源

文中动图：Sieve of Eratosthenes。https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

作者： 慕容玖 橘子数学社区核心成员

来源：橘子数学专栏 https://www.mathcrowd.cn/challenges/479