初等数论期末复习资料

1、数论教案1整数的整除带余除法1整数的整除设a,b是整数，且bw0,如果有整数q,使得a=bq,则称b整除a,记为b|a,也称b是a的因数,a是b的倍数.如果没有整数q,使得a=bq,则称b不能整除a,记为b?a.例如2|4,4|-12,-5|15;2?3,-3?22.在中小学数学里，整除概念中的整数是正整数，今天讲的整除中的整数可正可负.判断是否b|a?当a,b的数值较大时，可借助计算器判别.如果b除a的商数是整数，说明b|a;如果b除a的商不是整数，说明b?a.例1判断下列各题是否b|a?(1)7|127?(2)11|129?(3)46|9529?(4)29|5939?整除的简单性质(1)如

2、果c|b,b|a,那么c|a;(2)如果d|a,d|b,那么对任意整数m,n,都有d|ma+nb.如果aha2,L,an 都是m的倍数，q1，q2,L,qn 是任意整数，那么qeq2a2Lqnan 是m的倍数.(4)如果c|a,d|b,那么cd|ab。例如：2|4,2|(-6),那么2|4+(-6),2|4-(-6).2|4,3|(-6),那么2X3|4X(-6).例2证明任意2个连续整数的乘积，一定可被2整除.练习证明任意3个连续整数的乘积，一定可被3整除.2.带余除法设a,b是整数，且b0,那么有唯一一对整数q,r使得a=bq+r,0rb.(1)这里q称为b除a的商,r称为b除a的余数.例

3、如-5=3义(-2)+15=3义1+2-5=(-3)义2+15=(-3)X(-1)+215=(-5)X(-3),-24=(-2)X12.事实上，以b除a的余数也可以是负的.例如-5=3(-1)-2=3(-2)+1.求b除a的余数，也称为模运算(取余):mod.可用计算器进行.具体操作:输入a-按mod(取余)键-输入b-按二键得出余数.如果b除a的余数=0,则b|a;如果b除a的余数 w0,则b?a.例3利用计算器求余数：(1)7除127;(2)11除-129;(3)46除-9529;(4)-29除5939奇数、偶数及性质能被2整除的整数称为偶数.如,0,4,10,-6,-8都是偶数.不能被2

4、整除的整数称为奇数.如,-5,-3,1,7,11都是奇数.偶数的形式为2n(n是整数);奇数的形式为2n-1(n是整数).奇数、偶数的性质：偶数土偶数=偶数，奇数土奇数=偶数,奇数土偶数=奇数，偶数x偶数=偶数，偶数x奇数=偶数,奇数x奇数=奇数.例如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,22例4设a,b,n是任意3个整数，而且ab2n,证明n是偶数.一、一，例5设a是任一奇数，试证明8|a1.例6设n是正整数，证明形如3n-1整数不是完全平方数.证明对任意整a,设a=3q或a=3q1,于是 2_22

5、22a=9q或a=9q6q+1=3(3q2q)+1.2即a*3n-1,故3n-1不是完全平方数.练习设n是正整数，证明形如4n-1、4n+2的整数都不是完全平方数.习题:P3-4:1t,2t.2公因数、最大公因数1.最大公因数、辗转相除法中小学里的公因数、最大公因数的概念：几个数的公有因数叫做这几个数的公因数.公因数中最大的整数称为这几个数的最大公因数.(1)几个数:不能确定;(2)因数、公因数：都是正整数；最大公因数：没有专门的符号.定义设al,a2,La,d都是整数,dW0,如果dai,i=1,2，,n,称d是a1，a2,L,an的公因数，aa2,L,an的公因数中最大的整数称为最大公因数

6、.记为(ae,L自).如果(a,a,L,&)=1,则称国电L,%互质。例1(-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小学数学里，求正整数a,b的最大公因数主要有这个样几种方法：(1)观察法；(2)将a,b的所有公因数都求出来，再从中挑最大的；(3)用短除法.辗转相除法：设a,b是正整数，而且有abqri,0rb;b用2吼0r2兄rir2cbr3,03R;(*)玲2rnicnrn,0r1rli；rn1rnCn1.(a,b)j例2用辗转相除法求(123,78),练习:用辗转相除法求(66,54).下面说明辗转相除法的正确性.先证明性质1设整数a,b,c不

7、全为0,而且有整数q使彳3a=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)0.(短除法的根据)例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,-9

8、6).3n1例5设n是任意整数，证明是既约分数.5n2证明设d=(3n+1,5n+2),WJd|3(5n+2)-5(3n+1),即d|1,d=1,所以3n+1与5n+2互质.作业1.利用辗转相除法求(84,90).2.求(120,36).3n13.设n是整数，证明力是既约分数。3整除的进一步性质及最小公倍数1.整除的进一步性质推论1设a,b不全为零，那么有s,teZ使得as+bt=(a,b).由(*)式知br12Lrn1rn0,而n是有限正整数，再由性质1得证明将(*)中每式中的余数解出得n72r0iQn,n1n3721,r2b用2,1abq,再将例1用辗转相除法求(120,54),并求整数u

9、,v使得120u+54V=(120,54).解120=2X54+12,54=12X4+6,12=6X2,.(120,54)=6.12=120-2X54,6=54-12X4=54-(120-2X54)X4=120X(-4)+54X9.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

10、的因数.证明如果d=(a,b),由性质2有u,vCZ使彳#au+bv=d.设s是a,b的任一公因数，则s|au,s|bv,且s|au+bv,即s|d.ab性质2如果d=(a,b),则(,1)=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最小公倍数n1,n,L,r2,r1的表达式依次代入到n。2。14中就得au+bv=n=(a,b)=d,u,vZ乙定义如果m是司,%,1,an中每一个数的倍数，则称m是整数ai,a2,L,an的一个公倍数.

11、ab%。,斗的公倍中最小正整数称为ai,a2,L,an的最小公倍数.用,L,1来表示.例如2,4,-3=12,15,12,20=60,6,10,15=30.定理3a1,a2,L,an=|a1|,|a2|,an|.定理4设a,b是两个正整数，则(i)a,b的任一公倍数是a,b的倍数;ab(ii)a,b=(ab).而且若(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的公倍数，若0r2)个正整数，且两两互素，则a&L,anaLa例2求123,456,-789例3求正整数

12、a,b,满足:a+b=120,(a,b)=24,a,b=144.作业:P14:1.2.求(84,45),并求整数u,v使得84u+45v=(84,45)4质数算术基本定理1.质数定义设整数a1,如果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是合数时,qJ.证明假定q是合数，设q=bc,1b,cq.因b|q,q|a,得b

13、|a,但1bqq,即q003.素数判定定理设整数a1,不超过所有素数为Pl,P2,L,Rc,如果R?a,i=1,k,则a为素数.例14设a,b,c是正整数，则a,b,c=abc(ab,bc,ca例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,或(

14、P,a)=1.2.整数的唯一分解定理这里pl,p2,L,pc为不同素数，整数i0,i=1,k.一1-2|一k推论1若正整数a1的标准分解式为a=p1p2Lpk，则a的正因d=P/P22LPkk,0ii,i=1,k.而且a有不同的正因数(11)(12)L(1k)个.推论2设2=P11P22LPkk,b=P11P22LPkk,i0,i0,i=1,k.(1)(a,b)=p1p2Lpk,a,b=plp2Lpk,其中imin(i,i),imax(i,k.(2)a,b共有正公因数(11)(12)L(1k)个；(3)a,b共有公因数2(11)(12)L(1k)个.例3求725760,154200的标准分解式

15、，并求它们的最大公因数和最小公倍数O8o3八K2八一解因725760=2X5X11X41,154200=2X3X5X257,定理3任彳a1的整数都有标准分解式：a二PI1p22Lpkk所以(725760,154200)=2X5,725760,154200=28X3X52xi1X41X257例4求下列各组数的最大公因数及其公因数的个数(1)123,78;(2)120,54.练习:求下列各组数的最大公因数及其公因数的个数：(1)125,70;(2)140,56.22例8设p,q都是大于3的素数，证明24|Pq3质数的多少和质数的求法定理4素数有无穷多个.证明反证法，设质数只有k个:R,P2,L,P

16、k,令MP1P2LPkM1,于是M有素数因数p.因Pi?M,i=1,2,k,p|M,所以pwPi,i=1,2,k.这就是说，p1,P2,L,P1-n之间的所有素数怎样求出来？123451112131415212223242531323334354142434445515253545561626364657172737475,p是k+1个不同素数.这与假设矛盾678910161718192026272829303637383940464748495056575859606667686970767778798081828384858687888990919293949596979899100按以下

17、步骤进行：(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.P

18、19:5t;3.求725760,154200的标准分解式，并求它们的最大公因数和最小公倍数，并求它们的所有公因数的个数。5函数x,x及其应用1 .函数x,x的定义定义1设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，又称x=x冈为x的小数部分例13.5=3,-3.5=-4,-0.1=-1,0.1=0,=3,-=-4.性质设x与y是实数，则(1)xyxy；(2)若m是整数，mx=mx；(3)若0 x0,则a=braarab，故g=q,b，所以a=b-b+baab,2b,3b,，因此，若数1,2,a中能被b整除的整数有k个，则kba(k+1)bk7k+1k=；.bb10150099例2

19、不超过101且是5的倍数的正整数有-5=20个,100-500的整数中7的倍数的正整数有-H=71-14=57.2,函数x的应用kk1设P是素数,n是整数，如果p1n,p定理1在n!的标准分解式中，质因数p的指数是nn2+-3+,PP证明在1,2,3,n中,nn恰被P整除的整数有一-。个；(5)设a与b是正整数，则1-a中能被b整除的整数有；个。b3ba.bba设a=bqr,0r2是整数Th1不定方程(1)有整数解充分必要条件是，(ai,a2,L,an)|N.例1求9x+24y-5z=1000的一切整数解.解因(9,24,-5)=1,所以不定方程有整数解，因(9,24)=3,可设9x+24y=

20、3u,于是3x+8y=u,3u-5z=100的通解为x=u-8s,y=-u+3s,sZ,的通解为u=5t,z=-20+3t,tZ.故原不定方程的通解为x=5t-8s,y=-5t+3s,z=-20+3t,s,tZ.例2把17/60写成分母两两互质的三个既约分数之和.17xyz解因60=3X4X5，设 60345,整理得20 x+15y+12z=17.因(20,15,12=1,不定故方程有整数解，设20 x+15y=5u,则4x+3y=u,5u+12z=17.的通解为x=u-3s,y=-u+4s,sCZ,的通解为u=1-12t,z=1+5t,tZ.故原不定方程的通解为x=1-12t-3s,y=-1

21、+12t+4s,z=1+5t,s,t112t4s15t45.当t=s=0时,x=-y=z=1,此时有作业:1求3x+6y-5z=15的一切整数解.3勾股数2221.不定方程xyz222不定方程xyz的一组整数解(x,y,z)称为一组勾股数例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股数.222定理不定方程xyz,满足x0,y0,z0,(x,y)=1,2|x(2)2,22,2一切正整数解可由下式表出：x=2ab,y=ab,z=ab(3)Z.17112t3s所以，603171160345其中ab0,(a,b)=1,a,b一奇一偶.(4)a=2,b=1,x=

22、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=111y=+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

23、,x=-4,y=0.222作业:1.写出不定方程xyz的满足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同余， 记为a=b(modm).如果a,b被m除所得的余数不同，则称a,b对模m不同余，记为a?b(modm).例如4三7(mod3),6三11(mod5),4?5(mod3),6?8(mod5).定理1整数a,b对模m同余的充分必要条件是,m|a-b,即a=b+mt,t乙证明必要性，若amb(mod

24、m).可设a=msa=r,b=mua=r,s,uCZ则a-b=m(s-u)=mt,T=s-uZ.所以m|a-b,且a=b+mt.充分性，设a=ms+r1,b=mu+r2,a-b=m(s-u)+r1-r2.因m|a-b,所以m|ri-r2M|r1-r211,(a,m)=1,则2()1(modm).证明取模m的一个简化剩余系b1，b2，,bs,(S(m)，由于(a,m)=1,由3定理3知,ab1,ab2,1abs也是模m的一个简化剩余系，于是(ab)(a)L(abs)bLbs(modm)即 a,.bbLbsbLbs(modm)因b)=1j=2 ,2，(m),所以(m,b,b2,L,b(m)=1，从

25、而a1(modm).证毕。P1P推论(费尔玛定理)设P是素数，则a1(modP)，而且aeZ,aa(modP).证明若p|a,则aa0(modP),若(a,m)=1,则&1(modp),所以paa(modP).P1q1例1设p,q是不同的素数，证明qP1(modpq).P1q1证明因p,q是不同的素数，所以(p,q)=1,由费尔玛定理知，qP1(modp),P1q1,P1q1,qp1(modq).由同余的性质得,qp1(modpq).例2设pw2,5为素数，整数a的十进制数由p-1位，而且每一位上的数字都是9,证明p|a.11一)L(1一)P2PkP1.证明因p*2,5为素数，所以(1

26、0,p)=1,由费尔玛止理得,a=99-9=101=0(modp),即p|a.例3若变量x取整数时，多项式P(x)=b0 xL 必1的值总为整数，则称p(x)113(xx)为整值多项式.证明，2730 是整值多项式.证明2730=2X3X5X7X13，当x取整数值时，由费尔玛定理，1313xx0(mod13),即13|xx.13/7613xx(xx)(x1)0(mod7),即7|xx.13/5、/84-13xx(xx)(xx1)0(mod5),即5|xx.x13x(x3x)(x10 x8x6x4x21)0(mod3),即3|x13x.x13x(x2x)(x11Lx1)0(mod2),即2|x1

27、3x.13一因2,3,5.7.13两两互质，由整除的性质知,2X3X5X7X13|xx,即2730|11313(xx)xx.故 2730 是整值多项式.IO101,例4今天是星期一，问从今天起再过10天是星期几？2233解103(mod7),1032(mod7),1032g361(mod7),所以1061(mod7)。又因10-2(mod6),102222(mod6),故10124(mod6)。1010设 10106k4,k为正整数，于是 10101010434(mod7),这就是说，从今天起再过 1。天是星期五(1+4)则称它为循环小数，并简记为0.gg对满足(*)的最小正整数t,称as1L

28、ast为循环节，称t为循环节的长度.若最小的s=0,那小数就叫做纯循环小数，否则叫做混循环小定理2有理数b,0ab,(a,b)=1,能表成纯循环小数的充分必要条件是,(b,10)=1.有理数b,0ab,(a,b)=1,是纯有限小数的充分必要条件是(b,10)w1.必要性：若有理数 b 能表成纯循环小数，则由0Vb1及定义知tb=0a1a2LataLatL=0aa2Lat+10c0.a1a2LataLatL 于是四章同余方程1基本的概念及一次同余方程推论证明qbq10t10aa2Lata1a2Lata1LatL=q+b.所以a(101)bq,因(a,b)=1,所以b110t1,设 10t充分性：

29、如果(b,10)=1,由定理1知有一正整数t使得10t1(modb),0t(b),又有(10t1)a0令q=a110t10.a1a2Latb=0.aLataL1=qb,则10qb=1,故(b,10)=1.10taa(modb),设10aqba,则q(10t1)旦 10tba210t2L10at1,又由10taqbggatL=0.a1Lat定理3有理数b,0a一，例1f(x)=xx3m0(mod5)是模5的2次同余方程，由于f(1)=5=0(mod5),因此x=1(mod5)是同余方程的一个解.另外xx=m1tX0,m1m/d,t=0,1,2,(mod5)也是同余方程的一个解.2一次同余方程一次

30、同余方程的一般形式:ax=b(modm),a/0(modm)(2)例如2xm3(mod5),4x=8(mod7),3x=9(mod11),定理1同余方程有解的充分必要条件是，(a,m)|b.而且当有解时,(2)对模m来说有(a,m)个解.证明(2)有解的充分必要条件是ax-my=b有整数解，充分必要条件是(a,m)|b.设d=(a,m),如果(2)有解,则满足(2)的一切整数可以写成x=m1tx0,m1tm/d,t=0,1,2,，但对模m来说，这些整数可以写成xm1tx0(modm),t=0,1,2,d-1.而它们关于模m两两不同余.例2解一次同余方程2x+6m0(mod4),解因(2,4)6,由定理1,同余方程有(2,4)=2个整数解.设2x-4y=-6， 则x-2y=-3， 由此可得x=-1+2t,tCZ,所以同余方程的结为-1+2t(mod4),t=0,1.即x=-1(mod4)x=1(mod4).例3解一次同余方程12x+4m0(mod8),因(12,8)=4,4|4,由定理1,同余方程有4个整数解.设12x-8y=-4,则3x-2y=-1,由此