是什么让素数如此特别?

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

这是125个新科学问题的第一问. 2021年, 上海交通大学携手《科学》杂志发布“新125个科学问题”——《125个科学问题：探索与发现》 ^[1]. 其中三个数学问题被列在首位, 第一个问题就是关于素数的.

是什么让素数如此特别?

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

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

素数有无限多个

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

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

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

一个很自然的问题是：素数有多少个？早在公元前300年, 古希腊数学家欧几里得就已经研究过这个问题了, 称素数有无穷多个, 并用反证法给出了证明. 你可以点击下面的证明进行阅读.

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

素数的重要性

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

例如:

,

定理具体的证明如下.

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

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

例如：

, , , ,以此类推.

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

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

寻找素数

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

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

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

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

前20位素数依次是：

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

对整数, 如果是素数, 则 是的倍数. 这就是费马小定理. 比如, , 则, 是 的倍数.

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

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

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

孪生素数猜想：是否存在无穷多个素数, 使得也是素数？

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

未命名猜想：是否有无穷多个素数, 使得是一个平方数？ 换句话说：是否有无穷多个形式为的素数？

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

素数的应用

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

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

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

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