初等数论期末复习资料

-数论教案1整数的整除 带余除法1 整数的整除设a,b是整数,且b0,如果有整数q,使得a=bq,则称b整除a,记为b|a,也称b是a的因数,a是b的倍数.如果没有整数q,使得a=bq,则称b不能整除a,记为ba.例如 2|4,4|-12,-5|15;23，-322.在中小学数学里,整除概念中的整数是正整数,今天讲的整除中的整数可正可负.判断是否b|a.当a,b的数值较大时,可借助计算器判别.如果b除a的商数是整数,说明b|a;如果b除a的商不是整数,说明ba.例1判断以下各题是否b|a.(1) 7|127 (2)11|129 (3) 46|9529 (4) 29|5939整除的简单性质(1)如果c|b,b|a,则c|a; (2)如果d|a,d|b,则对任意整数m,n,都有d|ma+nb.(3)如果都是m的倍数,是任意整数,则是m的倍数.(4)如果c|a,d|b,则cd|ab。例如： 2|4,2|(-6),则2|4+(-6),2|4-(-6). 2|4,3|(-6),则23|4(-6).例2证明任意2个连续整数的乘积,一定可被2整除.练习 证明任意3个连续整数的乘积,一定可被3整除.2.带余除法设a,b是整数,且b0,则有唯一一对整数q,r使得 a=bq+r,0rb. (1)这里q称为b除a的商,r称为b除a的余数.例如-5=3(-2)+1 5=31+2 -5=(-3)2+15=(-3)(-1)+2 15=(-5)(-3), -24=(-2)12.事实上,以b除a的余数也可以是负的.例如 -5=3(-1)-2=3(-2)+1.求b除a的余数,也称为模运算(取余):mod.可用计算器进展.具体操作:输入a-按mod(取余)键-输入b-按=键得出余数.如果b除a的余数=0,则b|a;如果b除a的余数0,则ba.例3 利用计算器求余数:(1) 7除127;(2)11除-129 ;(3)46除-9529;(4)-29除5939奇数、偶数及性质能被2整除的整数称为偶数.如,0,4,10,-6,-8都是偶数.不能被2整除的整数称为奇数.如,-5,-3,1,7,11都是奇数.偶数的形式为2n(n是整数);奇数的形式为2n-1(n是整数).奇数、偶数的性质:偶数偶数=偶数,奇数奇数=偶数,奇数偶数=奇数,偶数偶数=偶数,偶数奇数=偶数,奇数奇数=奇数.例如2+4,2-4,3+1,3-1,3+4,6+5设a,b是任意两个整数,则a+b与a-b同奇同偶.例如3+5,3-5,6+3,6-3,例4设a,b,n是任意3个整数,而且,证明n是偶数.例5设a是任一奇数,试证明8|.例6设n是正整数,证明形如3n-1整数不是完全平方数.证明 对任意整a,设a=3q或a=3q1,于是=9或 =96q+1=3(32q)+1.即3n-1,故3n-1不是完全平方数.练习 设n是正整数,证明形如4n-1、4n+2的整数都不是完全平方数. 习题:P3-4:1t,2t.2公因数、最大公因数1.最大公因数、辗转相除法中小学里的公因数、最大公因数的概念：几个数的公有因数叫做这几个数的公因数.公因数中最大的整数称为这几个数的最大公因数.(1)几个数:不能确定;(2)因数、公因数:都是正整数;最大公因数:没有专门的符号.定义设,d都是整数,d0,如果,i=1,2,n,称d是的公因数,的公因数中最大的整数称为最大公因数.记为.如果=1,则称互质。例1 (-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小学数学里,求正整数a,b的最大公因数主要有这个样几种方法：(1)观察法；(2)将a,b的所有公因数都求出来,再从中挑最大的；(3)用短除法.辗转相除法:设a,b是正整数,而且有 *。例2用辗转相除法求(123,78),练习:用辗转相除法求(66,54).下面说明辗转相除法的正确性.先证明性质1设整数a,b,c不全为0,而且有整数q使得a=bq+c则(a,b)=(b,c).证明 由a,b,c不全为0知,(a,b)、(b,c)都存在.因(a,b)|a,(a,b)|b,c=a-bq,得(a,b)|c,又得(a,b)(b,c);反之,由(b,c)|b,(b,c)|c,a=bq+c,得(b,c)|a,(b,c)(a,b).所以(a,b)=(b,c). 由(*)式知而n是有限正整数,再由性质1得=.2.最大公因数的性质最大公因数的几个性质：性质2 (am,bm)=(a,b)m,m0.(短除法的根据)例3求(84,90),(120,36).(84,90)=3(28,30)=6(14,15)=6.(120,36)=12(10,3)=12.性质3 (a,b)=(|a|,|b|).性质4 (a,b,c)=(a,b),c).例4求(-84,120),(-120,-72),(24,-60,-96).例5设n是任意整数,证明是既约分数.证明 设d=(3n+1,5n+2),则d|3(5n+2)-5(3n+1),即d|1,d=1，所以3n+1与5n+2互质.作业 1.利用辗转相除法求(84,90).2.求(120,36). 3.设n是整数，证明是既约分数。3整除的进一步性质及最小公倍数1.整除的进一步性质推论1设a,b不全为零,则有s,tZ使得as+bt=(a,b).证明 将(*)中每式中的余数解出得,再将的表达式依次代入到中就得au+bv=(a,b)=d,u,vZ.例1用辗转相除法求(120,54),并求整数u,v使得120u+54v=(120,54).解120=254+12,54=124+6,12=62,(120,54)=6.12=120-254,6=54-124=54-(120-254)4=120(-4)+549. u=-4,v=9.练习用辗转相除法求(84,45),并求整数u,v使得84u+45v=(84,45).设a,b都是正整数,问a,b的公因数与最大公因数有什么关系. 例2求(12,18)及12与18的所有正的公因数；通过这个例子,请同学们观察最大公因数与公因数有何关系.能否提出自己的猜想.能否证明自己的猜想.性质1设d 是a,b的最大公因数,则,a,b的任一公因数都是d的因数.证明 如果d=(a,b),由性质2有u,vZ使得au+bv=d.设s是a,b的任一公因数,则s|au,s|bv,且s|au+bv,即s|d.性质2如果d=(a,b),则()=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是中每一个数的倍数,则称m是整数的一个公倍数.的公倍中最小正整数称为的最小公倍数.用来表示. 例如 2,4,-3=12,15,12,20=60,6,10,15=30. 定理3 =|,|,|.定理4 设a,b是两个正整数,则(i)a,b的任一公倍数是a,b的倍数；(ii)a,b=.而且假设(a,b)=1,则a,b=ab.证明(i)设m是a,b的任一公倍数,而且m=ta,b+r,0ra,b,因m,a,b都是a,b的公倍数,由r=m-ta,b知r也是a,b的公倍数,假设0r1,如果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设整数a1,则a除1外的最小正因数q是素数,而且当a是合数时,q. 证明 假定q是合数,设q=bc,1b,cq.因b|q,q|a,得b|a,但1b1,不超过所有素数为,如果a,i=1,k,则a为素数. 例1 以下正整数哪个是素数.哪个是合数. 231,89,103,169.素数判别威尔逊定理:设整数p1,则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 任何a1的整数都有标准分解式:a=(3)这里为不同素数,整数,i=1,k.推论1 假设正整数a1的标准分解式为a=,则a的正因数d为d=,i=1,k.而且a有不同的正因数个.推论2设a=,b=,i=1,k.则(1)(a,b)=,a,b=，其中,i=1,k.(2)a,b共有正公因数个;(3)a,b共有公因数个. 例3 求725760,154200的标准分解式,并求它们的最大公因数和最小公倍数.解 因725760=51141, 154200=3257,所以(725760,154200)=5, 725760,154200=31141257.例4求以下各组数的最大公因数及其公因数的个数:(1)123,78；(2)120,54.练习:求以下各组数的最大公因数及其公因数的个数:(1)125,70；(2)140,56.例8设p,q都是大于3的素数,证明24|.3质数的多少和质数的求法定理4 素数有无穷多个.证明 反证法,设质数只有k个:,令,M1,于是M有素数因数p.因M,i=1,2,k,p|M,所以p,i=1,2,k.这就是说,p是k+1个不同素数.这与假设矛盾.1-n之间的所有素数怎样求出来.1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 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是素数；LL现在表中剩下的就全为素数了: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；3.求725760,154200的标准分解式,并求它们的最大公因数和最小公倍数,并求它们的所有公因数的个数。5 函数*,*及其应用1. 函数*,*的定义定义1 设*是实数,以*表示不超过*的最大整数，称它为*的整数局部，又称* = * - *为*的小数局部。例1 3.5=3,-3.5=-4,-0.1=-1,0.1=0,=3,-=-4.性质 设*与y是实数,则(1)*y*y；(2)假设m是整数,m+*=m+*；(3)假设0*0,则a=b+b.设a=bq+r,0rb得,故=q,所以a=b+b.(5)设a与b是正整数,则1-a中能被b整除的整数有个。证明 能被b整除的正整数是b,2b,3b,L,因此,假设数1,2,L,a中能被b整除的整数有k个,则kba(k+1)bk0,y0,z0,(*,y)=1,2 |* (2)一切正整数解可由下式表出：*=2ab,y=,z= (3)其中ab0,(a,b)=1,a,b一奇一偶. (4) a=2,b=1,*=4,y=3,z=5; a=3,b=2,*=12,y=5,z=13; a=4,b=1,*=8,y=15,z=17; a=4,b=3,*=24,y=7,z=25; a=5,b=2,*=20,y=21,z=29; a=5,b=4,*=40,y=9,z=41.2.其它不定方程例3 求不定方程的全部整数解 *y=6, *y-*+y-4=0.解 *=1且y=6,或*=6,且y=1,或*=2,且y=3,或*=3,且y=2。原方程可变为(*+1)(y-1)-3=0,即(*+1)(y-1)=3.所以有*+1=1且y-1=3,或*+1=3,且y-1=1.故得不定方程的全部整数解为*=0,y=4;*=-2,y=-2;*=2,y=2,*=-4,y=0.作业:1.写出不定方程的满足*0,y0,z0,(*,y)=1,2 |*的2组正整数解。2.求不定方程*y-*-y-4=0的全部整数解.第三章 同 余1同余的概念及其性质1.同余及性质定义 设m是正整数,称m为模.a,bZ,如果a,b被m除所得的余数一样,则称a,b对模m同余,记为ab(modm).如果a,b被m除所得的余数不同,则称a,b对模m不同余,记为ab(modm).例如 47(mod3),611(mod5),45(mod3),68(mod5).定理1 整数a,b对模m同余的充分必要条件是,m|a-b,即a=b+mt,tZ.证明 必要性,假设ab(modm).可设a=msa=r,b=mua=r,s,uZ,则a-b=m(s-u)=mt,T=s-uZ.所以m|a-b,且a=b+mt.充分性,设a=ms+,b=mu+,a-b=m(s-u)+-.因m|a-b,所以m|-,但|-|1,(a,m)=1,则.证明取模的一个简化剩余系,由于(,)=1,由3定理3知,也是模的一个简化剩余系，于是,即,因(m,)=1,i=1,2,所以(m,)=1,从而.证毕。 推论(费尔玛定理)设P是素数,则,而且aZ,.证明 假设p |a,则(modP)，假设(,)=1，则，所以. 例1 设p,q是不同的素数,证明(modpq).证明 因p,q是不同的素数,所以(p,q)=1,由费尔玛定理知,(modp),(modq).由同余的性质得,(modpq).例2设p2,5为素数,整数a的十进制数由p-1位,而且每一位上的数字都是9,证明p |a.证明因p2,5为素数,所以(10,p)=1,由费尔玛定理得,a=999=0(modp),即p |a.例3 假设变量*取整数时,多项式P(*)=的值总为整数,则称P(*)为整值多项式.证明,是整值多项式.证明 2730=235713,当*取整数值时,由费尔玛定理,(mod13),即13|.(mod7),即7|.(mod5),即5|.(mod3),即3|.(mod2),即2|.因2,3,两两互质,由整除的性质知,235713|，即2730|.故是整值多项式.例4 今天是星期一，问从今天起再过天是星期几.解 103(mod7),(mod7),(mod7),所以(mod7)。又因10-2(mod6),(mod6),故(mod6)。设，k为正整数,于是(mod7),这就是说，从今天起再过天是星期五1+4。例5求被8除的余数。作业:P64:1.例32.分数与循环小数定义 如果无限小数0.0,1，,9从任何一位数后不全为0,且能找到两个整数s0,t0,使得,i=1,2,t,k=0,1,2,. (*)则称它为循环小数，并简记为0. 对满足(*)的最小正整数t,称为循环节，称t为循环节的长度.假设最小的s=0,那小数就叫做纯循环小数，否则叫做混循环小数。定理2有理数,0ab,(a,b)=1,能表成纯循环小数的充分必要条件是,(b,10)=1.推论 有理数,0ab,(a,b)=1,是纯有限小数的充分必要条件是(b,10)1.证明 必要性：假设有理数能表成纯循环小数，则由01及定义知=0.=0.+.于是+0.=q+.所以,因(a,b)=1,所以b|,设=qb,则=1,故(b,10)=1.充分性：如果(b,10)=1,由定理1知有一正整数t使得(modb),0t,又有(modb),设,则,.令q=,显然不全为9,也不全为0.而且,又由得=，反复利用 即得=0.=.定理3有理数,0ab,(a,b)=1,不全为0,=1,则能表成纯循环小数.其中不循环局部的位数是,四章 同余方程1根本的概念及一次同余方程1.同余方程的概念定义 设f(*)=,这里,i=0,1,n.m是正整数,则称 f(*)=0(modm). (1)为同余式,或模m的同余方程.假设0(modm),n称为同余方程(1)的次数.假设aZ而且f(a)0(modm),则称*a(modm)为同余方程(1)的解.例1 f(*)=0(mod5)是模5的2次同余方程,由于f(1)=50(mod5),因此*1(mod5)是同余方程的一个解.另外* *=，,t=0,1,2, (mod5)也是同余方程的一个解.2一次同余方程一次同余方程的一般形式：a*b(modm),a0(modm) (2)例如 2*3(mod5), 4*8(mod7), 3*9(mod11),定理1 同余方程(2)有解的充分必要条件是,(a,m)|b.而且当(2)有解时,(2)对模m来说有(a,m)个解. 证明 (2)有解的充分必要条件是a*-my=b有整数解,充分必要条件是(a,m)|b.设d=(a,m),如果(2)有解,则满足(2)的一切整数可以写成*=,t=0,1,2,但对模m来说,这些整数可以写成*(modm),t=0,1,2,d-1.而它们关于模m 两两不同余.例2 解一次同余方程2*+60 (mod4),解 因(2,4)|6,由定理1,同余方程有(2,4)=2个整数解.设2*-4y=-6,则*-2y=-3,由此可得*=-1+2t,tZ,所以同余方程的结为*-1+2t(mod4),t=0,1.即*-1(mod4)*1(mod4).例3 解一次同余方程12*+40 (mod8),因(12,8)=4,4|4,由定理1,同余方程有4个整数解.设12*-8y=-4,则3*-2y=-1,由此可得*=-1+2t,tZ,所以同余方程的结为*-1+2t(mod4),t=0,1,2,3. 即*-1,1,35(mod8). 例4 解一次同余方程15*+60 (mod9),作业:1 解一次同余方程:12*-60(mod9).2 子定理中国古代的子算经中有物不知数：今有物不知数,三三数之剩二，五五数之剩三,七七数之剩二,问物几何.答曰二十三.设物的数量为*,则*2(mod3),*3(mod3),*2(mod7).求满足此条件的整数*.这个同余方程可推广为 *(mod), *(mod),*(mod). (1)这里,为两两互质的正整数.定理 设,为两两互质的正整数,m=.i=1,2,k.则同余方程(1)的解为*(modm).这里(mod),i=1,2,k.例1 解同余方程*(mod5),*(mod6),*(mod7),*(mod11).解m=2310=56711=5462=6385=7330=11210.解(mod), i=1,2,3,4得,.故原同余式组的解为 *=3426+385+330+210(mod2310).例2 信点兵:有兵一队,假设列成五行纵队,则末行一人,假设列成六行纵队,则末行五人, 假设列成七行纵队,则末行四人, 假设列成十一行纵队,则末行十人,求兵数.解 此时,由例1即得*=34261+3855+3304+21010=67302111(mod2310).例3 解同余方程组*2(mod3),*3(mod3),*2(mod7).解 105=357=335=521=715.由35(mod3),21(mod5),15(mod7)得,.所以原同余方程组的解为*=35(-1)2+1213+1152=23(mod105). 作业P79:1(i). z.