辗转相除法与更相减损术

1、探究一,辗转相除法思考思考1:在小学中我们是如何求出两个正整数在小学中我们是如何求出两个正整数的最大公约数的呢的最大公约数的呢?算法案例算法案例之求最大公约数之求最大公约数解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：236 例、求18与24的最大公约数：短除法短除法 思考思考2:2:对于对于82518251与与61056105这两个数，它们这两个数，它们的最大的最大公约数是多少？你是怎样得到的？公约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求由于它们公有的质因数较大，利用上述方法

2、求最大公约数就比较困难最大公约数就比较困难. .有没有其它的方法可以较简有没有其它的方法可以较简单的找出它们的最大公约数呢？单的找出它们的最大公约数呢？辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得商和余数用两数中较大的数除以较小的数，求得商和余数8251=61051+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的公约数，求的公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105

3、和和2146的公约数就可以了。的公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最

4、大公约数，的最大公约数，也就是也就是8251和和6105的最大公约的最大公约数数 显然显然45是是90和和45的最大公约数，也就是的最大公约数，也就是225和和135的最大公约数的最大公约数 思考思考1：从上面的两个例子可以看出计算：从上面的两个例子可以看出计算的规律是什么？的规律是什么？ S1：用大数除以小数：用大数除以小数S2：除数变成被除数，余数变成除数：除数变成被除数，余数变成除数S3：重复：重复S1，直到余数为，直到余数为0练习：用辗转相除法求下列两数的最大公约数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）459824171 1、

5、辗转相除法（欧几里得算法）、辗转相除法（欧几里得算法）（1）算理：所谓辗转相除法，就是对于给定）算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大尽，则这时较小的数就是原来两个数的最大公约数。公约数。九章算术九章算术更相减损术更相减损术 算理：算理：可半者半之，不可半者，副置分母、子可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等

6、也，以等之数，以少减多，更相减损，求其等也，以等数约之。数约之。第一步：第一步：任意给定两个正整数；判断他们是否都是任意给定两个正整数；判断他们是否都是偶数。若是，则用偶数。若是，则用2约简；若不是则执行第二步。约简；若不是则执行第二步。第二步：第二步：以较大的数减较小的数，接着把所得的差以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。求的最大公约数。2、更相减损术、更相减损术（1）算理）算理：所谓更相减损术，就

7、是对于给：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。原来两个数的最大公约数。例例3 3 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大数减小数，并辗转相减并辗转相减 98986

8、3633535636335352828353528287 728287 7212121217 7212114147 77 7所以，所以，9898和和6363的最大公约数等于的最大公约数等于7 7 用更相减损术求两个正数用更相减损术求两个正数8484与与7272的最大公约数的最大公约数 练习：练习：先约简，再求先约简，再求21与与18的最大公约数的最大公约数,然后乘然后乘以两次约简的质因数以两次约简的质因数4 例例2 2 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数. . 168=93168=931+751+75， 93=7593=

9、751+181+18， 75=1875=184+34+3， 18=318=36.6.辗转相除法：辗转相除法：更相减损术更相减损术: : 168-93=75168-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=36-3=3. . 例例3 3 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求8080与与3636的最大公约数

10、的最大公约数. . 例例3、求、求324、243、135这三个数的最大这三个数的最大公约数公约数。思路分析：求三个数的最大公约数可以先求出两个思路分析：求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。数的最大公约数即为所求。 例例4 4 求求325325，130130，270270三个数的最大公约数三个数的最大公约数. . 因为因为325=130325=1302+652+65，130=65130=652 2，所以，所以325325与与130130的最大公约数是的最大公约数是6565. . 因为因为270=65270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565与与270270最大公约数是最大公约数是5.5. 故故325325，130130，270270三个数的最大公约数是三个数的最大公约数是5.5.比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别（1 1）都是求最大公约数的方法，计算上辗转相除）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特