高中数学例题：辗转相除法与更相减损术
-
高中数学例题：辗转相除法与更相减损术
例<
/p>
1
．
分别用辗转相除法和更相减损术求<
/p>
378
与
90
的
最大公约数．
【答案】
18
【解析】
用辗转相除法：
378
=90
×
4+18
，
< br>90=18
×
5
．
∴
378
与
90
的最大公约数是
18
．
用更相减损术：
∵
378
与
90
都是
偶数，
∴用
2
约分
后得
189
和
45
．
189
－
4
5=144
，
144
－
45=99
，
99
－
45=54
，
54
－<
/p>
45=9
，
45
－
9=36
，
36
－
9=27
，
27
－
9=18
，
18
－
9=9
．
∴
378
与
90<
/p>
的最大公约数为
2
×
9=18
．
【总结升华】比较辗转相除法与更相减损术的区别
(1)
都是求最大公约数的方法，
计算上辗转相除
法以除法为主，
更
相减损术以减法为主，
计算次数上辗转相除法计算次数相对较少，
特
别当两个数字大
小区别较大时计算次数的区别较明显；
(2)
从结果体现形式来看，
辗转相除法体现结果是以相除余数为
0
则得到，而更相减损术则以减数与差相等而得到
.
由该题可以看出，辗转相除法得最大公约数的步骤较少
.
对比两种方法控制好算法的结束，辗转相除法是到达余数为
0
，
更相减损术是到达减数和差相等
.
举一反三：
第
1
页
共
5
页
【变式
1
】
（
1
）
用更相减损术求两个正数
84
与
72
的最大公约数．
（
2
）利用辗转相除法求
< br>3869
与
6497
的最大公约
数与最小公倍
数．
【解析】
（
1
）
因为
84=21
×
4
，
72=18
×
4
，
所以
21
－
18=3
，
18
－
3=15
，
15
－
3=
12
，
12
－<
/p>
3=9
，
9
－
3=6
，
6
－
3=3
．
所以
21
和
18
的最大公约数等于
3
．
所以
84
和
72
的最大公约数等于
12
．
【总结
升华】
先约简，
再求
21
与
18
的最大公约数，
然后
乘以约
简的
4
得
84
与
72
的最大公约数．
（
2
）
6497=3869
×
1+2628
，
3869=2628
×
1+1241<
/p>
，
2628=1241
×
2+146
，
1241=146
×
8+73
，
146=73
×
2+0
．
所以
3
869
与
6 497
的最大公约数为<
/p>
73
，
最小公倍数为
3 869
×
6497
÷
73=344341
< br>．
例
2
．求三个数：
168
，
54
，
264
的最大公约数．
第
2
页
共
5
页