课堂探究·素养提升
题型一 求最大公约数 [例1] 分别用辗转相除法和更相减损术求779与209的最大公约数.
解:法一 辗转相除法: 779=209×3+152, 209=152×1+57, 152=57×2+38, 57=38×1+19, 38=19×2. 所以,779与209的最大公约数为19.
法二 更相减损术法: 779-209=570,570-209=361,361-209=152,209-152=57,152-57=95, 95-57=38,57-38=19,38-19=19. 所以779和209的最大公约数为19.
方法技巧
求两个正整数的最大公约数的问题,可以用辗转相除法,也可以用更 相减损术.
思考3:不同进位制之间的数是否能比较大小?
答案:能.都可以把其化为相同进位制的数,然后比较其大小.
名师点津
常见的进位制 (1)二进制:①只使用0和1两个数字;②满二进一,如1+1=10. (2)八进制:①使用0,1,2,3,4,5,6,7八个不同的数字;②满八进一,如 7+1=10. (3)十六进制:①使用0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F这十六个不 同的数码,其中A,B,C,D,E,F分别代表十进制中的10,11,12,13,14,15; ②满十六进一,如F+1=2+E=10.
新知导学·素养养成
1.求两个正整数的最大公约数的算法
(1)辗转相除法(欧几里得算法)的算法步骤: 第一步,给定 两个正整数m,n . 第二步,计算 m除以n所得的余数r . 第三步, m=n,n=r . 第四步,若r=0,则m,n的最大公约数等于 m ;否则返回 第二步 .