更相减损术原理

1、方法一： 7 98 63 14 9方法二： 更相减损术是出自更相减损术是出自九章算术九章算术的的一种求最大公约数的算法，它原本一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任是为约分而设计的，但它适用于任何需要求最大公约数的场合。何需要求最大公约数的场合。更相减损术的原理：更相减损术的原理：(a,b)=(a-b,b)这里将这里将gcd (a,b)简记为简记为(a,b).更相减损术是辗转相除法（欧几里德算法，更相减损术是辗转相除法（欧几里德算法，Euclid algorithm）的一个特例，）的一个特例，它的原理是它的原理是(a,b)=(a-nb,b)下面我们来证明：下面我们来证明：

2、(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 m，n(mn).n(mn). 第二步，计算第二步，计算m-nm-n所得的差所得的差k. k. 第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，

4、若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于 m 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该程序框图对应的程序如何表述该程序框图对应的程序如何表述? ?解：由于解：由于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=151