素数随想

素数随想

（一）随想的前奏

作为一个数学系学生，我应该算是一个曾经比较热血的，一直喜欢那些关于数论、平面几何等各种与自然界相关联的东西，直到毕业转行了还是如此。

我的中学时代受宣传陈景润的影响，当然也是本色亦然，对数学可以说是热爱，结果就在上大学时选择了这个专业 – 我是被第一志愿录取到数学系的。那时的人们还都比较理想化，就算是有务实的想法，也相信“学好数理化，走遍天下都不怕”那套说教。

上了大学后慢慢发现高级纯理论的数学和自己的想象不太一样，有点脱离自然世界，越来越抽象晦涩。但我比较懒，也比较皮实抗压，挺了过来，懒得去转换专业。

我的本科毕业论文搞得是调和分析（Harmonic Analysis）。那时因为家父病危，需要回家照顾，连这个论文也完全是好友帮忙的结果，很惭愧 – 这位好友现在美国大学做计算机教授，在此再次感谢 – 那可是真哥们儿：我离校回家一个多月，只是临走前告诉他有事就帮我应付一下，因为我不知道要回去多长时间，结果我在论文答辩前两天才回来，此时他在我不知情的情况下已经帮我写好了论文，连标题都是他命的名 – 关于调和函数性质的几点注记。

然后，毕业答辩时有一个精彩的桥段：

在我“复习”了一下那篇毕业论文后，就是看懂那些公式推导，就做了答辩。当我介绍了这种调和函数产生的几个“美丽”的属性之后，一个我不认识的评审老师提问，你能不能举一个具体的调和函数的例子来说明？应该说，这个问题是最基本的了，没有任何刁难之意。不幸的是，我还真的找不出这样一个例子。于是，我红着脸转向我的导师，寻求帮助。

在前排坐着的我的导师也是面露尴尬，转过头去解释说：我们搞理论数学研究的，主要注重形式逻辑推导和公式的美感，希望能够得到像爱因斯坦的质能方程、麦克斯韦电磁方程、欧拉公式等那样漂亮的公式。至于在现实中如何应用，不是我们关注的重点。说实话，这个例子我现在也举不出来。

这时我已经考了他的研究生并被录取了。我开始逐渐体会到，数学不属于真正的自然科学！数学只是纯理抽象，是一种逻辑工具。喜欢联系实际，对纯抽象有点脸盲的我，此时对于纯理数学的热情到此也消磨一空，后来虽然读了数学研究生，但还是又转成工科，离开了纯理抽象的数学天地。但巧合的是，毕业后我还真的做了多年的调和分析的应用，比如傅里叶谱分析、核磁共振信号处理等工作，虽然与理论数学上的调和分析不搭嘎。

这里插一句 – 人生就是这么狗血：在《童年的记忆》里我曾提及，我的小学第一堂课是以无知、无感的被动“作弊”开始的，我没有动一下笔就得到了入学考试的 100 分；而大学毕业又复制了小学入学的魔幻，没有动一下笔，毕业论文就得了 A – 当时考上研究生的同学好像都拿了 A。

我对数学中那些和自然世界贴近的部分还是情有独钟，在毕业工作后有时还会去琢磨一下。其中一大兴趣就是关于素数，也称为质数， prime number。它们像生长于自然数间的杂草，看上去随机分布，但又表现出惊人的规律性，并有规范其行为之法则，且以可证明的精准度遵守着这些法则。

为纪念创刊 125 周年，Science 杂志于 2005 年 7 月提出了 125 个重要的科学问题，其中包含 25 个最突出的重点问题以及其他 100 个生命科学、物理学、数学等领域的难题。

2021年，上海交大协同 Science 在全世界范围内再次征集并发布了新的 125 个问题。其中三个数学问题被列在首位，而第一个问题就是 “是什么让素数如此特别？”。

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

虽然数学在严格意义上不属于自然科学（没有证伪性），而是以形式逻辑为核心的符号语言，但在各种科学问题上数学工具是不可或缺的，而且极为重要。不信，你看看下面的公式，如果出现在某篇文章中，是不是就有让人肃然起敬的高大上的感觉？

– 熟识这个公式的人一定是物理学界的好学生。

声明一下：其实概率统计是可以验证的。所以我个人认为概率统计学属于自然科学范畴。但概率统计是否该归类为纯理数学，就是另一个问题了。

在八十年代，计算机性能还不像现在的水平，对复杂计算的能力有限。当时我接触到伪随机序列生成，就是用一个种子不断乘积后用大素数求模产生的序列。现在还记得一个经典的数对：种子是16807，大素数是2147483647 – 这是一个梅森素数，231-1，第31个梅森数。这对数产生的伪随机序列的“随机性”很好，序列长度为10位数。但理想的随机序列式白噪声，还是达不到的。

素数对应的是合数，也就是说，不是素数的自然数就是合数。对于刚刚接触到初等数学的人来说，素数与合数的关系和奇数与偶数的关系有点类似。但其本质却是有巨大的差异。和多年来的社会阅历融合在一起，我感受到素数及其属性可以映射到人类社会中。

现在我试一试用“关于素数的一点注记”的方式来补上我那“作弊”的大学毕业论文，也以此纪念我那数学系为我辩护的导师 – 他在我毕业后没几年就故去了，还不到50岁，英年早逝，也是癌症。可惜我连一张他的照片都没有，不过他长得很像陈教授：

下面就是我的素数随想。在开始之前，请有兴趣的读者做一个小练习，试证明：在n2和(n+1)2之间，至少有一个素数 – 答案在文后找，不过最好自己先尝试一下。

（二）随想

【素数性质 – 1】素数是自然数中的中坚。如果把自然数看成一个空间，那么素数就是这个空间的支撑框架。任何一个大于1的合数都可以用素数的积来表示。比如，2023 = 7 x 17 x 17。这样，素数就可以用来构成这个自然数世界。这就是我们小学学习的因式分解。

随想 – 这个社会上有一些素数人，就像砼（tóng，混凝土，我从土木系同学那里学习来的字）里的钢筋，支撑起了这个社会大厦。这些人有独立的人格，有自由的思想，不会人云亦云、随波逐流。这个人类社会靠的不是那些唯唯诺诺、见风使舵的人。当社会风起云涌之时，墙头草们都随风而去，只有他们坚韧不折，撑起这片天，是社会的中流砥柱；当社会政通人和，国泰民安之时，他们又是走在时代前列的先行者，引领着时代的潮流。人类社会上的最小思维单位就是那些素数人。

【素数性质 – 2】素数在自然数中的完备的。哥德巴赫猜想（向陈景润致敬）：任何一个大偶数都可以用两个素数的和来表示。虽然这个猜想没有被完全证明，但现在数学界没有人怀疑其正确性。比如，20 = 3 + 17。当然，奇数加 3 就是偶数，所以奇数可以最多用三个素数的和来表示。这样，不超过 3 个素数相加就可以得到所有的自然数。

随想 – 仅靠素数人就可以完成这个世界上的任何人间奇迹，素数人也可以把思想活动伸延到社会各个领域、各个角落，没有死角。如果有什么自然界的难题产生，只要有足够的时间，素数人就可以找出解决问题的方法，不管是小行星要撞地球，还是超级细菌未知病毒侵蚀人类健康。

【素数性质 – 3】素数在自然数中是稀疏的，而且值越大越稀疏。虽然在数值较小时，有不少靠近的素数，但随着数值的增大，素数在自然数中的分布就越来越稀少。比如以100为区间，100以下的素数有2、3、5、7…97等共25个，但1000~1100中就只有16个素数，10000~10100中就只有11个，100000~100100中就只有6个。如果上面的100区间改为1000区间，则上述的类似位置上素数的个数就变成了168、112、87、65、53。这个素数分布原理叫素数定理，用 π(x) 来代表小于x的素数的个数，其初等表达式： π(x) ≈ x / ln(x)，ln是自然对数。比如 π(100) = 22， π(1000) = 145， π(10000) = 1086， π(100000) = 8686，...；而实际上的素数个数对应为 25，168，1229，9592，...。其高级表达式更准确：π(x) = ∫1/ln(t)dt。当年高斯和勒让德都在18世纪末提出了类似的理论，但无法证明。这个问题的证明成为当时数学界的顶尖难题，当时有传言，谁证明了这个问题，就会得到永生。100年后，法国数学家雅克·阿达马和比利时数学家德·拉·瓦莱布桑先后独立给出证明！他们俩果然高寿，分别活到了98岁和96岁。相关联的素数定理推论：对每个正整数 n，从 (n+1)! + 2 至 (n+1)! + n + 1 的 n个连续正整数都是合数(非素数)。

随想 – 我也想长寿，可惜没有这份天赋去证明这个素数定理。社会中素数人不是均匀分布的，而是距你越远的地方素数人越稀少。这就好像是广义相对论中质量（引力）对时空的密度压变，让观察者看到平面的扭曲。素数数量本身就大大少于非素数，那么在你不熟悉的环境下，素数人更是显得少。在这个世界里，庸庸碌碌的人永远是大多数。

【素数性质 – 4】不仅素数是可以无限大的（欧几里得定理），而且孪生素数也是可以无穷大的 – 这就是希尔伯特在1900年提出的孪生素数猜想。孪生素数就是 N 和 N+2 都是素数的情况，比如17和19。虽然素数在自然数中是稀疏的，但不管如何设限，总有更大的孪生素数。北大学子张益唐对此颇有研究，目前他的结果在这个问题的研究上也是最先进的，不过和哥德巴赫猜想一样，也没有完全证明，不过大家都相信证明只是时间问题。

随想 – 道不孤行，不管素数人是如何的少，总会有结伴的素数人，在某个地方、某个领域，做出杰出的贡献。比如杨振宁与李政道，虽然前者在非学术领域让人有些微词。

【素数性质 – 5】素数理论是RSA加密算法的基石。因为对大数做因式分解的算法复杂度与大数相乘或求模的不对称性，两个大素数可以用来产生RSA算法。这样的两个素数的积也被称为半素数，RSA数是一些大的半素数的集合。这种加密算法是MIT的三位大咖在1977年提出的，随用他们三人姓名的首字母命名。这是一种公开密钥算法，在电子商务中被广泛应用。

随想 – 这就是 2021 版 Science 的 125 重要问题 No 1 的描述。到目前为止，分解素数还是没有什么太好办法，除了 brutal force，一些算法可以加速，但还是很慢。这就像在茫茫人海中寻找那个对的你，或是在复杂工程中寻找合适的能工巧匠。素数不像毛遂，无法自荐，荐了也不一定有用。素数人也是如此，能识别素数人的才是高才伯乐。

 

【素数性质 – 6】素数本身是有优美的内在规律的。对整数a，如果p是素数，则 ap-a 是p倍数 – 这就是费尔马小定理，比如 a = 2，p = 31，则 2 的 31 次方减 2 就是 2147483646，是 31 的倍数。

随想 – 发现素数人特征是很 tricky 的。作为律师，费尔马四百年前就发现了这么复杂的素数内在属性，厉害。欧拉和莱布尼兹都在费尔马发现约100 年后给出了证明。我也曾碰巧对此感兴趣 – 那还是在我知道有这个费尔马小定理之前，我也发现了类似的规律，但是是其逆命题，即如果 ap-a 是 p 倍数，则 p 是素数。我当时高兴得想发表论文，可遗憾的是这个发现是错的，而且我不是第一个犯错的人。中国数学前辈李善兰 （1810年—1882年）就曾发现过，并被称为中国猜想：当 a = 2，n = 341 时，中国猜想不成立，因为 341 = 11 x 31。关于这个中国猜想，还有许多神奇的故事，甚至被神话到春秋时代，李约瑟在《中国科学技术史》中也有提及。

素数还有许多性质，在此就不拓展了，大家可以自行脑补：

- 素数和而不同...

- 素数可助韩信点兵...

- 素数除了 2 都是奇数...

- 素数是有棱有角的石头…

- 素数是个性十足的的另类…

- 素数是不随波逐流的非主流…

- 素数是有自我意识的万物代表…

（三）随想的伸延

从其名字上就可以感受到其特性：素数、质数，翻译得真好，反映了其性质，类似几何上的奇点。英文更是有味道，prime，来自拉丁语primus，就是第一位的，初始的。由此派生的名词：

Prime minister – 总理

Prime time – 黄金时间

Primer – 底漆 

欧几里得（公元前 325 ~ 公元前 265）是伟大的古希腊数学家，在思想巨匠亚里斯多德离世前三年出生，和超长待机的秦昭襄王（秦始皇的曾祖父）是同时期的人。就在东方世界上演连横合纵、尔虞我诈之际，他贡献了三维空间的公理化体系结构，故我们现在最基本的三维几何空间被称为欧几里得空间。那时古希腊的哲学、科学、方法论是如此辉煌，看欧几里得的关于 “素数是无穷的” 证明就可见一斑。因为是欧几里得给出了第一个证明，故也称为欧几里得定理（后来欧拉在18世纪也给出过解析的证明，并且推论出素数的出现密度高于自然数的平方数）：

【证明】如果素数是有限的， S{P1,P2,P3…Pn} 是由所有素数所组成的有限集合，令 N = 1 + （P1…Pn）， （P1…Pn）为所有 S 中所有素数的积。如同其他自然数一样，N大于所有素数，必可被至少一个素数整除。但任何可整除 N 的素数都不可能是有限集合 S 内的元素（素数），因为后者除 N 都会余 1。所以，N可被其他不属于 S 的素数所整除。这与前面 S 的定义是矛盾的，所以 S 不是有限的。

前面的练习题“在n2和(n+1)2之间，至少有一个素数”的答案：不好意思，开了一个天大的玩笑 – 这是著名的勒让德猜想，由德国人 Edmund Georg Hermann Landau 在1912年提出，已经有一百多年了，至今无人征服，既无法证明也无法证伪。

我在上高中时曾经也有过类似的笑话。1978年，“科学的春天”刚刚开始，我靠数理竞赛上了我们那里唯一的重点高中。当时分班是按成绩排名，我们年级 7 个理科班，完全按入学考试成绩分，把我们竞赛的前 20 名加上升高中考试的前 30 名拼成一班。可想而知，同学们都是来自各个中学的尖子，牛气得不要不要的，感觉自己离陈景润华罗庚不远了。

高中开学的第一天，报到后也没有什么事，我们这些靠竞赛上去的因为不久前在地区礼堂里颁奖时见过，彼此认识，就嗨了起来：有一位猥琐的高手出了一道题，让这些不知深浅的同学证明：X3 + Y3 = Z3 没有非零整数解。一帮“骄子”们瞬间都静了下来，憋着劲要当第一个证明人。嘿嘿，结果可想而知......

1993 年 6 月，英国人 Andrew John Wiles 发表了他的证明，“解决”了费尔马大定理（也称费尔马最后定理），也就是这个题目的一般形式：“Xn + Yn = Zn 当 n 大于 2 时没有非零整数解”。

Andrew 的证明在数学界极为轰动，这可是公认的三百五十百年来最难啃的骨头。 他独自一人花了 7 年的时间，悄悄地啃了下来，并为此发明了许多新概念和方法。可是，可但是，但可是，他复杂的证明在当时无法马上验证，而几个月后在同行评审中发现了逻辑错误，有致命伤。虽然他发明的数学工具还是有巨大的价值，但此证明还是无法成立 – 数学就是这样黑白分明的逻辑关系。

携 170 的智商，Andrew 再度投入到证明中，和他的学生 Richard Taylor 一起，经过不到一年的奋战，居然再次完整地证明费尔马大定理，并在 1995 年《数学年刊》发表，这是经过同行评审、逻辑验证了的 – 真是神人啊，最终的证明和附带的讨论长达 130 页纸。他后来也因此获得了一系列的数学大奖，包括有数学界诺贝尔之称的菲尔兹奖 – 不过是特别奖，因为他已经超龄了（菲尔兹奖上限是 40 岁）。这个证明被誉为 “20 世纪最辉煌的数学成就”。

法国大律师费尔马搞数学是纯业余爱好。当年他在书的旁空处写下此式，并标注：“我确信我发现一种美妙的证法，可惜这里的空白处太小，写不下（Hanc marginis exiguitas non caperet）”，喜欢恶作剧的费尔马害得数学界努力了几百年也不见效，不知道那个“美妙的证法”是什么。这句话也成为了他的名言。

费尔马不愿意发表他的成果，所以好东西都在手稿里面。他在阅读数学书籍的过程中，习惯地把随想的一些思路写在旁边空白的地方。他还对证明思路讳莫如深，往往只会写出推导得到的定理，而不会保留证明过程。有趣的是，他还在手稿中非常理直气壮地给出理由，为什么没有给出证明过程：比如 “我可以证明这个结论，但现在我必须去喂猫了” 或者是 “我可以证明这一点，但我要去洗头了”。这种恶趣味让几百年以来的数学家对他又爱又恨。

费尔马去世后，其子出版了一本书，里面囊括了他老爹在页边空白处所做的所有笔记。因为都没有证明只有结果，所以留下了一个个极为诱人的挑战，无数数学家只能前赴后继去求证费马潦草笔记的正确性。这些东西在被后人证明之前，只能称为猜想，虽然被费尔马称为定理。

别总瞧不起民科，费尔马就是民科鼻祖。当年在中关村的人常能看到科学院数学所和北大来打擂台的民科，其中就有“证明了”费尔马大定理的，他们多被 “读过什么专业书？” 给打发回去了，不知道有没有误人子弟的。

费尔马这样的大咖，自然不会对素数熟视无睹。他对素数的贡献：

• 费尔马小定理：a^p-a ≡ 0 (mod p)，其中p是一个素数，a是正整数
• 素数可分为 4n+1 和 4n+3 两种形式
• 形如 4n+1 的素数能够、而且只能够以一种方式表为两个平方数之和
• 没有一个形如 4n+3 的素数可以表示为两个平方数之和
• 形如 4n+1 的素数能够且只能够作为一个直角边为整数的直角三角形的斜边；4n+1 的平方是且只能是两个这种直角三角形的斜边；类似地，4n+1 的 m 次方是且只能是 m 个这种直角三角形的斜边
• 形如 4n+1 的素数与它的平方都只能以一种方式表达为两个平方数之和；它的3次和4次方都只能以两种表达为两个平方数之和；5次和6次方都只能以3种方式表达为两个平方数之和，以此类推，直至无穷

欧拉给费尔马擦屁股：

• 1770年，证明了费尔马大定理当 n = 3 时成立，也就是我上高中碰到的第一个恶作剧。其实欧拉做了两种不同的证明，详情见这里。而且其中一个有问题，虽然看上去很手段巧妙 – 天才如欧拉也会犯错误。如果感兴趣关于欧拉的错误，可以看这里。
• 费尔马说他发现形如 Fn = 2^(2^n)+1 的数全是素数，比如 n 为 0~4 时，对应的值是3，5，17，257，65537都是素数。欧拉发现 n=5时，4294967297 = 641x6700417 却是个合数，而后面的直到 n

不知道这费尔马的脑子是怎么长的，业余爱好吊打专业大咖。另一个类似的情况是孟德尔，作为神职人员窥视上帝造物的秘密，把豌豆玩个爆，发现了遗传规律，不知道是否符合教规。达尔文也是差不多，学习医学、神学，最后反叛了教会，用《物种起源》阐明了生物进化原理。

现在还有许多素数相关的猜想没有解决，其中最著名的就是黎曼猜想，其描述比较复杂，是猜想中的皇冠，有兴趣的可以看这里。黎曼猜想与素数定理密切相关，不过，作为数学系的学生，我听到黎曼头就有点大。

还有许多关于素数的猜想，有兴趣的可以去研究，比如：

• 斐波那契素数是无限的
• 梅森素数是无限的
• 费尔马素数是有限的

回到我的高中课堂上。这个题目虽然通式证明非常困难，但当 n 为 3 的时候，并不是通式级别的超级难题，虽然对我们这些自以为是的小白们还是无法触及的。

下面给出欧拉在1770 年时候的证明，他使用了无穷递降法（proof by infinite descent）。术语：coprime – 互素；gcd – 最大公约数（greatest common divisor） 。

慎入！Theorem: Euler's Proof for FLT （Fermat's Last Theorem）: n = 3

x3 + y3 = z3 has integer solutions -> xyz = 0

(1) Let's assume that we have solutions x,y,z to the above equation.

(2) We can assume that x,y,z are coprime. [See here for the proof].

(3) First, we observe that there must exist p,q such that (see here for proof):

(a) gcd(p,q) = 1

(b) p,q have opposite parities (one is odd; one is even)

(c) p,q are positive

(d) 2p*(p2 + 3q2) is a cube

(4) Second, we know that gcd(2p, p2+3q2) is either 1 or 3. (see here for proof).

(5) If gcd(2p, p2+3q2) = 1, then there must be a smaller solution to FLT n=3. (see here for proof).

(6) Likewise, if gcd(2p, p2+3q2) = 3, then there must be a smaller solution to FLT n=3. (see here for proof).

(7) But then there is necessarily a smaller solution and we could use the same argument on this smaller solution to show the existence of an even smaller solution. We have thus shown a condition of infinite descent.

能看明白这个解题思路的，可以去练国际数学奥林匹克了。

我们那时还是一帮生瓜蛋子，哪里有这个本事？记得我用了一个不容易看出错误的简单方法给出了证明，高兴了两分钟，一片欢呼，但很快就被人看出了破绽，原来是个假把式。那个时候竞赛级别的难题很少见，后来出题人说这是费尔马大定理的特殊形式，我们马上就都打蔫了。

十几年后，留美时的一位同学，说到他刚刚上北大时，班上同学都是各地的尖子，不服不忿的，老师就用一道初等数学的平面几何题来震慑大家，说让你们看看什么是难题：

用圆规和直尺在三条平行线上画出一个等边三角形，使得三角形的三个顶点分别落在三条平行线上。

这道题很有趣，你来试试？

（四）随想中的生物

在北美有一种蝉，叫周期蝉，其生命周期是 13 年或 17 年，相应被称为 13 年蝉或 17 年蝉。幼虫孵化后即钻入地下，一生绝大多数时间在地下度过，靠吸食树根的汁液生存。它们在地下生活 13 年或 17 年后，同种蝉的幼虫同时破土而出，在 4~6 周内羽化、交配、产卵、死亡，而卵孵化后进入下一个生命周期。因此某一年份在美国东部一些地方每过 13 或 17 年就会突然出现大量的蝉，成为一种奇景。

为什么会有这个 13 年 或 17 年的奇怪周期？对了，就是素数长周期。

在这样长的素数周期年里，一般不会连续碰到天敌和自然灾害也与这个周期同步，从而避免被灭族。不同的周期蝉种群出地的年份不同，使这个大家族的基因继承就更安全了。

大自然真的很神奇。