初等数论期末复习资料

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整除的简单性质(

2、1) 如果c|b,b|a,那么c|a;(2) 如果d|a,d|b,那么对任意整数m,n,都有d|ma+nb.如果ai,a2,L,an都是m的倍数,qi,q2,L,qn是任意整数,那么qiaiq2a2Lqnan是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是整数,且b>0,那么有唯一一对整数q,r使得a=bq+r,0<r<b.(1)这里q称为

3、b除a的商,r称为b除a的余数.例如-5=3义(-2)+15=3义1+2-5=(-3)义2+15=(-3)X(-1)+215=(-5)X(-3),-24=(-2)X12.事实上,以b除a的余数也可以是负的.例如-5=3X(-1)-2=3X(-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、,4,10,-6,-8都是偶数.不能被2整除的整数称为奇数.如,-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是偶数.2.例5设a是任一奇数,试证实8|a1.例6设n是正整数,证实形如3n-1整数不是完全平方数.证实对任意整a,设

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

6、2,L,an的公因数,a1,L,an的公因数中最大的整数称为最大公因数.记为(a,电L,an).如果(ai2,L©)=1,那么称a1,a2,L自互质.例1(-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小学数学里,求正整数a,b的最大公因数主要有这个样几种方法：(1)观察法；(2)将a,b的所有公因数都求出来,再从中挑最大的;(3)用短除法.辗转相除法：设a,b是正整数,而且有abqr1,0r1b;b肌r2,0r21；rir%r3,0r3(*)n2.14n,0rnrnl；rn1NnI-(a,b)n.例2用辗转相除法求(123,78),练习：用辗转相除法求

7、(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).由(*)式知b1r2Ln1n0,而n是有限正整数,再由性质1得(a,b)(.1)(1,2)=(n2,n1)(n1,n)(n,.)n.2 .最大公因数的性质最大公因数的几个性质

8、：性质2(am,bm)=(a,b)m,m>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,-96).3n1例5设n是任意整数,证实；7是既约分数.5n2证实设d=(3n+1,5n+2),WJd|3(5n+2)-5(3n+1),即d|1,d=1,作业1.利用辗转相除法求(84,90).2.求(120,36).3n13 .设n是整数,证实是既约

9、分数.7n2§3整除的进一步性质及最小公倍数1 .整除的进一步性质推论1设a,b不全为零,那么有s,tZ使得as+bt=(a,b).证实将(*)中每式中的余数解出得rnrn2rn1qn,rn1rn3rn2qn1,r2brq2,r1abql,再将rn1,rn,L,2,r1的表达式依次代入到rnrn2rn1.中就得au+bv=rn=(a,b尸d,u,vZ.例1用辗转相除法求(120,54),并求整数u,v使得120u+54v=(120,54).解120=2X54+12,54=12X4+6,12=6X2,.(120,54)=6.12=120-2X54,6=54-12X4=54-(120-2

10、X54)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的因数.证实如果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),那么(-,二-)=

11、1.dd性质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,02,L,an中每一个数的倍数,那么称m是整数a,a2,L,an的一个公倍数.aba2,L,an的公倍中最小正整数称为al,a2,L,an的最小公倍数.用a1,a2,L,an来表示.例如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的任

12、一公倍数是a,b的倍数；ab(ii)a,b=(ab).而且假设(a,b)=1,那么a,b=ab.证实(i)设m是a,b的任一公倍数,而且m=ta,b+r,0<r<a,babb,因m,a,b都是a,b的公倍数,由r=m-ta,b知r也是a,b的公倍数,假设0<r<a,b,那么这与a,b的最小性矛盾.故r=0,m=ta,b.ab(ii)记d=ab,那么d是整数,由a|a,b,a|a,bb就da知d|a,d|b,即d是a,b的公因数.ab设h是a,b的任一公因数,由habab的公倍数及TH16知a,b|卜,即abhZ,所以h|d,ab(a,b)=d,从而(a,b尸ab.定理5

13、设d,%,1,an都是正整数,令qg3,观自观,n1自办,那么3,&,L,斗R定理19设a1,a2,L,an是n(>2)个正整数,且两两互素,那么&,a2,L,ana1a2Lan例2求123,456,-789例3求正整数a,b,满足:a+b=120,(a,b)=24,a,b=144.例14设a,b,c是正整数,那么a,b,c=abc(ab,bc,ca)作业:P14:1.2 .求(84,45),并求整数u,v使得84u+45v=(84,45)§4质数算术根本定理1.质数定义设整数a>1,如果a除了1和a外再无其它正因数,那么称a为质数,也称为素数.否那么,称

14、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<VO.证实假定q是合数,设q=bc,1<b,c<q.因b|q,q|a,得b|a,但1<b<q,这与q是a的最小正因数矛盾.故q是素数.假设a是合数,设a=qm,由q的最小性知a=qm>qq,即q&Ja.素数判定定理设整数a>1,不超过Va所有素数为pl,p2

15、,L,战,如果R?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.整数的唯一分解定理12k定理3任彳a>1的整数都有标准分解式:a=p1p2Lpk(3)这里pl,p2,L,Pk为不同素数

16、,整数i0,i=1,k.推论1假设正整数a>1的标准分解式为a=p11p22Lpkk,那么a的正因数d为d=p1p2Lpk,0ii,i=1,k.而且a有不同的正因数(11)(12)L(1k)个.2aa=p11p22Lpkk,b=p11P22Lpj,i0,i0,i=1,k.那么(1)(a,b尸PJPzUpkk,a,b=PJPzLpkk,其中imin(i,i),imax(i,i),i=1,k.(2)a,b共有正公因数(11)(12)L(1k)个;(3)a,b共有公因数2(11)(12)L(1k)个.例3求725760,154200的标准分解式,并求它们的最大公因数和最小公倍数832解因725

17、760=2X5X11X41,154200=2X3X5X257,所以(725760,154200)=2X5,725760,154200=28X3X52X11X41X257.例4求以下各组数的最大公因数及其公因数的个数:(1)123,78；(2)120,54.练习:求以下各组数的最大公因数及其公因数的个数:(1)125,70；(2)140,56.22例8设p,q都是大于3的素数,证实24|pq.3质数的多少和质数的求法定理4素数有无穷多个.证实反证法,设质数只有k个:R,P2,L,%,令Mp1p2Lpk1,M>1,于是M有素数因数p.因pi?M,i=1,2,k,p|M,所以pwpi,i=1.

18、2, ,k.这就是说,pl,p2,L,pk,p是k+1个不同素数.这与假设矛盾.1-n之间的所有素数怎样求出来123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以下步骤进行：(1) 删去1,剩下的后面的第一个数是2,2是素数；(2) 删去2后面被2整除的数(从4开

19、始),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是否为素数；:5t;3.求725760,154200的标准分解式,并求它们的最大公因数和最小公倍

20、数,并求它们的所有公因数的个数.§5函数x,x及其应用1.函数x,x的定义定义1设x是实数,以冈表示不超过x的最大整数,称它为x的整数局部,又称x=x?x为x的小数局部.例1=3,=-4,=-1,=0,=3,-=-4.性质设x与y是实数,那么x?y?x?y;(2)假设m是整数,？m?x=m?x；(3)假设0?x<1,贝Ux=0;(4)(带余除法)设a,b是整数,且b>0,那么a=b+bar设a=bq?r,0?r<b得.q.,故bb葩总bba(5)设a与b是正整数,那么1-a中能被b整除的整数有1b个.证实能被b整除的正整数是b,2b,3b,?,因此,假设数1,2,?

21、,a中能被b整除的整数有k个,那么kb?a<(k+1)b?k?-<k+1?k=-.例2不超过101且是5的倍数的正整数有二1=20个,100-500的整数中7的倍数的正整数有工-:7=71-14=57.5772.函数x的应用k设P是素数,n是整数,如果p|n,k1kP?n,那么称p恰好整除n.k例3设P是素数,那么在1-n的整数中,恰好被P整除的整数有多少个定理1在n!的标准分解式中,质因数p的指数是nnnh=-+-T+F+pppnn恰被p整除的整数有%-肃个；ppnn恰被p整除的整数有三-=个；PPnn恰被p整除的整数有-F个；,ppnn恰被p整除的整数有T-TT个,于是ppnn

22、nnnnnnnnnh=Z-7+2(-2-3)+3(-3-4)+-+r(-)+=、+币+之+.pppppppppppnn性质/HI/".pp例3求50!的标准分解式中,素数2,3,5的指数,并确定50!的十进制数的末尾0的个数.练习1:200-300的整数中,求11的倍数的整数的个数练习2:60!的十进制数的末尾0的个数.作业P23:1t.2t,求100!的十进制数的末尾0的个数.习题课第二章不定方程§1二元一次不定方程1 .二元一次不定方程概念例1百鸡问题：“鸡翁一,值钱五,鸡母一,值钱3,鸡雏三,值钱一.百钱买百鸡,问鸡翁、鸡母、鸡雏各几何设百钱买鸡翁、鸡母、鸡雏分别x只

23、、y只、z只.依题意得x+y+z=100,且5x+3y+z/3=100.整理得14x+8y=200且x+y+z=100.这里要求x,y,z都是非负整数.14x+8y=200称为二元一次不定方程.二元一次不定方程的一般形式为ax+by=c,(a,b,cCZ).如果整数m,n满足am+bn=c,那么称m,n为ax+by=c的一组整数解,ax+by=c的一组整数解,也称为特解.2 .二元一次不定方程解法定理1二元一次不定方程ax+by=c有整数解的充分必要条件是,(a,b)|c.证实假设不定方程ax+by=c有整数解m,n,那么am+bn=cJ3为(a,b)|a,(a,b)|b,所以(a,b)|am

24、+bn,即(a,b)|c.反之,假设(a,b)|c,设c=t(a,b).由第一章§3定理1知,有整数u,v使得au+bv=(a,b),两边都乘以t得aut+bvt=t(a,b)=c,即ut,vy是ax+by=c的整数解.定理2二元一次不定方程ax+by=c,(a,b)=1(1)有整数解m,n,那么方程的一切整数解为x=m-bt,y=n+at,tCZ,或x=m+bt,y=n-at,tZ.(2)证实易知tZ,由(2)得到的整数x,y都是方程的解.设x,y是(1)的任一整数解,于是ax+by=c,am+bn=c,所以a(x-m)+b(y-n)=0,又得a(x-m)=-b(y-n),从而b|

25、a(x-m).由于(a,b)=1,所以b|(x-m),设x-m=bt,tZ,a(x-m)=-b(y-n)得y-n=-at,这样就得x=m-bt,y=n+at,tZ.3 .例子与应用例1求14x+8y=200的一切整数解和所有非负整数解.例2求111x-321y=75的一切整数解.例3甲物品每件12元,乙物品每件18元,现用100元钱去买这两种物品,假设要求每种物品至少买1件,且尽量不剩或少剩钱,问甲乙物品各买多少件作业P31:1(a),2.§2多元一次不定方程n元一次不定方程的一般形式为a1x1a2x2Lan4N(1)其中a1,a2,L,an,NZ.n?2是整数.Th1不定方程(1)

26、有整数解充分必要条件是,(a1,a2,L,an)|N.例1求9x+24y-5z=1000的一切整数解.解因(9,24,-5)=1,所以不定方程有整数解,因(9,24)=3,可设9x+24y=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,整理得20x+15y+12z=17.因20,15,12=1,不定故方程有整数解,设20x+15y=5

27、u,那么4x+3y=u,5u+12z=17.的通解为x=u-3s,y=-u+4s,sCZ,的通解为u=1-12t,z=1+5t,tZ.故原不定方程的通解为所以,60317111603T517112t3s112t4s15t45.当t=s=0时,x=-y=z=1,此时有作业:1求3x+6y-5z=15的一切整数解.§3勾股数2221 .不定方程xyz2 22不定方程xyz的一组整数解x,y,z称为一组勾股数例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股数.222定理不定方程xyz,(1)满足x>0,y>0,z>0,(x,y)=1

28、,2|x(2),乙f2,22,2一切正整数解可由下式表出：x=2ab,y=ab,z=ab(3)其中a>b>0,(a,b)=1,a,b一奇一偶.a=3,b=2,x=12,y=5,z=13;a=4,b=3,x=24,y=7,z=25;a=5,b=4,x=40,y=9,z=41.a=2,b=1,x=4,y=3,z=5;a=4,b=1,x=8,y=15,z=17;a=5,b=2,x=20,y=21,z=29;2.其它不定方程例3求不定方程的全部整数解xy=6,xy-x+y-4=0.解x=±1且y=±6,或x=±6,且y=±1,或x=±2,且

29、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.222作业:1.写出不定方程xyz的满足x>0,y>0,z>0,(x,y)=1,2|x的2组正整数解2.求不定方程xy-x-y-4=0的全部整数解.AfV*弟二早1同余的概念及其性质1. 同余及性质定义设m是正整数,称m为模.a,b乙如果a,b被

30、m除所得的余数相同,那么称a,b对模m同余,记为amb(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,tZ.证实必要性,假设amb(modm).可设a=msa=r,b=mua=r,s,uZ,贝Ua-b=m(s-u)=mt,T=s-uCZ.所以m|a-b,且a=b+mt.充分性,设a=ms+r1,b=mu+r2,a-b=m(s-u)+r1-r2.因m|a-b,所以m|r1-r2,但|r1-r2

31、|<m.从而r1=r2,即a三b(modm).同余的性质甲：a三b(modm).乙：假设a三b(modm),bma(modm).丙：假设amb(modm),bmc(modm),贝Uamc(modm).丁、戊:abi(modm),a2b2(modm),那么a1a2b1b2(modm),a1a2b1b2(modm)bk(modm)那么,假设a1b1(modm),a2b2(modm),L,aka1a2Lakb1b2Lbk(modm),a1a2Lakb1b2Lbk(modm).由此可得定理2.2. 同余的应用(9)|a的条件设a=an10nan110niLa110a0,0ai9,i1,L,n,a

32、n0.那么因101(mod3(9),i=1,n,那么aanan1La1a0(modm),于是3(9)|a是3(9)|anLa1a0.(11,13)|a的条件设a=an1000nan11000niLa11000a0,0ai999,i1,L,n,an0.因1000i1(mod7(11,13),那么aa0a1L(1)an(modm),于是7(11,13)|a是7(11,13)|a0a1L(1)nan.例1设a=5874192,b=435693,anLa1a0=5+8+7+4+1+9+2=36,anLa1a0=4+3+5+6+9+3=30,所以9|a,3|b.例2假设a=637693,a04L(1)n

33、an=693-637=56,7|56,11?56,13?56,所以7|5a,11?a6,13?a.作业：2.§2剩余类及完全剩余系1 .模m的剩余类及完全剩余系设m是正整数,Z是整数集,令Kr=mt+巾CZ,r=0,1,m-1,那么心,K1,Km1称为模m的剩余类.易知,a,bKr,那么amb(modm).称a为Kr中其它数的剩余.设arKr,r=0,1,m-1,称a0,a1,am1为模m的完全剩余系.定义设m是正整数,0,1,m-1称为模m的非负最小完全剩余系.m,m1,L,1,0,1,L,m1,或-m1,L,1,0,1,L,-m为偶数时,22222称为模m的绝对最小完全剩余系；m

34、为奇数时,1,0,1,Lm12称为模m的绝对最小完全剩余系例1m=6,模6的剩余类为K0,K1,K2,K3,K4,K5,0,1,2,3,4,5是模6的一个完全剩余系,1,2,3,4,5,6也是模6的一个完全剩余系.-3,-2,-1,0,1,2;-2,-1,0,1,2,3都是模6的完全剩余系,称为模6的绝对最小完全剩余系.例2m=5时,0,1,2,3,4;-2,-1,0,1,2分别叫做模5的非负最小完全剩余系和绝对最小完全剩余系2.完全剩余系的判定定理1m个整数a1,a2,am为模m的完全剩余系的充分必要条件为,a1,a2,am对模m两两不同余.定理2设m是正整数,(a,m)=1,bCZ,x1,

35、x2,Xm是模m的一个完全剩余系,那么ax1bax2baxmb是模m的一个完全剩余系证实对jwi,m?(xjx),由于aXjb(axib)a(XjXi),且(a,m)=1,于是m?a(XjX),所以m?aXjb(aXib).aXjb?axib(modrm,i,j=1,2,m,jwi,从而ax1b,ax2b,aXmb是模m的一个完全剩余系.例3写出模9的一组完全剩余系,它的每一个数都是偶数；写出模9的一组完全剩余系,它的每一个数都是奇数.作业：1.分别写出模7、模8的非负最小完全剩余系、绝对最小完全剩余系.3简化剩余系与欧拉函数2 .简化剩余系、欧拉函数定义假设模m的一个剩余类里的数与m互质,那

36、么称这个剩余类为与模m互质的.对与模m互质的全部剩余类,从每一类里任取一数组成的集合,叫做模m的简化剩余系.m=6时,K1,K5是全部与模m互质的剩余类,1,5是模6的简化剩余系.m=8时,K1,K3,K5,K7是模8的简化剩余系.定义设a是正整数,欧拉函数(a)=0,1,a-1中与a互质的整数的个数.例如(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,(7)=6.模m的一个简化剩余系中含有(m)个数.(m).模m的每一个简化剩余系,是3 .简化剩余系的判定定理1模m的剩余类Kr与模m互质的是aCZ,使得(a,m)=1.与模m互质的剩余类的个数是由与mZL质的对模m两两

37、不同余的(m)个整数组成.定理3设m是正整数,(a,m)=1,x1,x2,x(m)是模m的一个简化剩余系,那么ax1ax2,ax(m)是模m的一个简化剩余系.定理4假设3,m2是互质的两个正整数,x1x2分别通过模的简化剩余系,那么m1x2+m2通过模m1m2的简化剩余系.推论假设色,m2是互质的两个正整数,那么Em2)(m1)(m2).一1一2k定理5设正整数a的标准分解式为a=p1p2Lpk,那么111,、11/八21/八1k1/八a(1-)(1A(1一)(a)=p1(p11)p2(p21)Lpk(pk1)=p1p2pk证实在数列1,2,p-1,p,p+1,p+p-1,2p,111p(p-

38、1)+1,p(p-1)+p-1,pp1()1(1)中与p互质的整数有p(p-1)个,即(p)p(p1).作业P60:3.§4欧拉定理费尔玛定理及其应用1 .欧拉定理费尔玛定理定理1(Euler)设a,mCZ,m>1,(a,m)=1,那么a1(modm).,abs也是模m的一个简化剩余系,证实取模m的一个简化剩余系b1,b2,bs,(s(m),由于(a,m)=1,由§3定理3知,ab1,ab2,于是(abl)(ab2)L(abs)bt2Lbs(modm)即a(m)bbLbsbbLbs(modm)因(m%=1j=1.2, ,(m),所以(m,n,b2,L,b(m)=i,从

39、而a(m)(modm).证毕.P1313(xx)xx.故2730是整值多项式.P推论(费尔玛定理)设p是素数,那么a1(modP),而且aez,aa(modP).证实假设p|a,那么aPa0(modP),假设(a,m)=1,那么a1(modP),所以paa(modP).P1q1例1设p,q是不同的素数,证实qp1(modpq).P1q1证实因p,q是不同的素数,所以(p,q)=1,由费尔玛定理知,qp1(modp),P1q1dP1q1Aqp1(modq).由同余的性质得,qp1(modpq).例2设pw2,5为素数,整数a的十进制数由p-1位,而且每一位上的数字都是9,证实p|a.P1.证实因

40、p*2,5为素数,所以(10,p)=1,由费尔玛止理得,a=99-9=101034(mod7),这就是说,从今天起再过10天是星期五(1+4).1=0(modp),即p|a.例3假设变量x取整数时,多项式P(x)=bob1xLbnxn的值总为整数,那么称P(x)为整值多项式.证实,2730(x13x)是整值多项式.证实2730=2X3X5X7X13,当x取整数值时,由费尔玛定理,1313xx0(mod13),即13|xx.x13x(x7x)(x61)0(mod7),即7|x13x.13584xx(xx)(xx1)0(mod5),即5|x13x.13/310864213xx(xx)(xxxxx1

41、)0(mod3),即3|xx.13-2-解103(mod7),1032(mod7),1113xx(xx)(xLx1)0(mod2),即2|xx.13一因2,3,5.7.13两两互质,由整除的性质知,2X3X5X7X13|xx,即2730|例4今天是星期一,问从今天起再过10101010天是星期几103332g361(mod7),所以1021061(mod7)o又因10-2(mod6),21022(mod6),故1024(mod6)0101010设106k4,k为正整数,于是106k410例5求202120212021被8除的余数.作业:P64:1.例32.分数与循环小数定义如果无限小数0.a1

42、a2LanL(an0,1,9)从任何一位数后不全为0,且能找到两个整数s>0,t>0,使得asiasikt,i=1,2,t,k=0,1,2,(*)那么称它为循环小数,并简记为g0a向Lasasg1Last对满足(*)的最小正整数ggt,称as1Last为循环节,称t为循环节的长度.假设最小的s=0,那小数就叫做纯循环小数,否那么叫做混循环小数.定理2有理数b,0<a<b,(a,b)=1,能表成纯循环小数的充分必要条件是,(b,10)=1.推论有理数b,0<a<b,(a,b)=1,是纯有限小数的充分必要条件是(b,10)w1.证实必要性：假设有理数b能表成纯循

43、环小数,那么由0<b<1及定义知qbq10tab=0.10tba1a2LaLatL=0a1a2Lat+10tg3.a1a2LataLa1a2Lat+0a1a2Lata1LatL.t=q+b.所以a(10充分性：如果(b,10)=1,由定理1知有一正整数(10t1)a0,q=a110t10.a1a2Latb=0.aa2LataLatL.于是1)bq,因(a,b)=1,所以b|10t1,设10t1=qb,那么10qb=1,故(b,10)=1.t使彳#10t1(modb),0<t<(b),又有10taa(modb),设10aqba,那么q(10t1)a10tba210t2L1

44、0at110taqbatL=0.aLat定理3有理数b,0<a<b,(a,b)=1,max(,)at,显然a1,a2,L,at不全为9,也不全为0.而且a_q_a得b10tb2g5b1,四章同余方程§1根本的概念及一次同余方程1a10tb0.a1a2Lat10tba反复利用b0.a1a2Lat10tb即得不全为0,(b1,10)=1,bl1,那么b能表成纯循环小数.其中不循环局部的位数是1.同余方程的概念nc7定义设f(x)=a0a1xLanx,这里aiZ,i=0,1,是正整数,那么称nf(x)=a0alXLanx0(modm).(1)为同余式,或模m的同余方程.假设an/0(modm),n称为同余方程(1)的次数.假设aZ而且f(a)三0(modm),那么称xma(modm历同余方程(1)的解.-2例1f(x)=xx3m0(mod5)是模5的2次同余方程,由于f(1)=5三0(m