2.思考: 小学学过的求两个数的最大公约数的方法? 先用两个公有的质因数连续去除, 直除到所得的商是互质数为止,然后 把所有的除数连乘起来
2. 思考： 小学学过的求两个数的最大公约数的方法？ 先用两个公有的质因数连续去除， 一直除到所得的商是互质数为止，然后 把所有的除数连乘起来
例:求下面两个正整数的最大公约数: (1)求25和35的最大公约数 (2)求49和63的最大公约数 (1)52535 (2)74963 57 所以,25和35的最所以,49和63的最 大公约数为5 大公约数为7 例:如何算出8251和6105的最大公约数?
例：求下面两个正整数的最大公约数： （1）求25和35的最大公约数 （2）求49和63的最大公约数 （1）5 25 5 35 7 （2）7 49 7 63 9 所以，25和35的最 大公约数为5 所以，49和63的最 大公约数为7 例：如何算出8251和6105的最大公约数？
新课讲解: 、辗转相除法(欧几里得算法) 1、定义: 所谓辗转相除法,就是对于给定的 两个数,用较大的数除以较小的数。若 余数不为零,则将余数和较小的数构成 新的一对数,继续上面的除法,直到大 数被小数除尽,则这时较小的数就是原 来两个数的最大公约数
新课讲解： 一、辗转相除法（欧几里得算法） 1、定义： 所谓辗转相除法，就是对于给定的 两个数，用较大的数除以较小的数。若 余数不为零，则将余数和较小的数构成 新的一对数，继续上面的除法，直到大 数被小数除尽，则这时较小的数就是原 来两个数的最大公约数
2、步骤:(以求8251和6105的最大公约数的过 程为例) 第一步用两数中较大的数除以较小的数,求得 商和余数:825116105×1+2146 结论:8251和6105的公约数就是6105和2146 的公约数,求8251和6105的最大公约数,只要 求6038461大公约数就可以乃什么 第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813 的最大公约数
2、步骤:（以求8251和6105的最大公约数的过 程为例） 第一步 用两数中较大的数除以较小的数，求得 商和余数:8251=6105×1+2146 结论： 8251和6105的公约数就是6105和2146 的公约数，求8251和6105的最大公约数，只要 求出6105和2146的最大公约数就可以了。 第二步 对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813 的最大公约数
完整的过程 8251=6105×1+2146 显然37是 6105=2146×2+1813148和37 的最大公 2146=1813×1+333约数,也 就是8251 1813=333×5+148和6105的 最大公约 333=148×2+37 数 148=37×4+0
完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是 148和37 的最大公 约数，也 就是8251 和6105的 最大公约 数