素数为何特殊（数论之巅5个关于素数的）

数学中研究最多的领域之一是素数的研究。素数领域存在很多非常困难的问题，即使是最伟大的数学家也没有解决。今天，我们来看看数学中关于素数的5个最古老的问题，这些问题理解起来很容易，但却没有得到证实。

完美数（完全数、完备数）：奇数完全数是否存在？偶数 完全数是无限的吗？

看一下6、28、496、8128这些数字.....

这些数字有什么特别之处？我建议你试着寻找一个关于数字的美丽的基本性质。

如果你看一下这些数的真因数，你可能会注意到这个“美丽”的性质。

• 6 = 1 2 3,
• 28 = 1 2 4 7 14,
• 496 = 1 2 4 8 16 31 62 124 248
• 8128 = 1 2 4 8 16 32 64 127 254 508 1016 2032 4064

真因数之和等于数字本身的数字被称为完全数。最早的关于完全数的研究已经消失在历史潮流中。然而，我们知道毕达哥拉斯人（公元前525年）曾研究过完全数。

我们对这些数字了解多少呢？

欧几里德证明，对于一个给定的n，如果（2^n-1）是一个素数，那么

是一个完全数。

再做些铺垫。

梅森素数：梅森猜想，当n为素数时，所有形式为2^n-1的数都是素数。

我们知道这不是真的。例如，2^11-1 = 2047 = 23 × 89

开放性问题：是否有无限多的梅森素数？目前我们知道47个梅森素数。

• 欧拉在18世纪提出，任何偶数完全素数的形式都是2^(n-1)(2^n-1)。换句话说，偶数完全数和梅森素数之间有一个一一对应的关系。

正如你所看到的，自从欧几里德（约公元前300年）以来，我们就知道偶数完全数以及得到它们的方法。我们不知道的是，是否存在任何奇数完全数？（实际上，对奇数完全数的研究很少，在这个问题上几乎没有任何进展。

总而言之，完全数的研究提出了两个长期未决的问题，即 "奇数完全数的存在 "和 "无限多梅森素数的存在"。

• 欧几里德（约公元前300年）首次证明了无限多素数的存在。

孪生素数猜想：有无限多的孪生素数

孪生素数是指一对(p, p 2)，使得p和p 2都是素数。

孪生素数猜想的确切来源没有得到证实，孪生素数猜想的第一个陈述是由法国数学家Alphonse de Polignac在1846年给出的。然而，希腊数学家欧几里德给出了已知的最古老的证明，即存在无限多的素数，他猜想存在无限多的孪生素数。

2000多年了，这个问题的证明几乎没有进展。

我们对孪生素数掌握了哪些？

1. 有无限多的(p, p k)形式的素数对，其中k≤246。
2. 假设艾略特-哈伯斯塔姆猜想（ Elliott-Halberstam conjecture）成立，那么有无限多的形式为(p, p k)的素数对，其中k≤6。这意味着，孪生素数（差值为2）、表亲素数（差值为4）和性感素数（差值为6）的集合是无限的。

小插曲：为什么把差值为6的一对素数称为性感素数？因为6在拉丁文中的拼写是“sex”，英文的意思是性感。

最伟大的在世数学家陶哲轩正在积极研究这个问题。

哪些正多边形是可构成的？

正多边形是可构成的是指可以用圆规和直尺构成。例如，正五边形可以用圆规和直尺构成，而正七边形则不能。

可构成[的]（constructible）是1993年公布的数学名词——百科

古希腊人知道如何构成边数为n=3,4,5的正多边形，他们也知道如何构成边数为给定正多边形两倍的正多边形。

所以他们可以构成正多边形，其中边数为n={6,12,24...4,8,16... 5,10,20...}，以此类推。

自然要问的问题是，什么样的n值是可构成的？

从希腊人第一次研究这个问题到1796年一个19岁的少年构成了一个正17边形，这个问题的真正进展花了近2000年。这个孩子不是别人，正是卡尔-弗里德里希-高斯。几年后，高斯想出了这个一般问题的答案。

我们所知道的可构成的正多边形：

高斯研究指出，当且仅当n是2的幂和任何费马素数的乘积时，就可以用圆规和直尺构成一个规则的正多边形。

费马素数的形式是：

因此，寻找所有可构成的多边形的问题可简化为寻找所有费马素数。这是个独立的开放性问题。

最前面的几个费马数（不是费马素数）是3, 5, 17, 257, 65537, 4294967297........截至2021年，已知的费马素数只有F0=3、F1=5、F2=17、F3=257和F4=65537。

费马猜想，所有的费马数都是素数。1732年，欧拉发现F5（4294967297）不是素数，它有因数641。从那时起，我们已经证明，n=5,6...31的费马数是合数。在F4之后没有已知的费马素数。

当我们能够找到关于费马素数存在性的答案的那一天，我们就会得到所有可构成的正多边形。

哥德巴赫猜想。(1742)

每个偶数都可以表示为两个素数之和。

哥德巴赫弱猜想：

每个大于5的奇数都可以表示为三个素数之和。

这个猜想被称为 "弱猜想"，因为如果强猜想被证明，那么这个猜想也会是真的。不幸的是，自欧拉以来，经过几代数学家的努力，我们也没能证明这两个猜想。

注：2013年，哈拉尔德-赫夫考特（ Harald Helfgott ）发表了哥德巴赫弱猜想的证明。截至2018年，该证明在数学界被广泛接受，但还没有在同行评议的期刊上发表。

我们所知道的哥德巴赫猜想

1. 1930年，有人证明，任何大于1的自然数都可以写成不超过C的素数之和，其中C<800000。（哥德巴赫猜想中c=2）
2. 在过去的十年中，每个偶数n≥4实际上是不超过4个素数(即C≤6)的和。后来，这一结果被加强到C≤4。

有趣的是，哥德巴赫猜想是2007年西班牙电影《费马的房间》中的部分情节。

素数在P中（2004）

免责声明：文章的标题有误导性。在展示了4个未解决的结果后，我想展示一个长期存在的数学问题（第5个问题），这个问题最近（2004年）已经被解决了。

假设给你一个数字n=10089886811898868001。

有人问你，这个数字是否是质数。你的直觉是这样的。

算法A：检查每个数字1<k<n，k能被n整除。如果n不是素数，那么n将有一个因子k，使得k≤根号n，这个嗅觉用于优化算法。

算法B： 所以我们只检查1 <k ≤ √n。

首先，什么是'P'？

如果存在一种 "快速 "算法，可以解决决策问题（返回 "是 "或 "否"），那么就可以说一个决策问题在 "P "中。

这里，决策问题是，给定n，n是素数吗？

那什么是快速算法？

• 对于任何给定的决策问题，你将有一个输入大小（让我们称之为x）。
• 对于这问题，输入大小是数字n的位数。
• 因此，对于上述n，x=20。
• 一般来说，对于一个给定的n，x=log(n)

如果一个算法能在f(x)步内解决决策问题，其中f是一个多项式函数，则该算法被称为快速算法（多项式时间算法）。

如果我们看一下上面的算法，找出n是否是素数，我们就会发现我们在算法A中用了n步，在算法B中用了√n步。

由于我们的输入大小是log(n)。

让我们把一个给定输入大小x的算法的步骤数称为γ(x)

• 对于算法A：

• 对于算法B：

这两个都是以x为单位的指数时间算法，400多年来，数学家们一直试图弄清楚素数的决策问题是否可以用多项式时间来计算。事实证明，答案是 "是的"。2004年，当一位教授宣布这一结果时，这一消息在数学界（特别是数论界）快速传播。

该算法（著名的AKS素数测试）被发表在一篇名为 "Primes Is In P "的论文中，它表明这个决策问题（n是否为素数），可以在log(n)^12步内解决。

​