来自 历史人物 2019-11-22 08:48 的文章
当前位置: 766net必赢 > 历史人物 > 正文

辗转相除法,最大公因数

欧几里得(希腊文:Ευκλειδη? ,约公元前330年—前275年),古希腊数学家,被称为“几何之父”。他活跃于托勒密一世(公元前323年-前283年)时期的亚历山大里亚,他最著名的着作《几何原本》是欧洲数学的基础,提出五大公式,发展欧几里得几何,被广泛的认为是历史上最成功的教科书。欧几里得也写了一些关于透视、圆锥曲线、球面几何学及数论的作品,是几何学的奠基人。欧几里得算法以及对完全数的研究都对后世产生很大影响。《几何原本》是古希腊数学发展的顶峰,欧几里得使几何学成为一门独立的、演绎的科学。 人物生平 关于他的生平,现在知道的很少。早年大概就学于雅典,深知柏拉图的学说。公元前300年左右,在托勒密王(公元前364~前283)的邀请下,来到亚历山大,长期在那里工作。他是一位温良敦厚的教育家,对有志数学之士,总是循循善诱。但反对不肯刻苦钻研、投机取巧的作风,也反对狭隘实用观点。据普罗克洛斯记载,托勒密王曾经问欧几里得,除了他的《几何原本》之外,还有没有其他学习几何的捷径。欧几里得回答说: “几何无王者之路。”意思是, 在几何里,没有专为国王铺设的大道。 这句话后来成为传诵千古的学习箴言。斯托贝乌斯记述了另一则故事,说一个学生才开始学第一个命题,就问欧几里得学了几何学之后将得到些什么。欧几里得说:给他三个钱币,因为他想在学习中获取实利。 欧几里得生于雅典,是柏拉图的学生。他的科学活动主要是在亚历山大进行的,在这里,他建立了以他为首的数学学派。 欧几里得,以他的主要着作《几何原本》而着称于世,他的工作重大意义在于把前人的数学成果加以系统的整理和总结,以严密的演绎逻辑,把建立在一些公理之上的初等几何学知识构成为一个严整的体系。欧几里得建立起来的几何学体系之严谨和完整,就连20世纪最杰出的大科学家爱因斯坦也不能对他不另眼相看。 爱因斯坦说:“一个人当他最初接触欧几里得几何学时,如果不曾为它的明晰性和可靠性所感动,那么他是不会成为一个科学家的。” 《几何原本》中的数学内容也许没有多少为他所创,但是关于公理的选择,定理的排列以及一些严密的证明无疑是他的功劳,在这方面,他的工作出色无比。 欧几里得的《几何原本》共有13篇,首先给出的是定义和公理。比如他首先定义了点、线、面的概念。他整理的5条公理其中包括: 1.从一点到另一任意点作直线是可能的; 2.所有的直角都相等; 3.a=b,b=c,则a=c; 4.若a=b则a c=b c等等。 这里面还有一条公理是欧几里得自己提出的,即:整体大于部分。虽然这条公理不像别的公理那么一望便知,不那么容易为人接受,但这是欧氏几何中必须的,必不可少的。他能提出来,这恰恰显示了他的天才,欧几里得除了写作重要几何学巨着《几何原本》外,还着有《数据》、《图形分割》、《论数学的伪结论》、《光学》、《反射光学之书》等着作。 欧几里得距离 欧几里得距离一般指欧几里得度量,欧几里得度量(euclidean metric)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。 欧几里得算法 欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。 其计算原理依赖于下面的定理: 定理:两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数(greatest common divisor)缩写为gcd。 gcd = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0) 证法一 a可以表示成a = kb r(a,b,k,r皆为正整数),则r = a mod b 假设d是a,b的一个公约数,记作d|a,d|b,即a和b都可以被d整除。 而r = a


欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。

  • kb,两边同时除以d,r/d=a/d-kb/d=m,等式左边可知m为整数,因此d|r 因此d也是(b,a mod b)的公约数 因此和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。 证法二 第一步:令c=gcd,则设a=mc,b=nc 第二步:可知r =a-kb=mc-knc=c 第三步:根据第二步结果可知c也是r的因数 第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,,则m=kn xd=kyd xd=d,则a=mc=dc,b=nc=ycd,故a与b最大公约数≥cd,而非c,与前面结论矛盾】 从而可知gcd=c,继而gcd=gcd,得证 以上两种方法实质一样的。 人物评价 欧几里德是古代希腊最负盛名、最有影响的数学家之一,他是亚历山大里亚学派的成员。欧几里德写过一本书,书名为《几何原本》共有13卷。这一着作对于几何学、数学和科学的未来发展,对于西方人的整个思维方法都有极大的影响。《几何原本》的主要对象是几何学,但它还处理了数论、无理数理论等其他课题。欧几里德使用了公理化的方法。公理就是确定的、不需证明的基本命题,一切定理都由此演绎而出。在这种演绎推理中,每个证明必须以公理为前提,或者以被证明了的定理为前提。这一方法后来成了建立任何知识体系的典范,在差不多2000年间,被奉为必须遵守的严密思维的范例。《几何原本》是古希腊数学发展的顶峰。

辗转相除法,最大公因数。问题##

欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数。例如,gcd(50,15)=5。


 

证明##

其计算原理依赖于下面的定理:
766net必赢,定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数(greatest common divisor)缩写为gcd。
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

基本算法:设a=qb r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。

证法一##

a可以表示成a = kb r(a,b,k,r皆为正整数,且r<b),则r = a mod b
假设d是a,b的一个公约数,记作d|a,d|b,即a和b都可以被d整除。
而r = a - kb,两边同时除以d,r/d=a/d-kb/d=m,由等式右边可知m为整数,因此d|r
因此d也是b,a mod b的公约数
假设d是b,a mod b的公约数, 则d|b,d|(a-k*b),k是一个整数,
进而d|a.因此d也是a,b的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

 

证法二##

第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:可知r =a-kb=mc-knc=(m-kn)c
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,(d>1),则m=kn xd=kyd xd=(ky x)d,则a=mc=(ky x)dc,b=nc=ycd,故a与b最大公约数≥cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r),得证
注意:两种方法是有区别的。


第一种证明:

代码##

    public static long gcd(long m, long n) {
        while (n != 0) {
            long rem = m % n;
            m = n;
            n = rem;
        }
        return m;
    }

      a可以表示成a = kb r,则r = a mod b

分析##

如代码所示的算法计算gcd(M,N),假设M>=N(如果N>M,则循环的第一次迭代,将他们互相交换)。算法连续计算余数直到余数是0为止,最后的非0余数就是最大公因数。因此,如果M=1989和N=1590,则余数序列为399,393,6,3,0。从而,gcd(1989,1590)=3。正如序列所表明的,这是一个快速算法。

估计算法的整个运行时间依赖于确定余数序列究竟有多长。显然logN看似像理想中的答案,但是根本看不出余数的值按照常数因子递减的必然性,因为我们看到余数从399仅仅降到393.事实上,在一次迭代中余数并不按照一个常数因子递减。然而,我们可以证明,在两次迭代后,余数最多是原始值得一半。

证明如果M>N,则M mod N < M/2如下:
存在两种情形。如果M<=M/2,则由于余数小于N,故定理在这种情况下一定成立。另一种情形则是M>M/2。但是此时M仅仅含有一个N,从而余数为M-N<M/2,定理得证。所以时间复杂度为O(logN)。

  假设d是a,b的一个公约数,则有

  d|a, d|b,而r = a - kb,因此d|r

  因此d是(b,a mod b)的公约数

  假设d 是(b,a mod b)的公约数,则

本文由766net必赢发布于历史人物,转载请注明出处:辗转相除法,最大公因数

关键词: 766net必赢