素数有无穷多个这一命题简单却魅力无穷, 2300多年间, 许多数学家都给出了数以百计的证明. 但在众多证明中, 英国数学家哈代(G. H. Hardy) 在《一位数学家的辩白》 (A Mathematician's Apology) 一书中称欧几里得的证明历久弥新, 依然如初发现时一样重要, 两千年的时光不曾刻下丝毫褶痕. 如果你想了解更多的证明, 可以阅读参考文献[1].
素数的重要性
要说素数在数论中的重要地位, 一个定理便足以说明, 那就是算术基本定理.
定理1 (算术基本定理)
任何大于1的整数要么本身就是素数, 要么可以写为两个或以上的素数的乘积, 如果将这些素因子按大小排列之后, 写法唯一.
例如:
定理具体的证明如下.
假设存在不能分解成有限个素数的乘积的合数, 根据最小数原理, 其中必有一个最小的数, 设为n. 根据合数的定义, 存在小于的自然数a,b使得n=ab.
如果a,b都是素数, 与假设矛盾.
如果a,b至少有一个是合数, 由于都比n小, 所以这个合数一定可以被分解成有限个素数的乘积, 用乘积替换这个数, 可推出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
尽管如此, 素数本身还是有很多优美的内在规律的.
在寻找素数时, 欧几里得曾提出有少量素数可以写成(其中指数为素数)的形式. 究竟有多少个素数可以写成这种形式？欧几里得把这个问题留给了后人. 于是, 费马、笛卡尔、哥德巴赫、欧拉、高斯……几乎所有大数学家都研究过这种特殊形式的素数, 17世纪的法国数学家马林·梅森是其中成果最为卓著的一位.
另外在寻找素数时还有下面几个著名猜想.
孪生素数猜想：是否存在无穷多个素数p, 使得p+2也是素数？
勒让德猜想：是否在所有连续的平方数之间至少存在一个素数？
未命名猜想：是否有无穷多个素数p, 使得p-1是一个平方数？换句话说：是否有无穷多个形式为
的素数？
在1912年国际数学家大会中, 埃德蒙兰道列出了关于素数的四个基本问题, 就是上述3个猜想外加哥德巴赫猜想. 这些问题在他认为是"在当前的数学认识下无法解决", 后人称之为兰道问题. 到2023年为止, 所有四个问题都未得到解决.
素数的应用
别以为研究素数只是数学家们的消遣和游戏, 事实上素数的研究在当代具有十分丰富的理论意义和实用价值.
比如寻找梅森素数是发现已知最大素数的最有效途径, 它的探究推动了数论的研究, 促进了计算技术、程序设计技术、密码技术、网格技术的发展以及快速傅立叶变换的应用. 另外, 梅森素数的探究方法还可用来测试计算机硬件运算是否正确.
素数理论是RSA加密算法的基石. 两个大素数相乘非常容易, 但将它们的乘积分解回这两个素数则非常困难. 正是基于此不对称性, MIT的三位大咖在1977年发明了RSA算法. RSA是他们三人姓名的首字母. 这是一种公开密钥算法, 这个算法广泛应用于数字通信和网络安全领域, 为信息的加密和解密提供了高度的安全性.
此外, 素数还在随机数生成、哈希函数设计、错误检测和分布式计算等领域发挥重要作用.
参考文献
[1] 卢昌海.素数有无穷多个之九类证明. https://www.changhai.org/articles/science/mathematics/IP.php
来源：数来数趣
编辑：紫竹小筑
转载内容仅代表作者观点
不代表中科院物理所立场返回搜狐，查看更多