第三节最大公约数与最小公倍数ppt课件.ppt

第三节,最大公约数与最小公倍数,一、最大公约数,二、最小公倍数,三、最大公约数与最小公倍数的性质,2022/12/11,1,皖西学院 数理系,一、最大公约数,由定义可以得到的两个结论：,1.定义,2022/12/11,2,皖西学院 数理系,定理1.3.1 若a=bq+c (a, b, c Z),则(a, b)=(b, c),证明：设d |a, d |b,则的d |bq.c=a-bq, d |c 即有：a, b的公约数也是b, c的公约数.同理可证b, c的公约数也是a, b的公约数 .这表明由a, b的全体公约数组成的集，与由b, c的全体公约数组成的集是同一个，故它们的最大公约数是同一个数，故(a, b)=(b, c) .故结论成立,2022/12/11,3,皖西学院 数理系,2.辗转相除法,每次用余数去除除数，直到余数为0停止，这种运算,方法称为辗转相除法。即有,( * ),或,2022/12/11,4,皖西学院 数理系,定理1.3.2 在上面的表达式( * )中，有：,证明：,另一方面，,2022/12/11,5,皖西学院 数理系,定理1.3.3 若a, b N+，则一定存在整数s, t Z 使得as+bt=(a, b).,特别的有：,推论1.3.4 (a, b)=1的充要条件是：存在整数s, t Z 使得 as+bt=1.,将其推广为k个的情形有：,定理1.3.5 若a1,a2, ,ak N+，则一定存在整数m1, m2, ,mk Z 使得a1m1+a2m2+akmk=(a1,a2,ak).,2022/12/11,6,皖西学院 数理系,例1 求下面各组数的最大公因数。,解：,1859 1573,1,1573,286,5,1430,143,2,286,0,注：亦可通过分解因数的方法求最大公因数.,2022/12/11,7,皖西学院 数理系,例2 对于任意的整数n,求证：,是既约的真分数.,证明：14n+8=(12n+7)1+2n+1 12n+7=(2n+1)6+1,故当nN+时，,是既约分数.,(14n+8,12n+7)=(12n+7,2n+1) =(2n+1,1)=1,2022/12/11,8,皖西学院 数理系,定义1.5 整数a1, a2, , an的公共倍数称为a1, a2, , an的公倍数。a1, a2, , an的正公倍数中的最小的一个叫做a1, a2, , an的最小公倍数，记为a1, a2, , an.,由定义1.5可知：() a, 1 = |a|，a, a = |a|；() a, b = b, a；() a1, a2, , ak = |a1|, |a2| , |ak|；() 若ab，则a, b = |b|.,二、最小公倍数,2022/12/11,9,皖西学院 数理系,定理1.3.6 (a1,a2,ak)=D的充分必要条件是： (1) D | ai (i=1,2,k); (2) 若d | ai ,则 d | D (i=1,2,k).,证明 （充分性证明）D | ai (i=1,2,k);D是a1,a2,ak的公约数，由定理1.1.1(8)和条件(2)知，对a1,a2,ak的任意公约数d，有d D ，故有：(a1,a2,ak)=D,（必要性证明）若(a1,a2,ak)=D，由公约数的定义知(1)成立；若d | ai (i=1,2,k)，由定理1.3.3的推论1可知，存在mi (i=1,2,k)使a1m1+a2m2+akmk=(a1,a2,ak)，从而d | D ，所以（2）成立,三、最大公约数与最小公倍数的性质,2022/12/11,10,皖西学院 数理系,定理1.3.7 (a1, a2, , ak)=d 的充分必要条件是：,定理1.3.8 (a1, a2, , ak)=d,且mZ+, c | ai (i=1,2,k),则有：,定理1.3.9 a1, a2, , ak=m 的充分必要条件是：,2022/12/11,11,皖西学院 数理系,定理1.3.10 对任意的正整数a，b，有,证明： 设m是a和b的一个公倍数，,那么存在整数k1，k2，使得m = ak1，m = bk2，,因此 ak1 = bk2 .,特别的,2022/12/11,12,皖西学院 数理系,推论1 两个整数的任何公倍数一定是最小公倍 数的倍数.,推论2 设m，a，b是正整数，则ma, mb = ma, b.,2022/12/11,13,皖西学院 数理系,定理1.3.11,注：把多个整数的公倍数化为两个数的公倍数来计算.,推论 若m是a1, a2, , an的公倍数，则a1, a2, , anm .,2022/12/11,14,皖西学院 数理系,例5 求（36, 108, 204）和36, 108, 51.,解：(36, 108, 204)=4(9, 27, 51)=43(3, 9, 17) =12(3, 9), 17)=12(3(1, 3),17)=12(3, 17) =121=12,36, 108, 204=312, 36, 17=312, 36, 17 =312(1, 3), 17=336,17=33617 =1836,注： 上述方法实际上是小学课本介绍的短除法.,2022/12/11,15,皖西学院 数理系,定理1.3.12 整数a1, a2, , an两两互素，即(ai, aj) = 1，1 i, j n，i j 的充要条件是,a1, a2, , an = a1a2an .,例6 设a，b，c是正整数，证明 a, b, c(ab, bc, ca) = abc 。,证：a, b, c = a, b, c =,(ab, bc, ca) = (ab, (bc, ca) = (ab, c(a, b),代入即得证.,2022/12/11,16,皖西学院 数理系,定理1.3.13 如果a |bc，且(a, b)=1,则有：a |c.,证明： a |bc，b |bc， bc 是a, b 的公倍数.(a, b)=1 a, b=ab(定理1.3.12的推论）则有： ab |bc,b0 a |c,定理1.3.14 若(a, b)=1,则有(a, bc)=(a, c).,推论1 若(a, bi)=1 (i=1, 2, , k), 则有(a, b1b2bk)=1.,推论2 若(ai, bj)=1 (i=1, 2, , n, j=1, 2, , n), 则有:,2022/12/11,17,皖西学院 数理系,推论3 若n N+ , (a, b)=1, 则有 (an, bn)=1.,定理1.3.15 若a |c, b |c, (a, b)=1,则有ab |c.,例7 已知a2+b2=468, (a, b)+a, b=42, 求a, b.,例8 求证：log25是无理数.,例9 设自然数A=10 x+y(y是A的个位数字，x是非负整数)，则10n-1|(x+ny)(nN+).并用此法判断21498能否被19整除，21498能否被29整除.,2022/12/11,18,皖西学院 数理系,2022/12/11,皖西学院 数理系,19,内容小结,1. 最大公约数；,3. 最大公约数与最小公倍数的性质；,作业 P17 2 (1),(3) ,(5); 4; 7; 9; 11 ; 12,2. 最小公倍数；,