Redian新闻
>
素数随想

素数随想

博客

素数随想

(一)随想的前奏

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

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

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

我的本科毕业论文搞得是调和分析(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 < 1495 时都是合数。

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

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

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

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

回到我的高中课堂上。这个题目虽然通式证明非常困难,但当 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 年的奇怪周期?对了,就是素数长周期。

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

大自然真的很神奇。

戳这里 Claim your page
来源: 文学城-枫散仙
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。