CHAPTER 苦浦高中课程标准实验教科书数学(选修46)初等数论初步 二最大公因数与最小公倍数 1.最大公因数 给定两个整数a,b,必有公共的因数,叫做它们的公因数,当a,b不全为零时,在 有限个公因数中最大的一个叫做a,b的最大公因数,记作(a,b). 例如,8和14的全部公因数为1,-1,2,-2,最大的公因数为2,所以 (-8.14)=2. 如果a,b的最大公因数为1,那么称a,b是互素的 类似地,我们可以定义三个或更多个整数的最大公因数和互素的概念.将整数a,b c的最大公因数记作(a,b,c),依此类推 如何计算一组非零整数的最大公因数呢?我们已经学习过一种算法短除法 试用短除法计算下列两组数的最大公因数: (1)375,105; (2)1840,667 从中你能感受到什么 …………… 我们发现,用短除法求最大公因数有一定的局限性,因为用它每进行一次操作必须事 先观察到一个大于1的公因数,而这一点有时难以做到.特别是求两个较大整数的公因数 时,这一点显得更为突出 如何求(1840,667)?一个自然的考虑是把1840,667通过适当的方式都变小,变小 后,公因数就容易求出了.如何变小呢?看下面的问题 如果b除a的余数为r,那么(a,b)是否等于(b,n)? 事实上,若d为a,b的公因数,即da,db,则d|a-by=r,从而d为b,r的 公因数.同理可证,r,b的公因数也是a,b的公因数.因此,a,b公因数的集合与r,b 公因数的集合相同,从而它们的最大公因数相等,即(a,b)=(b,r). 按照这种思路,我们来求(1840,667) 因为1840=667×2+506,所以(1840,667)=(667,506);又因为667=506×1+ H8■
第一讲整数的除 一拼 161,所以(667,506)=(506,161);又因为506=161×3+23,所以(506,161)=(161, 23),而(161,23)=23.因此 (1840,667)=23 这种求最大公因数的方法,叫做辗转相除法◎.它是一种古老而有效的算法.下面 我们给出辗转相除法的一般形式 设a和b为任意两个整数,且b≠0.应用带余除法,以b除a,得商q和余数n.如 果n≠0,那么再以n除b,得商qt和余数n,如果n2≠0,再以n除n,如此继续下去, r(=1,2,…)越来越小,有限次这种除法后,必然得到一个余数rn≠0,它整除前一个 余数r1.于是,我们有: hg+r b=ng+r y-2=ra-19+r t-IMat 即 b)=(b,n1)=(n,r2)=…=( )=(0,rn) 也就是说,r是a,b的最大公因数 上述辗转相除法的过程可用下面的程序框图表示: 开始 输人ab ①总可假定b为 正整数 种整数运算 r MOD(a, b) h=r 符号,表示a除 以b的余数 否 是 输出b3 ③b为所求最大公 因数 结束 0这种算法是欧几里得在公元前300年左右提出的,因此又叫欧几里得算法
CHAPTER 通高中课程标雉实验教科书数学(选修46)初等数论初步」 操宠 你能根据上面的程序框图,编写一个计算机程序,求两个整数的最大公因数吗? 国° 下面探讨三个整数的最大公因数的求法 探冕 1.自己列举几组整数a,bc,计算并比较(a,b,c),(a,b)·c),从中你能: 发现什么规律? 2.求三个整数的最大公因数与求两个整数的最大公因数之间有什么联系? 我们发现,无论怎样选取a,b,c,恒有 (a,b,c)=((a,b),c). 这表明,求三个整数的最大公因数,总可以转化为求两次两个整数的最大公因数 对于多于三个整数的最大公因数,我们也有类似的结论. 关于最大公因数,有一条重要的性质.这条性质在求解一次同余方程和不定方程时经 常要用到 设整数a,b不同时为零,则存在一对整数m,n,使得(a,b)=am+bm 你能用辗转相除法证明上述性质吗? 下面我们给出它的证明 证明:不妨设b>0,用b除a,则 +n(0≤n<b 因为(a,b)=(b,n),若n=0,则 b)=(b,n1)=b. 此时取m=0,n=1,即有 ,b)=b=a×0+b×1. 若n≠0,用n除b,则 b=rq+n2(0≤n2<n) 且 若n2=0,则 (a,b)=(n,n2) 此时取m=1,m=-q,即有 (a,b) a×1+b 若n≠0,用n除r,则 10
第一讲数的 n=r2q+r(0≤n<n2), 且 (n1,n2)=(n,r) 若n=0,则 (a, b=(n, ra)=n=b-n=b-(a-INn )q ax(-q:)+b×(1+qq) 此时取m=-q,n=1+qq,即有 (a,b)=a×(-q2)+b×(1+qq). 若n≠0,再用n除n2,依次类推 由上可知,这样的m和n是存在的 这个性质对多于两个整数情形仍然成立,由它还可以推出整除的一条重要性质 若a|b,且(a,b)=1,则alc 下面我们给出它的证明. 证明:因为(a,b)=1, 所以存在一对整数m,n,使得am+bm=1. 于是(ac)m+(bc)n=c 又因为alac,allk, 所以a|(ac)m+(bc)n,即alc. 由整除的上述性质,我们可以得出素数的一条重要性质 设p为素数,若pab,则p|a,或p| 下面我们给出它的证明 证明:因为P为素数,其正因数只有1,p,所以 p 或(p,a)=p 若(p,a)=1,则由上面整除的性质知 PIb. 若(p,a)=p,则p|a 素数的这条性质可以推广到一般情形:设p为素数,若p|aa2…a,则存在a,(1≤ 5k),使得p|a 你能给出它的证明吗? 2.最小公倍数 甲、乙两个齿轮互相啮合,齿数分别为84,36,在转动过程中同时啮合 的两齿到下次再同时啮合,甲、乙两个齿轮分别转过多少圈? ■■11晶
CHAPTER 却通高中课程标准实验教科书数学(选修46)初等数论初步 这个问题的实质是,求出一个最小正整数,它同时为84.36的倍数 事实上,任给两个非零整数a,b,一定存在一个整数,它同时为a,b的倍数,这个 倍数叫做a,b的公倍数.例如,ab|就是a,b的一个公倍数 我们把a,b的最小的正公倍数叫做a,b的最小公倍数,记作[a,b1 例如,8,-6的公倍数为24,-24,48,-48,72,-72,…其中最小的正公倍数 为24,因此[8,-6]=24. 类似地,我们还可以定义三个非零整数或更多个非零整数的最小公倍数的概念,将非 零整数a,b和c的最小公倍数记作[a,b,c],依此类推 下面我们证明两个非零整数a,b的最小公倍数a,b一定整除a,b的公倍数 证明:设a,b=m,n为a,b的任意一个公倍数 对n,m用带余除法:n=mq+r(0≤r<n) 假设m不能整除n,则r>0 由am,blm,aln,bln,得 a n-mq=r, b n-m=r, 所以r也是a,b的一个正公倍数,而r<m,这与m=[a,b矛盾 因此,m1n. 日,日日图,图图BBB 对于非零整数a,b,我们研究了(a,b),[a,b]的一些性质,那么a,b b),[a,b]这些数之间有什么关系呢 选取几组非零整数a,b,分别计算并观察(a,b),[a,b]和mb,并观察这三个 数之问的关系, 我们发现,(a,b),[a,b和ab之间存在下面的关系: Ka, bLa, b]=labl 上述关系的证明此处略 由上述关系可知,可以由两个非零整数乘积的绝对值除以它们的最大公因数求得它们 的最小公倍数 例4求[375,105]的值 解:因为375=105×3+60, 05=60×1+45 60=45×1+15, 15=15×3 所以 (375,105)=15. 1112四