素数是什么意思,素数的定义

 生活杂谈     |      2020-03-23 15:20
之前有读者希望无穷集聊聊素数。好,就从有趣的大素数开始吧。
素数277232917-1=467333183……97621790,中间省略了23249409位数。这种形如“幂-1”的素数为梅森素数。为行文整齐,将此处指数记作p,此素数记作p=77232917,下文记法同此。它在去年12月26日由民间组织Great Internet Mersenne Prime Search(GIMPS)发现,是迄今为止已知最大的素数。
若在无穷集中将它完整列出,以37位数/行×20行/屏=740位数/屏计(条件为iPhone 6上系统与应用字号设为最小,下同),需要约31418屏。另经测试,以单手全力划动,每翻过100行数需要划动屏幕约3次。如此算来,如果读者想越过该素数继续阅读,需要划动屏幕约18850次。进一步,假设你每秒能完成2次全力划动并一直保持该频率,那么完成这一任务需要约2小时37分。即使考虑生理疲劳与心理崩溃,一上午也是能翻过去的,听起来可以接受。
无穷集不准备列出该数。如果读者有兴趣阅读它,可以参考今年年初日本虹色社出版的《2017年最大の素数》,全书用719页将其完整列出。据说这一奇葩的素数周边销量相当可观。无穷集考虑将它作为礼物送给读者,当日记本用想来不错。另去[1]也可下载.txt文件阅读该数。

素数是什么意思
日本虹色社出版的《2017年最大の素数》。全书16开本,每个数字只有1.2mm×0.8mm大,页边距5mm,紧凑得不可思议。
为什么要找这么大的素数?可能原始动机是为了摸清素数分布的规律吧。关于这个规律下文还要多说两句,现且不表。不过我觉得即使是单纯为了好玩,也说得过去。而历史上首次用电子计算机尝试寻找大素数的动机,是测试计算机性能并吸引公众目光,传奇数学家图灵也参与其中。先提一句,手动发现的最大素数是p=127,由?.卢卡斯在1876年完成。
1949年夏天,图灵等人开始在人类首台可存储程序的数字计算机曼彻斯特马克一号上寻找梅森素数。他们从p=128一直搜索到p=433仍没有任何发现,便放弃了。实际上,下一个梅森素数是p=521,1952年初由R.M.罗宾逊发现。从p=127到相邻的p=521,发现这一个梅森素数花了数学家76年时间。而从p=521到今天的p=77232917,发现其间37个梅森素数只花了数学家(计算机)65年时间。机器可畏!
机器虽然可畏,但人类似乎并不真的在乎它们。从“梅森素数”的维基百科词条中可以发现两条有意思的注释:2009年4月12日,一台计算机证明p=42643801是梅森素数,但这一结果直到6月4日才被人注意。无独有偶,2015年9月17日,又有一台计算机证明p=74207281是梅森素数,但直到转年1月7日才被人注意。而官方记录的发现日期都以人的发现为标准。究竟谁才是发现梅森素数的主体?是亲力亲为算到它的计算机?还是使得计算机亲力亲为算到它的人类数学家?
图灵之后,寻找大素数以测试计算机性能并发现bug的做法一直延续至今。刚才提到的GIMPS便以大素数为基础为芯片公司提供CPU测试方案。2016年初,Intel六代Skylake处理器发布半年之后栽在了大素数手上。当数学家在搭载Core i7-6700K CPU的计算机上执行GIMPS Prime95程序寻找大素数时发现计算机宕机,随后Intel确认了这一bug。此外许多极客也用Prime95“烤机”,其乐无穷。虽然这方面测试还有许多可商榷的地方,但无人能否认大素数计算的复杂性。
最后介绍一个与大素数相关的严肃问题:是否存在最大的梅森素数?素数显然是无穷多的,但目前还无法证明存在无穷多个梅森素数。如果梅森素数的个数是有限的,并且有一天人们真的拿到了这个数,我想那时出版的《最大の梅森素数》一定更畅销,但愿它不要太厚以方便阅读。其实读者也可为发现更大的梅森素数出一份力。访问[2],下载他们的程序,允许你的计算机在空闲时间出让计算资源。如果你的贡献很可观,还会获得不菲的报酬。
周期蝉分布于北美洲。其幼虫孵化随即钻入地下,准确蛰伏13年或17年。时间一到,周期蝉集体同时破土而出,迅速交配、产卵、死亡,完成生命周期。这种蝉之所以选择13或17这两个素数,学术界莫衷一是。素数具有最少的因数是一个线索,但未必能将人们引向最终的答案。
细心的读者会发现,无穷集尚未给出素数的定义。那就告别大素数问题,回到一般的讨论上来。有的读者还需要一份关于素数的历史。好。我们就这两部分继续聊。
素数无非是一些简单纯粹的自然数。用“单纯”一词刚好能概括这一说法。
人们为了掌握最单纯的那一部分自然数,可以预先指明什么是“单纯”。而当人们作出诸如此类的指明时,最终依赖的似乎还是自己的本能。或者说依赖某种浑然天成的外物,人类的本能本能地趋向这个外物。
所谓单纯就是不能以某种形式分解的性质。于是不难理解,现在被称作素数的自然数,大概是那些不能分解成比它们各自更小的自然数的乘积的数。乘积中“1×原数本身”这种分解过于平凡,不予考虑。最终便得到素数的定义:除了1和它本身不再具有其他因数的大于1的自然数(将1当作素数会带来不必要的麻烦,所以人们定义1不是素数,详见[3]。实际上自然数可以分为三类:一、素数;二、非素数;三、1)。
读者不妨思考:素数是自由的么?就是说,素数是某些自然数自顾自地选择成为的么?还是听从于某些外部框架而不得不成为素数?由上述解释似乎可知,自然数集上的普通乘法充当了这个框架,于是素数是普通乘法的产物。这里有没有值得反驳的地方?再问:普通乘法是自由的么?并按此追问至无穷。另可问:外部框架是客观物?还是人的主观物?存在不同于人类主观的主观物么?继续再问:客观物与主观物是否可能是一物的两面?这是否意味着人类或者其他生物的本能是一外物,需像外部函数被调用?人类或其他生物是它的傀儡么?它这一物究竟是什么?是柏拉图的“理念”么?
我们离开这些困难问题。
而阐述素数的重要性是相对容易的。这是因为“重要性”这件事不太重要,它并不是什么稀缺的资源。有余力的读者可以试证:除重要性外,任何可论及对象都具有重要性。从上文大素数的讨论推断,素数的重要性主要体现在它的娱乐功能上:可以用来摧毁手机以及家用计算机。
不过为了保持严肃,这里还是试作他说。可以将算术基本定理作为素数重要性的证据,它陈述了这样一个事实:任何一个大于1的整数n都可以分解成若干素数(素因子)的乘积。并且若不计各个素数的顺序,这种分解是唯一的。这一还原论色彩的事实要求素数必须在数学中扮演“最小不可分单位”的角色。根据此观点,可以把素数p=77232917与第118号元素(原子)Og联系起来,即每个时代所发现的最大素数,对应于每个时代所发现(合成)的最重元素。
除此之外,素数的性质还有更现实的重要性,上世纪70年代涌现的RSA加密算法便是其中之一。由定理可知任何正整数都可唯一分解为若干素数的乘积,但对于充分大的正整数N,这种分解异常困难。而RSA密钥之所以安全就在于这种困难。当然,这里的N至少应为512位才能发挥保密的效果,实际上,位数的推荐值为2048以上。分解一个小整数对于计算机还是相当容易的。我的手机号码是一11位偶数,计算机对它作素因子分解需要的时间小于0.01秒。读者可去[4]尝试。
图中大齿轮有21齿,小齿轮有13齿。相邻的齿轮齿数设计成素数,可以减少两齿轮内两个相同的齿相遇啮合的机会,从而延长其工作寿命。素数在看似与其无关的场合反复出现,使人联想起高斯分布的普遍性。
一般意义上的素数就聊到这里。接下来我们聊聊素数的历史。如果我没记错的话,爱因斯坦曾说一个学科就是这个学科的历史。在我看来这是一种非常马克思化的框架,但如今做研究已经离不开它了。对此我不以为然,却也身不由已。
但历史本身无罪,往往还很有趣。素数的历史也是这样。我们仅选择几个片段聊。如果全力追溯素数的源头,结果首先令人沮丧,因为人类对于素数关注过早,以至于还不能留下有明确意义的史料。但随后令人兴奋,因为意义明确或意味着没意思,或意味着看不懂。
伊尚戈骨是由狒狒腓骨磨制的骨器,其可追溯至距今2万年的旧石器时代晚期。比利时考古学家de Braucourt在1960年探索中非刚果与乌干达交界处时发现了它。现藏于比利时皇家自然科学研究所。
首先关注伊尚戈骨(Ishango bone),它经常与地球文明的数学起源联系起来。上方一根腓骨与本次主题更紧密。由示意图中的Row(b)可知,骨上从左至右依次刻有代表素数11、13、17、19的计数标志,但这并不表明2万年前的人类已经对素数有初步认识。也许它更适合作为晚期智人掌握加法概念的证据,可以看到,Row(b)与Row(c)两行中的数字加起来均等于60。另外一种说法也非常刺眼:所谓“计数标志”仅仅是为了增加摩擦力。
在伊尚戈骨之后,我们介绍一份古老优雅的证明。数学史认为,人类第一次在充分高的高度上理解素数是在公元前300年前后,其标志性的事件是欧几里得在《原本》(Elements)中证明素数有无穷多个。这个证明如下:
1.写下几个已知素数;
2.把它们乘起来加1的结果记作q;
3.找到q的一个素因子。
由算术基本定理可知q总存在素因子,因此步骤3.总是可操作的;由于q是连乘后加1得到,所以q不具有步骤1.中写下的素数。这样,无论在步骤1.写下多少个素数,总可以在步骤3.中找到额外的素数,于是素数是无穷多的。
再往后我能想到的是哥德巴赫猜想,作家徐迟在1978年的一篇报告文学让这个猜想与它的追逐者陈景润火遍大江南北,同时“启蒙”了一批又一批“民科”、“民数”前赴后继投入战斗。猜想陈述道:任何一个大于2的偶数都可以表示为2个素数之和。俗称的“1+1”便指“1个素数+1个素数”。而陈景润证明的结果,也是目前该猜想最好的结果“1+2”,是指“任何一个大于2的偶数都可以表示为1个素数加1个自然数,这个自然数是2个素数之积”,即“1个素数+2个素数之积”。更严格与普遍的表述见[注释5]。
哥德巴赫猜想是1742年哥德巴赫在写给欧拉的一封信中提到的。再往后时间来到1859年,这一年诞生了震古烁今的黎曼猜想。以此猜想为起点,黎曼定义了他的素数计数函数,可以精确估计小于给定值素数的个数(高斯在这方面也做出了卓越贡献)。本来希望好好与读者聊聊素数分布与黎曼猜想,但市面上有非常优秀的科普读物,不容我班门弄斧。J.德比希尔著的《素数之恋》堪称这一领域的绝顶好书,好到无穷集曾经将它作为礼物送给读者。据消息灵通人士透露,收到该书的读者到现在只读了20页,令人震惊,特提出批评。卢昌海著《黎曼猜想》也值得推荐。
素数分布是数论研究中的主线之一。乌拉姆螺旋(Ulam spiral)提供了一个直观感受素数分布的机会。如左上图形式将自然数按螺旋顺序表出即得到乌拉姆螺旋。右上图标出了相应位置上的素数。下面两图是规模为200×200的乌拉姆螺旋。左下图中黑点表示随机选取的奇数,白点表示其他数;右下图中黑点表示素数,白点表示非素数。可以看出素数的分布在这种形式下呈现鲜明的对角线模式。
20世纪中叶素数进入了计算时代。前文提到的图灵、GIMPS、RSA等都可以作为这一时期的大事件。事实上图灵在数论上的另一项工作就是用计算机证伪黎曼猜想,详见[6]。显然,图灵的工作,连同迄今为止所有这方面尝试都没有动摇黎曼猜想,它依然保持开放。
然而更深远的意义在于,以图灵工作为首的这种尝试,即计算机,或者更广义地说,机器的介入,使得数论研究、数学研究,乃至全部人类理性研究进入了尴尬境地。黎曼猜想还好,像梅森素数无穷多这样的命题,今人手中除了数值实验,实在不比2300年前的欧几里得拥有更多的武器。作为一个把人类的智性看得很重的人,我有点不自在。但仔细想想,究竟是智性重要,还是人类重要?其实还是前者重要。所以我也欢迎机器 ,因为我不排除它们拥有更优秀智性的可能。至少,机器的介入使我这样的业余选手也能参与到数学的发现中去。
当然,有些读者对此可能持完全积极乐观的态度,认为机器代表了某种新希望等等。我倒也不很反对。不过如果把目前的机器时代比作人类的二次启蒙的话,我由衷呼唤一位新的康德,为彼此划下界限。
就聊到这里。欢迎读者就任何问题发表看法与意见。
相关注释、链接与文献:
[1]http://www.mersenne.org/primes/digits/M77232917.zip.
[2]www.mersenne.org.
[3]http://www.numberphile.com/videos/1notprime.html.
[4]https://www.calculatorsoup.com/calculators/math/prime-factors.php.
[5]该领域中“a+b”问题:是否能把偶数e表成一个素因子不超过a个的整数与素因子不超过b个的整数之和。
[6]S.巴里·库珀, 安德鲁·霍奇斯等. 永恒的图灵(The once and future Turing)[M]. 堵丁柱, 高晓沨等 译. 计算机科学丛书, 机械工业出版社, 2018. pp.47-56.