是什么让素数如此特别？

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

ysr

1，哥德巴赫猜想是远远成立的。
2，孪生素数对有无穷多，这就是孪生素数猜想。
3，在n^2与(n+1)^2之间(其中n大于等于1)至少有一个素数，且随着整数的增大，该区间内的素数个数是波动式增长的。
     这三个问题在我的《数论探秘》中都有严格的证明。
4，李明波的孪中差和孪中和猜想是成立的，猜想内容和证明也收集在我的《数论探秘》中了。
       到时候我的《数论探秘》将陆续在京东，淘宝，拼多多，亚马逊等平台上架，目前可以在淘宝上搜索“筑书文化”进入这个店铺，就可以看到我的《数论探秘》了。
     国内首发定价28元/本，欢迎惠顾结缘！

ysr

     猜想得到了证明就是客观规律和铁的事实，明白了这些规律，就可以有助于搞出高概率的素数公式，快速得到有密码特征的大素数，巨大的孪生素数，甚至用来破解世界纪录。
得到了有密码特征的大素数，可以使得RSA加密技术更加方便安全和强大。

ysr

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

其实就是说4n^2+1型的素数是否有无穷多，我可以肯定的回答，这是无穷多的，如5，17，37，101，197，257，401，……等，都是。证明是容易的，看了我的《数论探秘》中关于4X+1型的素数的分布规律，以及书中第一章第三节《抛物线数列中的孪生素数对和相邻素数对的差的定理》中对n^2+n+101中含有无穷素数的证明，您自己就可以证明的。

王守恩

ysr 发表于 2024-7-28 10:22
未命名猜想：是否有无穷多个素数 p ，使得 p - 1 是一个平方数？换句话说：是否有无穷多个形式为 n^2 + 1  ...

{2, 5, 17, 37, 101, 197, 257, 401, 577, 677, 1297, 1601, 2917, 3137, 4357, 5477, 7057, 8101, 8837, 12101, 13457, 14401, 15377, 15877, 16901, 17957, 21317, 22501, 24337, 25601, 28901, 30977, 32401, 33857,
41617, 42437, 44101, 50177, 52901, 55697, 57601, 62501, 65537, 67601, 69697, 72901, 78401, 80657, 90001, 93637, 98597, 106277, 115601, 122501, 147457, 148997, 156817, 160001, 164837, 176401, 184901,
190097, 193601, 197137, 215297, 217157, 220901, 224677, 240101, 246017, 287297, 295937, 309137, 324901, 331777, 341057, 352837, 401957, 404497, 414737, 417317, 427717, 454277, 462401, 470597, 476101}

1. Select[Table[n^2 + 1, {n, 800}], PrimeQ]

复制代码

ysr

40001内有s=33个：
5
17
37
101
197
257
401
577
677
1297
1601
2917
3137
4357
5477
7057
8101
8837
12101
13457
14401
15377
15877
16901
17957
21317
22501
24337
25601
28901
30977
32401
33857

ysr

这样素数还容易构成孪生素数对（其中能找到巨大的孪生素数的概率高）：
48401内有s=10对：
5   7
17   19
101   103
197   199
5477   5479
8837   8839
16901   16903
17957   17959
21317   21319
25601   25603

ysr

另一个高概率公式结果：25108406941546723055343157789013654956726327616418502854959内有s=1对：
25108406941546723055343157789013654956726327616418502011551   25108406941546723055343157789013654956726327616418502011553

ysr

哥德巴赫猜想并不难，有多种初等证明方法可以证明，哥德巴赫猜想是远远成立的。
1，由差定理（更容易证明）证明和定理（就是哥德巴赫猜想）成立。
2，设偶数2A的方根为M则其方根M内的素数的个数的下限是m=M/lnM，则偶数2A的哥德巴赫猜想解的个数的绝对下限就是m-1，这是对无穷大的偶数都成立的，随着偶数的增大实际解的个数远远大于m-1 ， 所以，哥德巴赫猜想远远成立。
3，据构成哥德巴赫猜想解的素数与偶数的方根的大小，把解分为两类：小根拆和大根拆，大于4的偶数，仅仅有73个偶数只有大根拆而不含有小根拆，其他的都是既有小根拆也有大根拆，而4=2+2.

所以，哥德巴赫猜想远远成立，容易证明，仅仅初等数学就可以证明，中学以上的学历都i可以完全解决。

至今不能和解决的原因仅仅有两个：一是数学家喜欢本末倒置从解析数论下手解决问题，二是中国数学界到处是汉奸破环了中国数学界的学术氛围！！

ysr

3712026882238267536501932433308085611826288915638251449549181667内有s=1个：
3712026882238267536501932433308085611826288915638251449548881367   3712026882238267536501932433308085611826288915638251449548881369  n1= 1606938044258990275541962092341162602522202993782792835302546
数大的话很稀少，这是在300项内找到的64位的孪生素数