首页 百科知识 整数之间的整除关系

整数之间的整除关系

时间:2022-08-23 百科知识 版权反馈
【摘要】:大的数与小的数相减不会遇到什么问题。但是,小的数与大的数相减就麻烦了。比如 11÷4,结果不能用自然数、0 或者负数表示结果。如果给定的整数是 a,我们就把与 a 的倒数表示成 a 1 。引入余数和引入分数造就了不同的数学路线。有了整除和因子,我们就可以回顾「质数」的概念了。例如,1 和 7 是正整数 7 仅有的正因子,因此 7 是质数。正整数 9 拥有 3 个正因子 1、3、9,因此 9 是合数。

最开始的内容总是最轻松的内容,那我们干脆来个最轻松的。我们一口气回到上古时代,回顾一下数字的发展历史吧!人类为什么会引入数字呢?其实本质上就是为了运算。人类每多理解一个运算,就会对应地多了一些符号和一些数字。

最早出现的数字是「自然数」。自然数之所以叫自然数,是因为很早以前我们就会数数了。小孩子自然就知道有 1 个苹果、2 个香蕉。去掉苹果和香蕉,剩下的 1 和 2 就是最早的数学

有了自然数,人类就可以愉快地做「加法」了。1 个苹果加上 1 个苹果等于 2 个苹果(1+1=2),3 个香蕉加上 5 个香蕉等于 8 个香蕉(3+5=8),加法的引入非常轻松。

有了加法,自然而然也就有了「减法」。大的数与小的数相减不会遇到什么问题。我有 3 个苹果,给了你 1 个苹果,我还有 2 个苹果(3−1=2)。但是,小的数与大的数相减就麻烦了。昨天我有 3 个苹果,今天我还有 3 个苹果,苹果数量没有变化。没有变化用什么数字表示呢?为此,人类引入了 0 的概念。更严重的问题是,昨天我有 3 个苹果,今天我只有 2 个苹果,苹果数量少了 1 个。少了 1 个用什么数字表示呢?为此,人类引入了「负数」的概念。人类规定,小于 0 的数是「负数」,大于 0 的数则为「正数」。这样,我们就可以解决少了 1 个的表示问题,顺利执行减法运算了(2−3=−1)。有了自然数、0、负数、加法和减法,人类已经基本解决了计数问题。

为什么负数这么好用呢?我们实际上也可以这么理解负数:负数是与某个正数相加后结果为 0 的数。如果给定的整数是 a,我们就把与 a 相加等于 0 的数表示成−a。这样一来,2−3 就可以写成 2+(−3)了。只要定义了负数,我们就可以把减法也用加法来表示。后面我们会使用这个概念来理解负数和减法。

再往后,人类发现加法和减法还是不够:古代战争时士兵总站成方阵的形式,5 行7 列什么的。此时,用什么方法可以快速得到方阵中的士兵总人数呢?为了解决这个问题,人类引入了「乘法」的概念。通过乘法运算,我们很快就能知道 5 行 7 列一共有 35 个士兵(5×7=35)。有了乘法,自然就出现了「除法」:一共有 35 个士兵,站成 7 列,应该有多少行呢?运用除法,我们可以快速得到应该有 5 行(35÷7=5)。

为什么分数这么好用呢?我们把分数分开看:分数包含「分子」和「分母」。和减法与负数的概念类似,我们可以把分数看成分子和分母的「倒数」相乘的形式:=11×我们把倒数理解成:与某个整数相乘结果等于 1 的数。如果给定的整数是 a,我们就把与 a 的倒数表示成 a −1 。例如,由于 4× =1,我们可以把 写为 4−1,这样, 就写为 11× =11× 4−1。只要定义倒数,我们就可以把除法也用乘法来表示。后面我们会使用这个概念来理解倒数和除法。

至此,人类已经愉快地定义了自然数、0、负数、分数等最为基本的概念,以及加法、减法、乘法、除法等最为基本的运算。直到「第一次数学危机」之前,人类的数学一直和平有序。而我们要讨论的运算也就到此为止。我们甚至都不会涉及到分数,仅考虑整数的问题。

引入余数和引入分数造就了不同的数学路线。在小学时,我们走向了引入分数的路线。引入分数的结果是在初中引入了「无理数」,在大学引入了「实数」,最终走到了「高等数学」领域。于是,人们想起了被数学支配的恐惧。那么另一条路线怎么样呢?我们这次就走一走另一条路线,看看会发生什么。

回到除法运算上面。如果整数 b 除以整数 a 后还能得到一个整数 c,我们就称 a「整除」b,且称 a 是 b 的一个「因子」,b 是 a 的「倍数」。例如,12÷3=4 是整数,我们称 3 整除 12,3 是 12 的因子,12 是 3 的倍数。

有了整除和因子,我们就可以回顾「质数」的概念了。大于 1 的每一个正整数都至少能被两个整数整除,因为它们都可以被 1 和它自己整除。如果一个正整数只能被 1 和它自己整除,即一个正整数只有 1 和它自己两个正因子,我们就称这个整数为质数(或为素数);否则,我们称这个整数为「合数」。例如,1 和 7 是正整数 7 仅有的正因子,因此 7 是质数。正整数 9 拥有 3 个正因子 1、3、9,因此 9 是合数。

有了质数和合数的概念,我们惊讶地发现竟然可以讲解数学历史上最为著名的一个猜想:「哥德巴赫猜想」[8]了。

1742 年 6 月 7 日,普鲁士数学家哥德巴赫(Christian Goldbach)给瑞士数学家欧拉(Leonhard Euler)写了一封信,在信中提出了以下的猜想[9]:

任意一个大于 5 的整数都可以写成三个质数的和。

三周后,欧拉在 6 月 30 日向哥德巴赫撰写回信,并在回信中注明此猜想有另一个等价论述:

任意一个大于 2 的偶数都可以写成两个质数的和。

欧拉在回信中同时指出[10]:

然而,任意数字都可以由两个质数组成,我非常确信这是一个定理,尽管我无法证明。(i)

现今我们了解到的哥德巴赫猜想论述为欧拉给出的版本,亦成为「强哥德巴赫猜想」。从强哥德巴赫猜想还可以推出一个稍弱的假设:

任意一个大于 5 的奇数都可以写成三个质数的和。

这一论述称为「弱哥德巴赫猜想」。已经证明,如果强哥德巴赫猜想是正确的,那么弱哥德巴赫猜想一定也是正确的[11]。

图 1:哥德巴赫信件手稿影音本第 127 页描述了哥德巴赫猜想

哥德巴赫猜想的论述如此简单,几乎每一个学习过一点数学的朋友都可以理解猜想的内容。然而,哥德巴赫猜想的证明却又如此的困难。至今为止,强哥德巴赫猜想依然没有得到证明,也没有找到反例;弱哥德巴赫猜想的证明取得了突破进展,2013 年,弱哥德巴赫猜想基本得到了完全证明[12]。

实际上,从 1742 年哥德巴赫正式提出了这个猜想,到 1920 年代之前,哥德巴赫猜想的证明没有取得任何实质性的进展。1900 年,德国数学家希尔伯特(David Hilbert)在巴黎举行的第二届国际数学家大会上作了题为《数学问题》的演讲,并提出了 23 道最为重要的数学问题[13]。其中,第八个问题就包括了哥德巴赫猜想和与它相似的「孪生质数猜想」(稍后我们就会见到孪生质数猜想了)。实际上,至今除了包括哥德巴赫猜想在内的 4 个问题外,其它的 19 个问题都得到了解决或者部分解决。

十九世纪至二十世纪初,欧洲数学家们在「数论」与「函数论」方面取得了辉煌成就,为哥德巴赫猜想的突破提供了坚实的数学基础。

数学研究的一般都不是一蹴而就的,而是由易到难,先证明一个简单,甚至条件有点苛刻的结果。然后,通过优化证明中使用的技巧,或者加入新的技巧,从而逐渐接近最终的目标。哥德巴赫猜想的研究就是如此。1920 年左右,英国数学家哈代(Godfrey Harold Hardy)和利特尓伍德(John Edensor Littlewood)极大地发展了解析数论,建立起「圆法」工具,并用圆法证明了:如果「广义黎曼猜想」(Generalized Riemann Hypothesis)成立,则每个充分大的奇数都能表示为三个质数的和;「几乎」每一个充分大的偶数都能表示成两个质数的和。注意这里的「几乎」和「充分大」,哈代和利特尓伍德依赖了另一个猜想,经过了艰苦的努力,也还没证明出「每一个」。但他们的工作对哥德巴赫猜想的证明做出了巨大的贡献。1997 年,法国数学家 Deshouillers 及其合作者 Effinger、Te Riele 和 Zinoviev 证明,在广义黎曼假设猜想成立的前提下,弱哥德巴赫猜想是完全成立的[14]。Kaniecki 证明,在广义黎曼假设猜想成立的前提下,奇数都可以表示为最多五个质数的和[15]。2012 年,华人数学家陶哲轩在无需广义黎曼假设猜想的情形下证明了这一结论[16]。

序号

问题名称

进展

01

连续统假设

部分解决

02

算术公理之相容性

已解决

03

两四面体有相同体积之证明法

已解决

04

建立所有度量空间使得所有线段为测地线

论述晦涩,无法解决

05

所有连续群是否皆为可微群

已解决

06

公理化物理

非数学问题

07

若 b 是无理数、a 是非 0、1 代数数,

那么 ab 是否超越数

已解决

08

黎曼猜想、哥德巴赫猜想、孪生素数猜想

未解决

09

任意代数数域的一般互反律

部分解决

10

不定方程可解性

已解决

11

代数系数之二次形式

已解决

12

一般代数数域的阿贝尔扩张

未解决

13

以二元函数解任意七次方程

已解决

14

证明一些函数完全系统的有限性

已解决

15

舒伯特演算之严格基础

部分解决

16

代数曲线及表面之拓扑结构

未解决

17

把有理函数写成平方和分式

已解决

18

非正多面体能否密铺空间、球体最紧密的排列

已解决

19

拉格朗日系统之解是否均可解析

已解决

20

所有有边界条件的变分问题是否都有解

已解决

21

证明有线性微分方程有给定的单值群

已解决

22

将解析关系以自守函数一致化

已解决

23

变分法的长远发展

未解决

表 1:希尔伯特 23 个问题的解决进度

另一方面,在哈代和利特尓伍德建立圆法工具的前 1 年,也就是 1919 年,挪威数学家布朗(Viggo Brun)推广了公元前 250 年就出现在古希腊的「筛法」,并利用推广后的筛法证明了:所有充分大的偶数都能表示成两个数之和,并且两个数的质因数个数都不超过 9 个。也就是说,所有「充分大」的偶数确实可以表示成两个数的和,但这两个数是合数,且这两个合数所包含的质因子个数小于等于 9 个。因此,布朗的证明一般被记作「9+9」,而哥德巴赫猜想就是「1+1」。

圆法和筛法为弱哥德巴赫猜想的证明提供了巨大的帮助。1937 年,苏联数学家维诺格拉多夫(Ivan Vinogradov)指出,充分大的奇数可以表示为三个质数的和。这一定理被称为维诺格拉多夫定理。他的学生博罗兹金(K. Borozdin)在 1939 年确定了这个「充分大」的下限是 314348907。这样一来,数学家们只需要验证小于 314348907 的奇数都可以表示为三个质数的和,结合维诺格拉多夫定理,就可以完全证明弱哥德巴赫猜想了。

数学家们似乎看到了曙光。然而,博罗兹金给出的这个下限实在是太大了,即使是用今天的超级计算机也无法对比这个下限小的所有数进行验证。1989 年,陈景润和王元将这个下限降低到 1043000.5。这个优化的下限结果仍然比较大,但相对已经好了很多。2002 年,香港大学的廖明哲与王天泽把这个下限降低到了 e3100[17]。虽然这个下限还是超过了计算机验证的范围,但比 1043000.5 来说又小了很多。

2013 年 5 月 1 日,法国国家科学研究院和巴黎高等师范学院的研究员 Helfgott 在线发表了两篇论文,宣布彻底证明了弱哥德巴赫猜想[18][19]。Helfgott 综合使用了圆法、筛法和「指数和」等统计方法,把维诺格拉多夫定理中的下限降低到了 1030 。同时,Helfgott 的同事 Platt 用计算机验证了在 1030之下的所有奇数都符合猜想,从而彻底解决了弱哥德巴赫猜想。

圆法对于弱哥德巴赫猜想的证明提供了巨大的帮助。但圆法对于强哥德巴赫猜想似乎无能为力。前面讲到,1919 年布朗用推广后的筛法证明「9+9」问题。数学家们将强哥德巴赫猜想解决的希望放在了布朗提出的方法上。数学家们在 1924 年至 1963 年,分别证明了「7+7」(1924 年)、「6+6」(1932 年)、「5+5」(1938 年)、「4+4」(1938 年)、「3+4」(1956 年)、「3+3」(1956 年)、「2+3」(1957 年)、「1+6」(1932 年)、「1+5」(1962 年)、「1+4」(1956 年)以及「1+3」(1965 年)问题,逐渐与最终目标:强哥德巴赫猜想的「1+1」靠近。

中国数学家陈景润于 1973 年对筛法做出重大的改进,提出了一种新的「加权筛法」,并证明了「1+2」问题[20]。然而,陈景润几乎已经将筛法发挥到了极致,似乎很难用筛法证明最终的「1+1」问题了。强哥德巴赫猜想的解决或许需要新的数学工具。质数的个数

我们回到质数的定义中来。相信朋友们在五年级学习质数时,小学老师一定会让每一位同学背诵 100 以内的质数表吧?我依稀记得我的小学老师教授了我们下述口诀:

2、3、5、7 和 11,

13、19 和 17,

23 来 29,31 来 37,

41、43 和 47,

53、59、61,

67、71 和 73,

79、83、89,再加一个 97。

不过,小学数学老师没有让每一位同学背诵大于 100 的质数,当时我们每个人心里一定都为此怀有感激之心。然而,现在想来,为什么小学老师不再要求我们背诵大于 100 的质数呢?

一个可能的原因是没有大于 100 的质数,然而这显然是不正确的,因为经过尝试后我们会发现 101 就是一个质数。我们扩展一下这个疑问,质数是否有无限多个?答案是肯定的。人类很早以前就已经知道有无限多个质数。早在公元前的 200~300 年间,古希腊数学家欧几里得(Euclid)就在他著名的数学教科书《几何原本》中证明了质数有无限多个。

第二个不需背诵大于 100 质数的可能原因是:质数在正整数之间出现的位置没有任何规律,只能通过死记硬背的方法记忆质数位置。用稍微数学一点的语言描述就是:质数在正整数中的分布似乎并无规律。18 世纪晚期,数学家们编制了一个巨大的质数表,试图寻找质数出现位置的规律,却并没有成功。不要说质数出现的位置了,就算求某个范围内质数的数量就已经非常困难。有多少个质数小于一个正整数 x 这样一个看似简单的问题都困扰了人类将近 200 年。当时,包括德国数学家高斯(Johann Carl Friedrich Gauss)和法国数学家勒让德(Adrien-Marie Legendre)等大数学家都有下述猜想,然而并没有找到严谨的证明。

当x无限增长时,不超过 x 的质数个数与 x/ln x 之比趋近于 1。(ln x 是 x 的自然对数)。

这个猜想后来被称为「质数定理」,简单来说就是:前 x 个正整数中大约有 x/ ln x 个质数。在质数定理提出后的大约 200 年,法国数学家阿达马(Jacques Hadamard)和比利时数学家瓦列-普金(Charles-Jean-Gustave-Nicholas de la Vallée-Poussin)才利用复变函数论在 1896 年首次证明了质数定理。虽然现在数学家们已经找到了不应用复变函数论证明质数定理的方法,但是所有已知的证明都非常复杂,远非原始结论这样清晰和简洁。

质数定理告诉我们,随着 x 的增大,质数在正整数中的分布会变得越来越稀疏。举例来说,100 以内有 25 个质数,质数占比为 25%。而 100 万以内的质数只占 100 万的 7.85%。这么看来,随着 x 的增大,每个质数之间相隔的距离平均来看也应该会越来越远。然而,事实似乎并非如此简单。这就涉及到与哥德巴赫猜想平级的「孪生质数猜想」[21]了。

所谓「孪生质数」,是指相差为 2 的质数对,例如:3 和 5、5 和 7、11 和 13,等等。用数学形式描述即为:质数对(p,p+2)为孪生质数。希尔伯特 1900 年报告中的第八个问题不仅回顾了哥德巴赫猜想,还提出了下面一个假设:

存在无穷多个质数 p,使得 p+2 也是质数。

1849 年,法国数学家波利尼亚克(Alphonse de Polignac)提出了一个更一般的「波利尼亚克猜想」:

对所有自然数 k,存在无穷多个质数对(p,p+2k)。

当 k=1 时,波利尼亚克猜想就是孪生质数猜想。

孪生质数猜想虽然不如哥德巴赫猜想那样著名,但其仍然被认为是一个公认的难题。2013 年 5 月 14 日,据《自然》(Nature)杂志报道[22],华人数学家张益唐证明:存在无穷多个质数对,其相差都小于 7000 万。张益唐的论文已被国际数学旗舰期刊《数学年刊》(Annals of Mathematics)于 2013 年 5 月 21 日接受。华人数学家陶哲轩随后于 2013 年 6 月 4 日开始了一个名为「PolyMath」的计划[23],邀请网上的志愿者们协助合作,降低张益唐的论文中所给出的 7000 万上限。截止至 2016 年 7 月 14 日,PolyMath 维基宣称上限已经降至 246[24]。

第三个可能的原因是很难找到一种快速方法判断一个正整数是否为质数。例如,339061 是否为一个质数?相信大家第一个反应就是用 339061 除以小于它的各个正整数,尝试找到一个因子。经过漫长而艰苦的人工计算后,我们最终会发现 339061=409×829,因此不是一个质数。判断某个正整数是否为质数的问题到现在为止依然困扰着数学界。这一问题在数学上被称为质数判定问题,或质性检测问题。

我们先看看特殊形式正整数的质数判定方法,没准会带来一定的突破呢?欧几里得在《几何原本》中指出,少量的质数可以写成 2p−1 的形式,其中 p 也是一个质数。1644 年,法国传教士梅森(Martin Mersenne)对形如 2p−1 形式的质数进行了研究。他提出了这样的论断:当 p=2,3,5,7,13,17,19,31,67,127,257 时,2p−1 是质数,而对于小于 257 的所有其它质数 p, 2p−1 都不是质数。数学家们花费了将近 300 年的时间研究了梅森给出的这一系列质数,并发现当 p=67 和 p=257 时, 2p−1 不是质数。与此同时,梅森给出的这一系列质数之间还遗漏了一些质数。1883 年,Pervushin 证明了 261−1 是质数。1911 年和 1914 年,Powers 分别证明了 289−1 和 2107−1 为质数。因梅森对这类质数的研究所做出的突出贡献,人们将形如 2p−1 的质数称为「梅森质数」。

梅森质数的发现历史也代表了人类寻找最大质数的历史。1876 年,法国数学家卢卡斯(François Édouard Anatole Lucas)证明了 2127−1 是梅森质数。在这之后的 75 年间, 2127−1 都保持了人类已知最大质数的记录。1876 年,卢卡斯总结并完善了一种检验梅森质数的快速方法。1930 年代,美国数学家莱默(Derrick Henry Lehmer)改进了卢卡斯所提出的算法。现今我们称这种梅森质数的快速检验方法为「卢卡斯-莱默质数检验法」(Lucas-Lehmer Primality Test)。电子计算机的发明革命化地改进了梅森质数的寻找。借助电子计算机的帮助,人类才通过卢卡斯-莱默质数检验法发现了更大的质数。1952 年,加州大学伯克利分校的美国数学家 Robinson 在莱默的指导下编写了计算机程序,利用位于洛杉矶加利福尼亚大学的西部自动计算机(Standards Western Automatic Computer,SWAC)发现了梅森质数 2521−1 和 2607−1。

为了找到更大的梅森质数,毕业于麻省理工学院的 Woltman 于 1996 年发起了因特网梅森质数大搜索(Great Internet Mersenne Prime Search,GIMPS)项目。任何志愿者都可以从网站上免费下载开放源代码的 Prime95 和 MPrime 软件来搜索梅森质数。这一项目取得了巨大的成功。截止到 2016 年 1 月,GIMPS 共搜索到 15 个梅森质数。现在已知最大的梅森质数是 2016 年 1 月 7 日发现的 274207281−1[25],共有 22338618 位十进制数。第二大的梅森质数是 2013 年 1 月 25 日发现的 257885161−1,共有 17425170 位十进制数。

对于一个不是特殊形式的正整数 a,其质数判定就变成一个比较困难的问题了。最简单的方法是所谓的「试除法」,依次尝试用 除以小于 a 的数(实际上,试到 a 就足够了),看看是否可以整除。然而,对于比较大的正整数 a,尝试所有 种可能所带来的计算量实在是太大了。数学家们因此寻找各种方式,提高质数判定的效率。

1770 年,英格兰数学家华林(Edward Waring)与他的学生威尔逊(John Wilson)提出了一个判定某个正整数是否为质数的等价条件。历史上称这个结论为威尔逊定理。这对师生当时未能给出这一定理的证明。1773 年,法国籍意大利裔数学家拉格朗日首次证明了威尔逊定理。基于威尔逊定理的质数判定法效率有所提高,但是判定的过程要进行一次「阶乘」运算,此质数判定法的计算量仍然比较夸张。随后,数学家们又提出了多种质数判定方法,包括莱默判定法、普洛兹(Proth)判定法、波克林顿(Pocklington)判定法等。但这些判定方法都涉及到复杂的指数运算。对于大整数的质数判定来说,这些判定方法的效率还是太低了。

上述方法都可以 100% 判定某个正整数是否为质数,我们一般称这些判定法为「确定判别法」。既然确定判别法的效率太低,我们能否换一种思路:是否能判断一个比较大的正整数基本上应该是个质数呢?也就是说,找到某种方法对正整数进行测试,如果测试通过,则有比较大的概率判断此正整数是个质数。遵循这一思路的判定方法一般称为「概率判别法」。事实证明,概率判别法虽然丧失了一部分准确性,但判定速度比确定判别法要快得多。最先发现的质数概率判别法直接利用了 1636 年法国数学家费马(Pierre de Fermat)提出的费马小定理,这一方法被称为「费马概率判别法」。

提到费马,最广为人知的想必就是费马《页边笔记》中留下的这句话了:

我发现了一个美妙的证明,但是由于空白太小而没有写下来。

这句话指的就是「费马猜想」的证明。不曾想,这简单的一句话花费了数学家们超过 300 年的努力,才最终得到了猜想的完全证明。为了证明费马猜想,在横跨三个世纪的证明过程中诞生了代数几何中的「椭圆曲线」(在现代密码学中我们经常会用到它),以及群论中的「伽罗华理论」(同样是现代密码学构造的基石)。经过数学家们的不懈努力,1994 年英国数学家怀尔斯(Andrew John Wiles)最终完成了费马猜想的证明,使得费马猜想升级为「费马大定理」。相关证明结果发表在 1995 年的《数学年刊》(Annals of Mathematics)上[26]。是的,这和张益唐「孪生质数猜想」证明所发表的期刊相同。怀尔斯的完整证明一共有 109 页,怪不得 300 年前费马在《页边笔记》中写不下。

为了进一步提高质数概率判别法的效率,美国数学家Solovay 和德国数学家Strassen 于 1977 年提出了「Solovay-Strassen 概率判别法」[27]。然而,Solovay-Strassen 概率判别法并没有得到广泛的应用,但在思想上给予了数学家们很大的启迪。1976 年,卡内基梅隆大学的计算机系教授Miller 提出了一个基于广义黎曼猜想的质数确定判别法[28]。然而,广义黎曼猜想还没有得到证明,因此Miller 所提出的判别法暂时还无法使用。后来,以色列耶路撒冷希伯来大学的Rabin 教授对判别法进行了修改,提出了不依赖于广义黎曼猜想的质数概率判别法[29]。因 Miller 和 Rabin 对此判别法都做出了突出的贡献,这一判别法被命名为「Miller-Rabin 质数判别法」。现今,Miller-Rabin 质数判别法是最为常用的质数判别法,广泛用于密码学方案中的大质数选取步骤中。

有了质数的概念,我们就可以进一步回顾另一个广为人知的概念:「最大公约数」。能整除两个整数的整数成为这两个整数的「公约数」。例如,对于整数 24 和 36,整数 1、2、3、4、6、12 都可以整除 24 和 36,因此它们都是 24 和 36 的公约数。而最大公约数,顾名思义,就是公约数里面最大的那个。例如,12 是 24 和 36 公约数中最大的,因此 12 就是 24 和 36 的最大公约数。如果两个整数的最大公约数是 1,就称这两个整数「互质」。例如,17 和 22 的最大公约数是 1,因此 17 和 22 互质。

如何求两个整数的最大公约数呢?这里又出现了欧几里得的名字,可见欧几里得为数学做出了巨大的贡献。欧几里得在《几何原本》中记载了一个求解最大公约数的方法,这个方法也就被命名为「欧几里得法」。又因为这个方法的过程是依次进行多次除法,故这个方法又被称为「辗转相除法」。辗转相除法的效率比「分别求两个数的公约数,再找最大值的方法」高得多。我们这里不对方法做详细讲解,只要知道人类找到了快速求解最大公约数的方法就可以了。

(i) 回信原文为古德语:Dass aber ein jeder numerous par eine summa duorum primorum sey, halte ich für ein ganz gewisses theorem, ungeachtet ich dasselbe nicht demonstriren kann. 感谢金歌同学协助翻译.

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈