1、1.3 算法案例算法案例 第二课时第二课时 主讲教师 知识探究（一）知识探究（一）:辗转相除法辗转相除法知识探究（一）知识探究（一）:辗转相除法辗转相除法思考思考1:18与与30的最大公约数是多少？你的最大公约数是多少？你是怎样得到的？是怎样得到的？知识探究（一）知识探究（一）:辗转相除法辗转相除法思考思考1:18与与30的最大公约数是多少？你的最大公约数是多少？你是怎样得到的？是怎样得到的？先用两个数公有的质因数连续去除，先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公后把所有的除数连乘起来即为最大公约数约数.思
2、考思考2:对于对于8251与与6105这两个数，由于这两个数，由于其公有的质因数较大，利用上述方法求其公有的质因数较大，利用上述方法求最大公约数就比较困难最大公约数就比较困难.注意到注意到8251=61051+2146，那么，那么8251与与6105这两个数的公约数和这两个数的公约数和6105与与2146的公约的公约数有什么关系？数有什么关系？思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数
3、吗？8251=8251=610561051+1+21462146，思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？8251=8251=610561051+1+21462146，61056105=214621462+2+18131813，思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述
4、操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146=181318131+1+333333，8251=8251=610561051+1+21462146，61056105=214621462+2+18131813，思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146=181318131+1+333333，18
5、131813=3333335+5+148148，8251=8251=610561051+1+21462146，61056105=214621462+2+18131813，思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146=181318131+1+333333，333333=1481482+2+3737，18131813=3333335+5+148148，8251=8251=
6、610561051+1+21462146，61056105=214621462+2+18131813，思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？21462146=181318131+1+333333，148148=37374+0.4+0.333333=1481482+2+3737，18131813=3333335+5+148148，8251=8251=610561051+1+214
7、62146，61056105=214621462+2+18131813，思考思考3:又又6105=21462+1813，同理，同理，6105与与2146的公约数和的公约数和2146与与1813的公的公约数相等约数相等.重复上述操作，你能得到重复上述操作，你能得到8251与与6105这两个数的最大公约数吗？这两个数的最大公约数吗？理论迁移理论迁移(1)1515，600(2)117，182例例1 用辗转相除法求下列各数的最大用辗转相除法求下列各数的最大公约数公约数.理论迁移理论迁移(1)1515，600(2)117，182例例1 用辗转相除法求下列各数的最大用辗转相除法求下列各数的最大公约数公约数
8、.答案答案：(1)15 (2)13例例2 求求325，130，270三个数的最大公约数三个数的最大公约数.例例2 求求325，130，270三个数的最大公约数三个数的最大公约数.因为因为325=1302+65，130=652，所所以以325与与130的最大公约数是的最大公约数是65.例例2 求求325，130，270三个数的最大公约数三个数的最大公约数.因为因为325=1302+65，130=652，所所以以325与与130的最大公约数是的最大公约数是65.因为因为270=654+10，65=106+5，10=52，所以所以65与与270最大公约数是最大公约数是5.例例2 求求325，130，
9、270三个数的最大公约数三个数的最大公约数.因为因为325=1302+65，130=652，所所以以325与与130的最大公约数是的最大公约数是65.因为因为270=654+10，65=106+5，10=52，所以所以65与与270最大公约数是最大公约数是5.故故325，130，270三个数的最大公三个数的最大公约数是约数是5.知识探究（二）知识探究（二）:更相减损术更相减损术 思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多
10、少？的最大公约数为多少？知识探究（二）知识探究（二）:更相减损术更相减损术 98-63=3598-63=35，思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？知识探究（二）知识探究（二）:更相减损术更相减损术 98-63=3598-63=35，63-35=2863-35=28，思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约
11、数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？知识探究（二）知识探究（二）:更相减损术更相减损术 98-63=3598-63=35，35-28=735-28=7，63-35=2863-35=28，思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？知识探究（二）知识探究（二）:更相减损术更相减损术 98-63=3598-63=35，28-7
12、=2128-7=21，35-28=735-28=7，63-35=2863-35=28，思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？知识探究（二）知识探究（二）:更相减损术更相减损术 98-63=3598-63=35，21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则
13、则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？知识探究（二）知识探究（二）:更相减损术更相减损术 98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，35-28=735-28=7，63-35=2863-35=28，思考思考1:设两个正整数设两个正整数mn，若，若m-n=k，则则m与与n的最大公约数和的最大公约数和n与与k的最大公约的最大公约数相等数相等.反复利用这个原理，可求得反复利用这个原理，可求得98与与63的最大公约数为多少？的最大公约数为多少？“更相减损术更相减损术”在中国古代数学专著在中国古代数学专著九九章算术章算术中记述为：中记述为：可半者半之，不可半者，副置分母、可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等子之数，以少减多，更相减损，求其等也，以等数约之也，以等数约之.理论迁移理论迁移用辗转相除法求用辗转相除法求80和和36的最大公约数，的最大公约数，并用更相减损术检验所得结果并用更相减损术检验所得结果.练习练习 小结作业小结作业小结作业小结作业作业：作业：习案习案作业八作业八
