发布时间 : 星期三 文章初等数论期末复习资料更新完毕开始阅读9f5b262a6c175f0e7dd13714
证明 如果d=(a,b),由性质2有u,v∈Z使得au+bv=d.设s是a,b的任一公因数,则s|au,s|bv,且s|au+bv,即s|d.
ab,性质2如果d=(a,b),则(
dd)=1.
性质3如果(a,c)=1,且c|ab,则c|b. 性质4如果(a,c)=1,则(ab,c)=(b,c). 性质5如果(a,b)=1,且a|c,b|c,则ab|c. 例3证明 三个连续整数的积一定可被6整除. 2最小公倍数
定义 如果m是
a1,a2,?,an中每一个数的倍数,则称m是整数
a1,a2,?,an的一个公倍数.a1,a2,?,an的公倍中最小正整数称为a1,a2,?,an的最小公倍数.用
[
a1,a2,?,an]来表示.
a1,a2,?,an]=[|a1|,|a2|,?,|an|].
例如 [2,4,-3]=12,[15,12,20]=60,[6,10,15]=30.
定理3 [
定理4 设a,b是两个正整数,则 (i)a,b的任一公倍数是[a,b]的倍数；
ab(ii)[a,b]=
(a,b).而且若(a,b)=1,则[a,b]=ab.
证明(i)设m是a,b的任一公倍数,而且m=t[a,b]+r,0?r<[a,b]
,因m,[a,b]都是a,b的公倍数,由r=m-t[a,b]知r也是a,b的公倍数,若0 a[a,b]ab?(ii)记d=,则d是整数,由a|[a,b],a|[a,b]及 [a,b]db, b[a,b]?da知d|a,d|b,即d是a,b的公因数. ababdabba??Z?a?b 设h是a,b的任一公因数,由,所以h|d, hhh是a,b的公倍数及TH16知[a,b]|h,即[a,b]hh 5 ab(a,b)=d,从而(a,b)= [a,b]. 定理5 设 a1,a2,?,an都是正整数,令 [a1,a2]?m2,[m2,a3]?m3,?,[mn?1,an]?mn,则[a1,a2,?,an]?mn. 定理19设 a1,a2,?,an是n(?2)个正整数,且两两互素,则 [a1,a2,?,an]?a1a2?an 例2 求[123,456,-789] 例3 求正整数a,b,满足:a+b=120,(a,b)=24,[a,b]=144. abc例14设a,b,c是正整数,则[a,b,c]= (ab,bc,ca) 作业:P14:1. 2.求(84,45),并求整数u,v使得84u+45v=(84,45) . §4质数 算术基本定理 1.质数 定义设整数a>1,如果a除了1和a外再无其它正因数,则称a为质数,也称为素数.否则,称a为合数. 2,3,5,7,11都是质数，4,6,8,9,10都是合数. 1-100内有素数25个,1-1000内有素数168个,1-10000内有素数1229,10万内有素数9592个,100万之内78498个. 定理1设整数a>1,则a除1外的最小正因数q是素数,而且当a是合数时,q? a. 证明 假定q是合数,设q=bc,1 若a是合数,设a=qm,由q的最小性知a=qm?qq,即q? a. 6 素数判定定理 设整数a>1,不超过 a所有素数为p1,p2,?,pk,如果pi?a,i=1,?,k,则a为素数. 例1 以下正整数哪个是素数？哪个是合数？ 231,89,103,169. 素数判别威尔逊定理:设整数p>1,那么p是素数的充分必要条件是 p|(p-1)!+1. 例2 利用威尔逊定理判别3,5,7,11都是素数. 当p较大时,(p-1)!+1的数值非常大,在实际运用时不可行。 定理2 设P是素数,a为任一整数,则或P|a,或(P,a)=1. 证明 因(P,a)|P,P为素数,所以(P,a)=P,或(P,a)=1.即P|a,或(P,a)=1. 2.整数的唯一分解定理 ?定理3 任何a>1的整数都有标准分解式:a=p11p?22?p?kk (3) 这里 p1,p2,?,pk为不同素数,整数?i?0,i=1,?,k. p??1 若正整数 a>1 的标准分解式为 a= 12?推论 k1p2?pk,则a的正因数?1?2?kd= p1p2?pk,0??i??i,i=1,?,k.而且a有不同的正因数(1??1)(1??2)?(1??k)个. ?推论2设a= p11p?22?p??1?2?kkk,b= p1p2?pk,?i?0,?i?0,i=1,?,k. 则 ?1?2?kp??(1)(a,b)=p1p2?pk,[a,b]= 11p22?p?kk， 其中?i?min(?i,?i),?i?max(?i,?i),i=1,?,k. (2)a,b共有正公因数(1??1)(1??2)?(1??k)个; (3)a,b共有公因数 2(1??1)(1??2)?(1??k)个. 例3 求725760,154200的标准分解式,并求它们的最大公因数和最小公倍数. 解 因725760=28×5×11×41, 154200=23×3×52×257, 所以(725760,154200)= 23×5, [725760,154200]=282×3×5×11×41×257. 7 d为 例4求下列各组数的最大公因数及其公因数的个数: (1)123,78；(2)120,54. 练习:求下列各组数的最大公因数及其公因数的个数: (1)125,70；(2)140,56. 22例8设p,q都是大于3的素数,证明24|. p?q3质数的多少和质数的求法 定理4 素数有无穷多个. 证明 反证法,设质数只有k个: p1,p2,L,pk,令M?p1p2Lpk?1, M>1,于是M有素数因数p.因 pi?M,i=1,2,?,k,p|M,所以p≠pi,i= 1,2,?,k.这就是说, p1,p2,L,pk,p是k+1个不同素数.这与假设矛盾. 1-n之间的所有素数怎样求出来？ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 按以下步骤进行： (1)删去1，剩下的后面的第一个数是2，2是素数； (2)删去2后面被2整除的数(从4开始),2后面剩下的第一个数3是素数； (3)删去3后面的被3整除的数(从9开始),3后面剩下的第一个数5是素数； (4)删去5后面的被5整除的数(从25开始),5后面剩下的第一个数7是素数； ? ? 现在表中剩下的就全为素数了: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97. 对较小范围内的素数以上求法方便,对较大范围内的素数,需要编程求素数了. 现在运行程序,求较大范围内的素数.找两个同学来求. 作业:1.判别1577是否为素数;2.P19:5t； 8