1.3 算 法 案 例—— 辗转相除法（欧几里得算法）与更相减损术 3 59 15[ 问题 1] ：在小学，我们已经学过求最大公约数的知识，你能求出 18 与 30 的最大公约数吗？〖创设情景，揭示课题〗 18 3023∴18 和 30 的最大公约数是 2×3=6.先用两个数公有的质因数连续去除 , 一直除到所得的商是互质数为止 , 然后把所有的除数连乘起来 . 练习 1 、求两个正整数的最大公约数（ 1 ）求 25 和 35 的最大公约数（ 2 ）求 49 和 63 的最大公约数2 、求 204 与 85 的最大公约数 25（ 1 ） 5535749（ 2 ） 77639所以， 25 和 35 的最大公约数为 5 所以， 49 和 63 的最大公约数为 7 分析： 204 与 85 两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数 辗转相除法（欧几里得算法）用辗转相除法求 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 6105=2146×2+1813 2146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例 2 用辗转相除法求 225 和 135 的最大公约数225=135×1+90135=90×1+4590=45×2显然 37 是 148 和 37 的最大公约数，也就是 8251 和 6105 的最大公约数 显然 45 是 90 和 45 的最大公约数，也就是 225 和 135 的最大公约数 练习 1 ：利用辗转相除法求两数 4081 与 20723的最大公约数 . 20723=4081×5+318; 4081=318×12+265; 318=265×1+53; 265=53×5+0.(53) 利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数 m 除以较小的数 n 得到一个商 q0 和一个余数 r0 ； (m=n×q0+r0) 第二步：若 r0 ＝ 0 ，则 n 为 m ， n 的最大公约数；若 r0≠0 ，则用除数 n 除以余数 r0 得到一个商 q1 和一个余数 r1 ； (n=r0×q1+r1) 第三步：若 r1 ＝ 0 ，则 r0 为 m ， n 的最大公约数；若 r1≠0 ，则用除数 r0 除以余数 r1 得到...
VIP
