初等数论期末复习资料.doc

数论教案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,0r b. (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是素数； L L现在表中剩下的就全为素数了: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 函数x,x及其应用1. 函数x,x的定义定义1 设x是实数,以x表示不超过x的最大整数，称它为x的整数部分，又称x = x - x为x的小数部分。例1 3.5=3,-3.5=-4,-0.1=-1,0.1=0,=3,-=-4.性质 设x与y是实数,则(1)xyxy；(2)若m是整数,m+x=m+x；(3)若0x0,则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,(x,y)=1,2 |x (2)一切正整数解可由下式表出：x=2ab,y=,z= (3)其中ab0,(a,b)=1,a,b一奇一偶. (4) a=2,b=1,x=4,y=3,z=5; a=3,b=2,x=12,y=5,z=13; a=4,b=1,x=8,y=15,z=17; a=4,b=3,x=24,y=7,z=25; a=5,b=2,x=20,y=21,z=29; a=5,b=4,x=40,y=9,z=41.2.其它不定方程例3 求不定方程的全部整数解 xy=6, xy-x+y-4=0.解 x=1且y=6,或x=6,且y=1,或x=2,且y=3,或x=3,且y=2。原方程可变为(x+1)(y-1)-3=0,即(x+1)(y-1)=3.所以有x+1=1且y-1=3,或x+1=3,且y-1=1.故得不定方程的全部整数解为x=0,y=4;x=-2,y=-2;x=2,y=2,x=-4,y=0.作业:1.写出不定方程的满足x0,y0,z0,(x,y)=1,2 |x的2组正整数解。2.求不定方程xy-x-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 若变量x取整数时,多项式P(x)=的值总为整数,则称P(x)为整值多项式.证明,是整值多项式.证明 2730=235713,当x取整数值时,由费尔玛定理,(mod13),即13|.(mod7),即7|.(mod5),即5|.(mod3),即3|.(mod2),即2|.因2,3,5.7.13两两互质,由整除的性质知,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(x)=,这里,i=0,1,n.m是正整数,则称 f(x)=0(modm). (1)为同余式,或模m的同余方程.若0(modm),n称为同余方程(1)的次数.若aZ而且f(a)0(modm),则称xa(modm)为同余方程(1)的解.例1 f(x)=0(mod5)是模5的2次同余方程,由于f(1)=50(mod5),因此x1(mod5)是同余方程的一个解.另外x x=，,t=0,1,2, (mod5)也是同余方程的一个解.2一次同余方程一次同余方程的一般形式：axb(modm),a0(modm) (2)例如 2x3(mod5), 4x8(mod7), 3x9(mod11),定理1 同余方程(2)有解的充分必要条件是,(a,m)|b.而且当(2)有解时,(2)对模m来说有(a,m)个解. 证明 (2)有解的充分必要条件是ax-my=b有整数解,充分必要条件是(a,m)|b.设d=(a,m),如果(2)有解,则满足(2)的一切整数可以写成x=,t=0,1,2,但对模m来说,这些整数可以写成x(modm),t=0,1,2,d-1.而它们关于模m 两两不同余.例2 解一次同余方程2x+60 (mod4),解 因(2,4)|6,由定理1,同余方程有(2,4)=2个整数解.设2x-4y=-6,则x-2y=-3,由此可得x=-1+2t,tZ,所以同余方程的结为x-1+2t(mod4),t=0,1.即x