更相减损术原理

《更相减损术原理》由会员分享，可在线阅读，更多相关《更相减损术原理（12页珍藏版）》请在金锄头文库上搜索。

1、更相减损术原理更相减损术原理更相减损术原理更相减损术原理研究性学习研究性学习研究性学习研究性学习求98与63的最大公约数方法一： 7 98 63 14 9方法二： 更相减损术是出自更相减损术是出自九章算术九章算术的一的一种求最大公约数的算法，它原本是为种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要约分而设计的，但它适用于任何需要求最大公约数的场合。求最大公约数的场合。更相减损术的原理：更相减损术的原理：(a,b)=(a-b,b)这里将这里将gcd (a,b)简记为简记为(a,b).更相减损术是辗转相除法（欧几里德算法，更相减损术是辗转相除法（欧几里德算法，Euclid alg

2、orithm）的一个特例，）的一个特例，它的原理是它的原理是(a,b)=(a-nb,b)下面我们来证明：下面我们来证明：(a,b)=(a-nb,b)证：不妨设证：不妨设d是是a,b的最大公因子。的最大公因子。即即a=rd,b=sd,并且并且其中其中(r,s)=1,即存在即存在x,y,使得使得xr+ys=1.从而从而a-nb=(r-ns)d,b=sd,且且x(r-ns)+(xn+y)s=xr+ys=1,即即(r-ns,s)=1于是于是:d=(a-nb,b)于是得证。于是得证。九章算术九章算术 可半者半之，不可半者半之，不可半者，副置分母、可半者，副置分母、子之数，以少减多，子之数，以少减多，更相

3、减损，求其等更相减损，求其等也。以等数约之。也。以等数约之。九章算术九章算术 翻译成现代语言如下： 第一步第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法，实际上就是辗转相除法。第一步，第一步，给定两个正整数定两个正整数m，n(mn). 第二步，第二步，计算算m-n所得的差所得的差k. 第三步，比第三步，比较n与与k的大小，其中大

4、者用的大小，其中大者用m表表示，小者用示，小者用n表示表示. 第四步，若第四步，若m=n，则m，n的最大公的最大公约数等于数等于m；否；否则，返回第二步，返回第二步. 该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m，nnkm=n是是输出输出m结束结束mnk=m- -n是是否否=m=k否否INPUT mINPUT m，n nWHILE WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDENDm=n该程序框图对应的程序如何表述该

5、程序框图对应的程序如何表述? ?用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，以大数减小数，并并 展转相减展转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，所以，98和和63的最大公约数等于的最大公约数等于7。理论迁移：理论迁移：用更相减损术求用更相减损术求168与与93的的最大公约数。最大公约数。更相减损术更相减损术:168-93=75:168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3.所以168与93的最大公约数是3