1、如何求如何求8251和和6105的最大公约数？的最大公约数？所以，所以，24和和30的最大公约数为的最大公约数为6210和和462的最大公约数为的最大公约数为4224（1）2123015435210（2）21054622313357577111 1、辗转相除法（欧几里得算法）、辗转相除法（欧几里得算法）所谓辗转相除法所谓辗转相除法,就是对于给定的两个数就是对于给定的两个数,用较大的数除以较用较大的数除以较小的数小的数.若余数不为零若余数不为零,则将余数和较小的数构成新的一对数则将余数和较小的数构成新的一对数,继继续上面的除法续上面的除法,直到大数被小数除尽直到大数被小数除尽,则这时较小的数就是
2、原来两则这时较小的数就是原来两个数的最大公约数个数的最大公约数.例例1.用辗转相除法求用辗转相除法求98与与63的最大公约数的最大公约数.98=1633563=1 352835=1 28728=4 70所以，所以，98与与63的最大公约数为的最大公约数为7 7新新 课课探究探究1。用辗转相除法求用辗转相除法求225和和135的最大的最大公约数公约数完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大的最大公约数，也就是公约数，也就是8
3、251和和6105的最大公约数的最大公约数 显然显然45是是90和和45的最大公约数，的最大公约数，也就是也就是225和和135的最大公约数的最大公约数 探究探究2：辗转相除法的解题步骤：辗转相除法的解题步骤如何？其蕴含的数学原理是什如何？其蕴含的数学原理是什么？么？225=1351+90135=901+4590=452 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤,这实际上是一个循环结构这实际上是一个循环结构m=nm=nq qr r算法步骤算法步骤第一步：输入两个正整数第一步：输入两个正整数m,n(mn).m,n(mn).第二步：计算第二
4、步：计算m m除以除以n n所得的余数所得的余数r.r.第三步：第三步：m=n,n=r.m=n,n=r.第四步：若第四步：若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则转到第二步否则转到第二步.第五步：输出最大公约数第五步：输出最大公约数m.m.程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0?输出输出m m结束结束INPUT“m,n=“;m,nDOLOOP UNTIL r=m MOD nm=nn=rr=0PRINT mEND程序框图程序框图程程 序序INPUT“m,n=“;m
5、,nWHILE WEND r=m MOD nm=nn=rr0PRINT mENDr=1求求m m除以除以n n的余数的余数r rm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr0?r0?输出输出m m结束结束r=1r=1翻译出来为：翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶第一步：任意给出两个正数；判断它们是否都是偶数若是，用数若是，用2 2约简；若不是，执行第二步约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作数与所得的差比较，并以大数减小数继续这个操作，直
6、到所得的数相等为止，则这个数（等数）就是所，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数求的最大公约数例例2 2 用更相减损术求用更相减损术求9191与与4949的最大公约数，的最大公约数，并用并用辗转相除法检验结果辗转相除法检验结果 解法解法1：（更相减损术）由于更相减损术）由于49不是偶数，把不是偶数，把91和和49以以大数减小数，并辗转相减，大数减小数，并辗转相减，即：即：914942 49427 42735 35728 28721 21714 147791与与49的最大公约数是的最大公约数是7。解法解法2（辗转相除法）辗转相除法）919149491 142 4942 4942421 17 7 42 427 76 6 91与与49的最大公约数是的最大公约数是7。INPUT“m,n=”;m,nWHILE mn IF mn THEN m=m-n ELSE n=n-m END IFWENDPRINT nEND程序框图程序框图输入输入m,n开始开始mn？mn？m=m-nn=n-m输出输出n结束结束NYYN算法步骤算法步骤(1)输入两个整数输入两个整数m，n(2)若若mn,转到转到(3),否则转到否则转到(4)(3)若若mn,则则m=m-n,否则否则n=n-m,转到转到(2)(4)输出最大公约数输出最大公约数n
