初等数论期末复习资料

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.(3) 如果a1,a2,L,an都是m的倍数,q1,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&l

3、t;r<b.(1)这里q称为b除a的商,r称为b除a的余数.例如-5=3X(-2)+15=3X1+2-5=(-3)X2+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奇数、偶数及性质能

4、被2整除的整数称为偶数.如,0,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是任一奇数，试证明81a1.例6设n是正整

5、数，证明形如3n-1整数不是完全平方数.证明对任意整a,设a=3q或a=3q±1,于是22222a=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)因数、公因数：都是正整数；最大公因数：没有专门的符号.定义设al,a2,L

6、,ai,d都是整数,d.如果dai,i=1,2,"称d是a1,a2,L,4的公因数，d,a2,L,an的公因数中最大的整数称为最大公因数.记为(W,a2,L,%).如果(a),%L,aJ=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是正整数,而且有abq1r1,0r1b;br1q2r2,0r2r1;r1r2q3r3,0r3r2;(*)rn2rn1qn

7、rn,0rnrn1;rn1rnqn1.(a,b)rn。例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).由(*)式知 brir2rn 1rn0,而 n 是有限正整数，再由

8、性质 1 得(a,b)(b,R)(n,r2)=(rn2,rni)(rnl,rn)(rn,。)rn.2 .最大公因数的性质最大公因数的几个性质：性质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是任意整数,证明力是既约分数.即 d|1,d=1证明设d=(3n+1,5n+2),则d|

9、3(5n+2)-5(3n+1),所以3n+1与5n+2互质.作业1.利用辗转相除法求(84,90).2.求(120,36).3n13 .设n是整数，证明二二是既约分数。7n2§3整除的进一步性质及最小公倍数1 .整除的进一步性质推论1设a,b不全为零，那么有s,t£Z使得as+bt=(a,b).证明将(*)中每式中的余数解出得rnrn 1, rn 2,L , r2, ri的表达式依次代入到rnrn 2rn 1qn 中就得 au+bv= rn =(a,b尸d,u,vC Z.r2rn0n,rn1n3rn21,2b用2,1abq,再将例1用辗转相除法求(120,54),并求整数u

10、,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的任一公因数

11、都是d的因数.证明如果d=(a,b),由性质2有u,vZ使得au+bv=d.设s是a,b的任一公因数，则s|au,s|bv,且s|au+bv,即s|d.ab性质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是ai,a2,L,an中每一个数的倍数，则称m是整数a1,a2,L,an的一个公倍数.al,a2，L,an的公倍中最小正整数称为al,a2，L，an的最小公倍数.用闰,出,1_a来

12、表示.例如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,0<r<a,bab，因m,a,b都是a,b的公倍数，由r=m-ta,b知r也是a,b的公倍数，若0<r<a,b,则这与a,b的最小性矛盾.故r=0,m=ta,b.aab(ii)记d=ab，则d是整数，由a|a,b,a|a,b及dbabda知d

13、|a,d|b,即d是a,b的公因数.ab b a设h是a,b的任一公因数，由卜 ah b卜是a,babab的公倍数及TH16知a,b|卜，即a bhZ，所以h|d,ab(a,b)=d,从而(a,b)=ab.定理5设ai，a2，L，an都是正整数，令a© mjmz,% m3,，叫斗叫,则&,%人，如n.定理19设a&l昌是n(>2)个正整数，且两两互素，则H,a2,L,anaLa例2求123,456,-789例3求正整数a,b,满足:a+b=120,(a,b)=24,a,b=144.abc例14设a,b,c是正整数，则a,b,c二(abbcca)作业:P14:1.

14、2 .求(84,45),并求整数u,v使得84u+45v=(84,45)斗质数算术基本定理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&Ja证明假定q是合数，设q=bc,1<b,c<q.因b|q,q|a,得b|a,但1<b<

15、q,这与q是a的最小正因数矛盾.故q是素数.若a是合数，设a=qm,由q的最小性知a=qm>qq,即q&Ja素数判定定理设整数a>1,不超过所有素数为pl,p2,L,pk,如果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

16、尸P,或(P,a)=1.即P|a,或(P,a)=1.2.整数的唯一分解定理定理3任何a>1的整数都有标准分解式:a=p11p22Lpkk(3)这里p1,p2,L,pk为不同素数,整数i0尸i,.,k.推论1若正整数a>1准分解式为a=p11p22Lpkk,则a的正因d=p11p22Lpkk,0i,i=1,k.而且a有不同的正因数(11)(12)L(1k)个.12推论2设a=p1p2pkk,b=p11p22Lpkk,i0,i0,i=1,k.12(1)(a,b)=p1p2Lpkk12,a,b=p1p2Lpkk，其中imin(i,i),imax(i,i),i=1,k.(2)a,b共有正公

17、因数(11)(12)L(1k)个;(3)a,b共有公因数2(11)(12)L(1例3求725760,154200,并求它们的最大公因数和最小公倍数解因725760=28X5X11X41,154200=23x3x52x257,所以(725760,154200)=21*35,725760,154200=28X3X52X11X41X257.例4求下列各组数的最大公因数及其公因数的个数(1)123,78；(2)120,54.练习:求下列各组数的最大公因数及其公因数的个数:(1)125,70；(2)140,56.22例8设p,q都是大于3的素数,证明24|pq3质数的多少和质数的求法定理4素数有无穷多个

18、.证明 反证法 ,设质数只有k 个:R,P2,L ,Pk,令 Mp1 p2 L pk 1,M>1,于是M有素数因数p.因pi?M,i=1,2,k,p|M,所以pwPi,i=1,2,k.这就是说,p1, p2,L,p 是 k+1个不同素数.这与假设矛盾.1-n之间的所有素数怎样求出来？34131423243334434453546364737483845615162526353645465556656675768586781718272837384748575867687778878891019202930394049505960697079808990919293949596979899

19、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

20、.判别1577是否为素数;2.P19:5t；(5) 725760,154200的标准分解式,并求它们的最大公因数和最小公倍数,并求它们的所有公因数的个数。§5函数x,x及其应用1.函数x,x的定义定义1设x是实数，以冈表示不超过x的最大整数，称它为x的整数部分，又称x=xx为x的小数部分例13.5=3,-3.5=-4,-0.1=-1,0.1=0,=3,-=-4.性质设x与y是实数,则(1)xyxy；(2)若m是整数,mx=mx；若0x<1,则x=0;(4)(带余除法)设a,b是整数，且b>0,则a=bJ+bb设a=bqr,0r<b得qbb>b=q,b4所以a=

21、bb+bb.(5)设a与b是正整数，则1-a中能被b整除的整数有b个。证明能被b整除的正整数是b,2b,3b,，因此，若数1,2,a中能被b整除的整数有k个，则kba<(k+1)bakb<k+1k=b.例2不超过101且是5的倍数的正整数有1015-=20个,100-500的整数中7的倍数的正整数有7-997=71-14=57.2.函数冈的应用k设p是素数,n是整数，如果pIn,1k?n,则称p恰好整除n.例3设P是素数，那么在1-n的整数中，恰好被kp整除的整数有多少个?定理1在n!的标准分解式中，质因数p的指数是nnnh=+/+1+ppp证明在1,2,3,n中，nn恰被p整除的

22、整数有-二个；ppnn恰被p整除的整数有W-F个；ppnn恰被p整除的整数有F-F个;,pp恰被p整除的整数有7-T7个,，于是PPnnnnnnnnnh=T-T2+2(-?-3)+3(-4)+-+r(-7-)+=-+pppppppppnn性质TT=7/r.pp例3求50!的标准分解式中，素数2,3,5的指数，并确定50!的十进制数的末尾0的个数.练习1:200-300的整数中，求11的倍数的整数的个数.练习2:60!的十进制数的末尾0的个数.作业P23:1t.2t,求100!的十进制数的末尾0的个数.习题课第二章不定方程§1二元一次不定方程1. 二元一次不定方程概念鸡雏各几何?例1百

23、鸡问题：“鸡翁一，值钱五，鸡母一，值钱3,鸡雏三，值钱一.百钱买百鸡，问鸡翁、鸡母、设百钱买鸡翁、鸡母、鸡雏分别x只、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,cZ).如果整数m,n满足am+bn=c,则称m,n为ax+by=c的一组整数解,ax+by=c的一组已知整数解,也称为特解.2. 二元一次不定方程解法定理1二元一次不定方程ax+by=c有整数解的充分必要条件是,(a,b)|c.证明若

24、不定方程ax+by=c有整数解m,n,则am+bn=c,因为(a,b)|a,(a,b)|b,所以(a,b)|am+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,tC2,或x=m+bt,y=n-at,tCZ.(2)证明易知t乙由(2)得到的整数x,y都是方程的解.设x,y是(1)的任一整数解,于是a

25、x+by=c,am+bn=c，所以a(x-m)+b(y-n)=0,又得a(x-m)=-b(y-n),从而b|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,t6Z.3. 例子与应用例1求14x+8y=200的一切整数解和所有非负整数解.例2求111x-321y=75的一切整数解.例3甲物品每件12元，乙物品每件18元，现用100元钱去买这两种物品，若要求每种物品至少买1件，且尽量不剩或少剩钱，问甲乙物品各买多少件？作业P31:1(a),2.2多元一次不定方程其中a1,a2,L,an,N

26、Z.n2是整数.n 元一次不定方程的一般形式为a1x1 a2x2 LanxnN(1)Th1不定方程(1)有整数解充分必要条件是,(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,sCZ,的通解为u=5t,z=-20+3t,tZ.故原不定方程的通解为x=5t-8s,y=-5t+3s,z=-20+3t,s,tZ.例2把17/60写成分母两两互质的三个既约分数之和17xyz解因60=3X4X5，设60

27、22不定方程x y z的一组整数解(x,y,z)称为一组勾股数.例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股数.2224定理不定方程x y z ,(1)满足 x>0,y>0,z>0,(x,y)=1,2 |x(2)2. 22. 2一切正整数解可由下式表出：x=2ab,y= a b ,z= a b,整理得20x+15y+12z=17.因(20,15,12=1,不定故方程有整数解，设20x+15y=5u,则4x+3y=u,5u+12z=17.的通解为x=u-3s,y=-u+4s,sZ,的通解为u=1-12t,z=1+5t,tZ.故原不定方

28、程的通解为x=1-12t-3s,y=-1+12t+4s,z=1+5t,s,tZ.17112t 3s所以，60317 1160345112t4s15t45.当t=s=0时,x=-y=z=1,此时有作业:1求3x+6y-5z=15的一切整数解.S勾股数2221 .不定方程xyz其中 a>b>0,(a,b)=1,a,b奇一偶. 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.其它不定方程2Da=3,b=2,x=12,y=5,z=13; a=4,b=3,x=24,y=7,z=25; a=5,b=4,x

29、=40,y=9,z=41.例3求不定方程的全部整数解xy=6, xy-x+y-4=0.解x=±1且y=±6,或乂=±6,且y=±1,或乂=±2,且丫=±3,或x=±3,且丫=±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,

30、z>0,(x,y)=1,2|x的2组正整数解2.求不定方程xy-x-y-4=0的全部整数解.第三章同余国同余的概念及其性质1 .同余及性质定义设m是正整数，称m为模.a,b乙如果a,b被m除所得的余数相同，则称a,b对模m同余，记为a书(modm).如果a,b被m除所得的余数不同,则称a,b对模m不同余,记为a?b(modm).例如4目(mod3),6鸟1(mod5),4?5(mod3),6?8(mod5).定理1整数a,b对模m同余的充分必要条件是，m|a-b,即a=b+mt,t乙证明必要性，若a书(modm).可设a=msa=r,b=mua=r,s,uZ,贝Ua-b=m(s-u)=m

31、t,T=s-uC乙所以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|<m.从而r1=r2,即a也modm).同余的性质甲:a书(modm).乙:若a书(modm),b刃(modm).丙:若a书(modm),b刃(modm),贝Ua(modm).丁、戊:a1b1(modm),a2b2(modm),则a1a2b1b2(modm),a1a2b1b2(modm)由此可得，若&6(modm),a2d(modm),L,akbk(modm)则a1a2Lakb1b2Lbk(modm),a1

32、a2Lakb1b2Lbk(modm)由此可得定理2.2 .同余的应用A.3(9)|a的条件设a=an10nan110niLa110a0,0ai9,i1,L,n,an0.则因101(mod3(9),i=1,n,则aanan1La1a0(modm),于是3(9)|a是3(9)|anLa1a0.B.7(11,13)|a的条件设a=an1000nan11000niLa11000a0,0ai999,i1,L,n,an0.因1000i1 (mod7(11,13),则 aa0 a1 L ( 1) an z01 v n n(modm),于是7(11,13)|a 是 7(11,13)| a0a1 L ( 1)n

33、an例 1 设 a=5874192,b=435693,an La1a0=5+8+7+4+1+9+2=36,an La1a0=4+3+5+6+9+3=30,所以9|a,31b.例 2 若 a=637693, a0 a1 L(1)na.( ) n =693-637=56,7|56,11?56,13?56,所以715a,11?a6,13?a.作业：1.p53:2.§2剩余类及完全剩余系1 .模m的剩余类及完全剩余系设m是正整数,Z是整数集，令Kr=mt+r|tCZ,r=0,1，,m-1,则K0,K1,，Km1称为模m的剩余类.易知，a,bKr，则a书(modm).称a为"中其它数

34、的剩余.设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为奇数m 1时，21,0,1,Lm 12称为模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的绝对最小完全剩余系例2

35、m=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,x2，xm是模m的一个完全剩余系，则ax1 b ax2 baxm b 是模 m 的一个完全剩余系证明对jwi,m?(XjXi),因为aXjb(axib)a(xjxi),且(a,m)=1,于是m?a(XjK),所以m?axjb(a"b).axjb?泌b(modm),i,j=1,2,m,jwi,从而ax1b,a

36、x2b,axmb是模m的一个完全剩余系.例3写出模9的一组完全剩余系,它的每一个数都是偶数;写出模9的一组完全剩余系,它的每一个数都是奇数作业：1.分别写出模7、模8的非负最小完全剩余系、绝对最小完全剩余系.3 简化剩余系与欧拉函数1. 简化剩余系、欧拉函数定义若模m的一个剩余类里的数与m互质,则称这个剩余类为与模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互质的整数的个数

37、.例如(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,(7)=6.模m的一个简化剩余系中含有(m)个数。2. 简化剩余系的判定定理1模m的剩余类Kr与模m互质的是a乙使得(a,m)=1.与模m互质的剩余类的个数是(m).模m的每一个简化剩余系是由与m互质的对模m两两不同余的(m)个整数组成.定理3设m是正整数，(a,m)=1,x1,x2，,x(m)是模m的一个简化剩余系，则ax1,ax2ax(m) 是模 m 的一个简化剩余系定理4若m1,m2是互质的两个正整数，x1,x2分别通过模的简化剩余系，则m1x2+m2x1通过模m1m2的简化剩余系.推论若m1,0是互质的两个正

38、整数，则(m1m2)(mJ (m2)一1一2k定理5设正整数a的标准分解式为a=p1p2Lpk，则(a). p11 1( p1 1)p22 1( p2 1)L P1a(1kk 1( Pk1).力(11一)L (1p2p;)证明在数列1,2,p-1,p,p+1,p+p-1,2p,111P(P-1)+1,P(P-1)+p-1,PP1(P)P1(P1)中与P互质的整数有P(p-1)个，即(P)P(P1)作业P60:3.势欧拉定理费尔玛定理及其应用贝U a (m) 1(mod m)1 .欧拉定理费尔玛定理定理1(Euler)设a,mCZ,m>1,(a,m)=1,证明取模m的一个简化剩余系b1,b

39、2,bs,(s(m),由于(a,m)=1,由§3定理3知,ab1,ab2,1abs也是模m的一个简化剩余系，于bMbsgodm),因(m, bi)=1,i=(ab)(a0)L(abs)bb2Lbs(modm)a(m)b1b2Lbs1,2，(m),所以(m,Db,L,b(m)=1,从而a1(modm).证毕。P1P推论(费尔玛定理)设P是素数，则a1(modP),而且aeZ,aa(modP).证明若p|a,则aPa0(modP),若(a,m)=1,则aP11(modP),所以paa(modP).P1q1例1设p,q是不同的素数，证明qp1(modpq).P1q1证明因p,q是不同的素数

40、，所以(p,q)=1,由费尔玛定理知,qp1(modp),P1q1P1q1qp1(modq).由同余的性质得，qp1(modpq).例2设p*2,5为素数，整数a的十进制数由p-1位，而且每一位上的数字都是9,证明p|a.P1证明因p*2,5为素数，所以(10,p)=1,由费尔玛定理得,a=99-9=101目(modp),即p|a.例3若变量x取整数时，多项式P(x)=b0b1xLbnxn的值总为整数，则称P(x)-(x13x)为整值多项式.证明，2730是整值多项式.证明2730=2X3X5X7X13，当x取整数值时，由费尔玛定理，13-13xx0(mod13),即13|xx.13/7、/6

41、-13xx(xx)(x1)0(mod7),即7|xx.13z58413xx(xx)(xx1)0(mod5),即5|xx.x13x(x3x)(x10x8x6x4x21)0(mod3),即3|x13x.x13x(x2x)(x11Lx1)0(mod2),即2|x13x.13因2,3,5.7.13两两互质，由整除的性质知,2X3X5X7X13|xx，即2730|1.13、13(xx)xx.故2730是整值多项式.例4今天是星期一，问从今天起再过1010101天是星期几?22解103(mod7),1032(mod7),103332g361(mod7),所以6101(mod7)。又因10-2(mod6),

42、2-2101022(mod6),故1024(mod6)。10设106k4,k为正整数，于是1010106k10101034(mod7),这就是说，从今天起再过10天是星期五(1+4)。20112011例5求2011被8除的余数。作业:P64:1.例32.分数与循环小数定义如果无限小数0.a1a2LanL(an0,1,9)从任何一位数后不全为0,且能找到两个整数s>0,t>0,使得asiasikt,i=1,2,t,k=0,1,2,(*)则称它为循环小数，并简记为0.a1a2Lggasas1Lastqbq10t对满足(*)的最小正整数gt,称as1Lgast为循环节，称t为循环节的长度

43、.若最小的s=0,那小数就叫做纯循环小数，否则叫做混循环小定理2有理数b,0<a<b,(a,b)=1,能表成纯循环小数的充分必要条件是，(b,10)=1.推论证明有理数b,0<a<b,(a,b)=1,是纯有限小数的充分必要条件是(b,10)w1.必要性：若有理数b能表成纯循环小数，则由0<tb=0a1a2LataLatL=0QazLat+10BaazLataL10taa1a2Lata1a2Lata1LatLat=q+b.所以a(10充分性：如果(b,10)=1,由定理1知有一正整数ttat(10t1)a0q(101)b101令q=a110t10.a1a2Latb=

44、0.a1a2Lata1L定理3max(,a210t2L10at1，又由10taqb有理数b,0<a<b,(a,b)=1,b<1及定义知atL.于是1bq,因(a,b)=1,所以b|10使彳#10t1(modb),0<tat,显然前比山，at不全为9,也不全为0.而且F1,设10t1=qb,<(b)，又有10taa贝-0tqb=1,故(b,10)=1.(modb),设10aqba,则q1a10t10tb0.a1a2Lat1a10tba反复利用b0.a1a2Lat1a10tb即得b1,不全为0910)=1,b11,则b能表成纯循环小数.其中不循环部分的位数是四章同余方程§1基本的概念及一次同余方程1.同余方程的概念n-c7定义设f(x)=a0a1xLanx,这里3iZ,i=0,1,n.m是正整数，则称na。axLanxf(x)=01n0(modm).(1)为同余式，或模m的同余方程.若an/0(modm),n称为同余方程(1)的次数.若aCZ而且f(a)司(modm),则称x刃(modm)为同余方程(1)的解.2例1f(x)=xx3司(mod5)是模5的2次同余方程，由于f(1)=5司(mod5),因此xM(mod5)是同余方程的一个解.另外xx=m1tx0,m1m/d,t=0,±1,±2,，(mod5