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

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

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

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

素数有无限多个

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

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

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

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

证明

假设存在有限个素数, 将他们写在一个集合里, 用 ,其中 是集合里最大的素数. 然后我们定义

根据假设, 是素数, 并且 不能被 整除. 因此, 不能被任何素数整除, 根据素数的定义, 是一个素数并且大于 , 所以 不是全部的素数, 故与假设矛盾, "素数有有限个"这一假设应该被否定.

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

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

素数的重要性

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

定理1 ( 算术基本定理 )

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

例如:

定理具体的证明如下.

证明

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

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

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

总之假设不成立, 结论成立.

唯一性证明略.

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

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

猜想1 ( 哥德巴赫猜想 )

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

例如：

, , , ,以此类推.

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

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

寻找素数

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

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

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

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

前20位素数依次是：

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

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

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

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

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

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

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

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

在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

来源：数来数趣

编辑：紫竹小筑

转载内容仅代表作者观点

不代表中科院物理所立场

如需转载请联系原公众号