初等數(shù)論期末復(fù)習(xí)資料

1、精品數(shù)論教案§1 整數(shù)的整除帶余除法1 整數(shù)的整除設(shè)a,b是整數(shù)，且bw0,如果有整數(shù)q,使得a=bq,則稱b整除a,記為b|a,也稱b是a的因數(shù),a是b的倍數(shù).如果沒有整數(shù)q,使得a=bq,則稱b不能整除a,記為b?a.例如2|4,4|-12,-5|15;2?3,-3?22.在中小學(xué)數(shù)學(xué)里,整除概念中的整數(shù)是正整數(shù),今天講的整除中的整數(shù)可正可負(fù).判斷是否b|a？當(dāng)a,b的數(shù)值較大時,可借助計算器判別.如果b除a的商數(shù)是整數(shù),說明b|a;如果b除a的商不是整數(shù),說明b?a.例1判斷下列各題是否b|a？(1)7|127?(2)11|129?(3)46|9529?(4)29|5939?整

2、除的簡單性質(zhì)(1) 如果c|b,b|a,那么c|a;(2) 如果d|a,d|b,那么對任意整數(shù)m,n,都有d|ma+nb.(3) 如果a1,a2,L,an都是m的倍數(shù),q1,q2,L,qn是任意整數(shù),那么qiaiq2a2Lqnan是m的倍數(shù).(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個連續(xù)整數(shù)的乘積,一定可被2整除.練習(xí)證明任意3個連續(xù)整數(shù)的乘積,一定可被3整除.感謝下載載2.帶余除法設(shè)a,b是整數(shù)，且b>0,那么有唯一一對整數(shù)q,r使得a=bq+r,0&l

3、t;r<b.(1)這里q稱為b除a的商,r稱為b除a的余數(shù).例如-5=3X(-2)+15=3X1+2-5=(-3)X2+15=(-3)X(-1)+215=(-5)X(-3),-24=(-2)X12.事實上,以b除a的余數(shù)也可以是負(fù)的.例如-5=3X(-1)-2=3X(-2)+1.求b除a的余數(shù),也稱為模運算(取余):mod.可用計算器進(jìn)行.具體操作:輸入a-按mod(取余)鍵-輸入b-按=鍵得出余數(shù).如果b除a的余數(shù)=0,則b|a;如果b除a的余數(shù)w0,則b?a.例3利用計算器求余數(shù):(1)7除127;(2)11除-129;(3)46除-9529;(4)-29除5939奇數(shù)、偶數(shù)及性質(zhì)能

4、被2整除的整數(shù)稱為偶數(shù).如,0,4,10,-6,-8都是偶數(shù).不能被2整除的整數(shù)稱為奇數(shù).如,-5,-3,1,7,11都是奇數(shù).偶數(shù)的形式為2n(n是整數(shù));奇數(shù)的形式為2n-1(n是整數(shù)).奇數(shù)、偶數(shù)的性質(zhì):偶數(shù)±偶數(shù)=偶數(shù),奇數(shù)±奇數(shù)=偶數(shù),奇數(shù)±偶數(shù)=奇數(shù),偶數(shù)x偶數(shù)=偶數(shù)，偶數(shù)x奇數(shù)=偶數(shù)，奇數(shù)x奇數(shù)=奇數(shù).例如2+4,2-4,3+1,3-1,3+4,6+5設(shè)a,b是任意兩個整數(shù),則a+b與a-b同奇同偶.例如3+5,3-5,6+3,6-3,22例4設(shè)a,b,n是任意3個整數(shù),而且ab2n,證明n是偶數(shù).2例5設(shè)a是任一奇數(shù)，試證明81a1.例6設(shè)n是正整

5、數(shù)，證明形如3n-1整數(shù)不是完全平方數(shù).證明對任意整a,設(shè)a=3q或a=3q±1,于是22222a=9q或a=9q±6q+1=3(3q±2q)+1.2即aw3n-1,故3n-1不是完全平方數(shù).練習(xí)設(shè)n是正整數(shù)，證明形如4n-1、4n+2的整數(shù)都不是完全平方數(shù).習(xí)題:P3-4:1t,2t.§2公因數(shù)、最大公因數(shù)1 .最大公因數(shù)、輾轉(zhuǎn)相除法中小學(xué)里的公因數(shù)、最大公因數(shù)的概念：幾個數(shù)的公有因數(shù)叫做這幾個數(shù)的公因數(shù).公因數(shù)中最大的整數(shù)稱為這幾個數(shù)的最大公因數(shù).(1)幾個數(shù):不能確定;(2)因數(shù)、公因數(shù)：都是正整數(shù)；最大公因數(shù)：沒有專門的符號.定義設(shè)al,a2,L

6、,ai,d都是整數(shù),d.如果dai,i=1,2,"稱d是a1,a2,L,4的公因數(shù)，d,a2,L,an的公因數(shù)中最大的整數(shù)稱為最大公因數(shù).記為(W,a2,L,%).如果(a),%L,aJ=1,則稱西電L©互質(zhì)。例1(-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小學(xué)數(shù)學(xué)里，求正整數(shù)a,b的最大公因數(shù)主要有這個樣幾種方法：(1) 觀察法；(2) 將a,b的所有公因數(shù)都求出來,再從中挑最大的；(3) 用短除法.輾轉(zhuǎn)相除法:設(shè)a,b是正整數(shù),而且有abq1r1,0r1b;br1q2r2,0r2r1;r1r2q3r3,0r3r2;(*)rn2rn1qn

7、rn,0rnrn1;rn1rnqn1.(a,b)rn。例2用輾轉(zhuǎn)相除法求(123,78),練習(xí):用輾轉(zhuǎn)相除法求(66,54).下面說明輾轉(zhuǎn)相除法的正確性.先證明性質(zhì)1設(shè)整數(shù)a,b,c不全為0,而且有整數(shù)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 是有限正整數(shù)，再由

8、性質(zhì) 1 得(a,b)(b,R)(n,r2)=(rn2,rni)(rnl,rn)(rn,。)rn.2 .最大公因數(shù)的性質(zhì)最大公因數(shù)的幾個性質(zhì)：性質(zhì)2(am,bm)=(a,b)m,m>0.(短除法的根據(jù))例3求(84,90),(120,36).(84,90)=3(28,30)=6(14,15)=6.(120,36)=12(10,3)=12.性質(zhì)3(a,b)=(|a|,|b|).性質(zhì)4(a,b,c)=(a,b),c).例4求(-84,120),(-120,-72),(24,-60,-96).3n1例5設(shè)n是任意整數(shù),證明力是既約分?jǐn)?shù).即 d|1,d=1證明設(shè)d=(3n+1,5n+2),則d|

9、3(5n+2)-5(3n+1),所以3n+1與5n+2互質(zhì).作業(yè)1.利用輾轉(zhuǎn)相除法求(84,90).2.求(120,36).3n13 .設(shè)n是整數(shù)，證明二二是既約分?jǐn)?shù)。7n2§3整除的進(jìn)一步性質(zhì)及最小公倍數(shù)1 .整除的進(jìn)一步性質(zhì)推論1設(shè)a,b不全為零，那么有s,t£Z使得as+bt=(a,b).證明將(*)中每式中的余數(shù)解出得rnrn 1, rn 2,L , r2, ri的表達(dá)式依次代入到rnrn 2rn 1qn 中就得 au+bv= rn =(a,b尸d,u,vC Z.r2rn0n,rn1n3rn21,2b用2,1abq,再將例1用輾轉(zhuǎn)相除法求(120,54),并求整數(shù)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.練習(xí)用輾轉(zhuǎn)相除法求(84,45),并求整數(shù)u,v使得84u+45v=(84,45).設(shè)a,b都是正整數(shù)，問a,b的公因數(shù)與最大公因數(shù)有什么關(guān)系?例2求(12,18)及12與18的所有正的公因數(shù)；通過這個例子，請同學(xué)們觀察最大公因數(shù)與公因數(shù)有何關(guān)系？能否提出自己的猜想？能否證明自己的猜想?性質(zhì)1設(shè)d是a,b的最大公因數(shù)，那么,a,b的任一公因數(shù)

11、都是d的因數(shù).證明如果d=(a,b),由性質(zhì)2有u,vZ使得au+bv=d.設(shè)s是a,b的任一公因數(shù)，則s|au,s|bv,且s|au+bv,即s|d.ab性質(zhì)2如果d=(a,b),則(了，了)=1.性質(zhì)3如果(a,c)=1,且c|ab,則c|b.性質(zhì)4如果(a,c)=1,則(ab,c)=(b,c).性質(zhì)5如果(a,b)=1,且a|c,b|c,則ab|c.例3證明三個連續(xù)整數(shù)的積一定可被6整除.2最小公倍數(shù)定義如果m是ai,a2,L,an中每一個數(shù)的倍數(shù)，則稱m是整數(shù)a1,a2,L,an的一個公倍數(shù).al,a2，L,an的公倍中最小正整數(shù)稱為al,a2，L，an的最小公倍數(shù).用閏,出,1_a來

12、表示.例如2,4,-3=12,15,12,20=60,6,10,15=30.定理3a1，a2，L，an=|a1|,|a2|,-,|an|.定理4設(shè)a,b是兩個正整數(shù)，則(i)a,b的任一公倍數(shù)是a,b的倍數(shù);ab(ii)a,b=(ab).而且若(a,b)=1,則a,b=ab.證明(i)設(shè)m是a,b的任一公倍數(shù)，而且m=ta,b+r,0<r<a,bab，因m,a,b都是a,b的公倍數(shù)，由r=m-ta,b知r也是a,b的公倍數(shù)，若0<r<a,b,則這與a,b的最小性矛盾.故r=0,m=ta,b.aab(ii)記d=ab，則d是整數(shù)，由a|a,b,a|a,b及dbabda知d

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

14、2 .求(84,45),并求整數(shù)u,v使得84u+45v=(84,45)斗質(zhì)數(shù)算術(shù)基本定理1.質(zhì)數(shù)定義設(shè)整數(shù)a>1,如果a除了1和a外再無其它正因數(shù)，則稱a為質(zhì)數(shù)，也稱為素數(shù).否則，稱a為合數(shù).2,3,5,7,11都是質(zhì)數(shù)，4,6,8,9,10都是合數(shù).1-100內(nèi)有素數(shù)25個,1-1000內(nèi)有素數(shù)168個,1-10000內(nèi)有素數(shù)1229,10萬內(nèi)有素數(shù)9592個,100萬之內(nèi)78498個.定理1設(shè)整數(shù)a>1,則a除1外的最小正因數(shù)q是素數(shù)，而且當(dāng)a是合數(shù)時,q&Ja證明假定q是合數(shù)，設(shè)q=bc,1<b,c<q.因b|q,q|a,得b|a,但1<b<

15、q,這與q是a的最小正因數(shù)矛盾.故q是素數(shù).若a是合數(shù)，設(shè)a=qm,由q的最小性知a=qm>qq,即q&Ja素數(shù)判定定理設(shè)整數(shù)a>1,不超過所有素數(shù)為pl,p2,L,pk,如果R?a,i=1,k,則a為素數(shù).例1以下正整數(shù)哪個是素數(shù)？哪個是合數(shù)？231,89,103,169.素數(shù)判別威爾遜定理:設(shè)整數(shù)p>1,那么p是素數(shù)的充分必要條件是p|(p-1)!+1.例2利用威爾遜定理判別3,5,7,11都是素數(shù).p較大時,(p-1)!+1的數(shù)值非常大,在實際運用時不可行。定理2設(shè)P是素數(shù),a為任一整數(shù)，則或P|a,或(P,a)=1.證明因(P,a)|P,P為素數(shù)，所以(P,a

16、尸P,或(P,a)=1.即P|a,或(P,a)=1.2.整數(shù)的唯一分解定理定理3任何a>1的整數(shù)都有標(biāo)準(zhǔn)分解式:a=p11p22Lpkk(3)這里p1,p2,L,pk為不同素數(shù),整數(shù)i0尸i,.,k.推論1若正整數(shù)a>1準(zhǔn)分解式為a=p11p22Lpkk,則a的正因d=p11p22Lpkk,0i,i=1,k.而且a有不同的正因數(shù)(11)(12)L(1k)個.12推論2設(shè)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、因數(shù)(11)(12)L(1k)個;(3)a,b共有公因數(shù)2(11)(12)L(1例3求725760,154200,并求它們的最大公因數(shù)和最小公倍數(shù)解因725760=28X5X11X41,154200=23x3x52x257,所以(725760,154200)=21*35,725760,154200=28X3X52X11X41X257.例4求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個數(shù)(1)123,78；(2)120,54.練習(xí):求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個數(shù):(1)125,70；(2)140,56.22例8設(shè)p,q都是大于3的素數(shù),證明24|pq3質(zhì)數(shù)的多少和質(zhì)數(shù)的求法定理4素數(shù)有無窮多個

18、.證明 反證法 ,設(shè)質(zhì)數(shù)只有k 個:R,P2,L ,Pk,令 Mp1 p2 L pk 1,M>1,于是M有素數(shù)因數(shù)p.因pi?M,i=1,2,k,p|M,所以pwPi,i=1,2,k.這就是說,p1, p2,L,p 是 k+1個不同素數(shù).這與假設(shè)矛盾.1-n之間的所有素數(shù)怎樣求出來？34131423243334434453546364737483845615162526353645465556656675768586781718272837384748575867687778878891019202930394049505960697079808990919293949596979899

19、100按以下步驟進(jìn)行：(1) 刪去1，剩下的后面的第一個數(shù)是2，2是素數(shù)；(2) 刪去2后面被2整除的數(shù)(從4開始),2后面剩下的第一個數(shù)3是素數(shù)；(3) 刪去3后面的被3整除的數(shù)(從9開始),3后面剩下的第一個數(shù)5是素數(shù)；(4) 刪去5后面的被5整除的數(shù)(從25開始),5后面剩下的第一個數(shù)7是素數(shù)；現(xiàn)在表中剩下的就全為素數(shù)了: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.對較小范圍內(nèi)的素數(shù)以上求法方便,對較大范圍內(nèi)的素數(shù),需要編程求素數(shù)了.現(xiàn)在運行程序,求較大范圍內(nèi)的素數(shù).找兩個同學(xué)來求.作業(yè):1

20、.判別1577是否為素數(shù);2.P19:5t；(5) 725760,154200的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍數(shù),并求它們的所有公因數(shù)的個數(shù)。§5函數(shù)x,x及其應(yīng)用1.函數(shù)x,x的定義定義1設(shè)x是實數(shù)，以岡表示不超過x的最大整數(shù)，稱它為x的整數(shù)部分，又稱x=xx為x的小數(shù)部分例13.5=3,-3.5=-4,-0.1=-1,0.1=0,=3,-=-4.性質(zhì)設(shè)x與y是實數(shù),則(1)xyxy；(2)若m是整數(shù),mx=mx；若0x<1,則x=0;(4)(帶余除法)設(shè)a,b是整數(shù)，且b>0,則a=bJ+bb設(shè)a=bqr,0r<b得qbb>b=q,b4所以a=

21、bb+bb.(5)設(shè)a與b是正整數(shù)，則1-a中能被b整除的整數(shù)有b個。證明能被b整除的正整數(shù)是b,2b,3b,，因此，若數(shù)1,2,a中能被b整除的整數(shù)有k個，則kba<(k+1)bakb<k+1k=b.例2不超過101且是5的倍數(shù)的正整數(shù)有1015-=20個,100-500的整數(shù)中7的倍數(shù)的正整數(shù)有7-997=71-14=57.2.函數(shù)岡的應(yīng)用k設(shè)p是素數(shù),n是整數(shù)，如果pIn,1k?n,則稱p恰好整除n.例3設(shè)P是素數(shù)，那么在1-n的整數(shù)中，恰好被kp整除的整數(shù)有多少個?定理1在n!的標(biāo)準(zhǔn)分解式中，質(zhì)因數(shù)p的指數(shù)是nnnh=+/+1+ppp證明在1,2,3,n中，nn恰被p整除的

22、整數(shù)有-二個；ppnn恰被p整除的整數(shù)有W-F個；ppnn恰被p整除的整數(shù)有F-F個;,pp恰被p整除的整數(shù)有7-T7個,，于是PPnnnnnnnnnh=T-T2+2(-?-3)+3(-4)+-+r(-7-)+=-+pppppppppnn性質(zhì)TT=7/r.pp例3求50!的標(biāo)準(zhǔn)分解式中，素數(shù)2,3,5的指數(shù)，并確定50!的十進(jìn)制數(shù)的末尾0的個數(shù).練習(xí)1:200-300的整數(shù)中，求11的倍數(shù)的整數(shù)的個數(shù).練習(xí)2:60!的十進(jìn)制數(shù)的末尾0的個數(shù).作業(yè)P23:1t.2t,求100!的十進(jìn)制數(shù)的末尾0的個數(shù).習(xí)題課第二章不定方程§1二元一次不定方程1. 二元一次不定方程概念雞雛各幾何?例1百

23、雞問題：“雞翁一，值錢五，雞母一，值錢3,雞雛三，值錢一.百錢買百雞，問雞翁、雞母、設(shè)百錢買雞翁、雞母、雞雛分別x只、y只、z只.依題意得x+y+z=100,且5x+3y+z/3=100.整理得14x+8y=200且x+y+z=100.這里要求x,y,z都是非負(fù)整數(shù).14x+8y=200稱為二元一次不定方程.二元一次不定方程的一般形式為ax+by=c,(a,b,cZ).如果整數(shù)m,n滿足am+bn=c,則稱m,n為ax+by=c的一組整數(shù)解,ax+by=c的一組已知整數(shù)解,也稱為特解.2. 二元一次不定方程解法定理1二元一次不定方程ax+by=c有整數(shù)解的充分必要條件是,(a,b)|c.證明若

24、不定方程ax+by=c有整數(shù)解m,n,則am+bn=c,因為(a,b)|a,(a,b)|b,所以(a,b)|am+bn,即(a,b)|c.反之，若(a,b)|c,設(shè)c=t(a,b).由第一章§3定理1知,有整數(shù)u,v使得au+bv=(a,b),兩邊都乘以t得aut+bvt=t(a,b)=c,即ut,vy是ax+by=c的整數(shù)解。定理2二元一次不定方程ax+by=c,(a,b)=1(1)有整數(shù)解m,n,則方程的一切整數(shù)解為x=m-bt,y=n+at,tC2,或x=m+bt,y=n-at,tCZ.(2)證明易知t乙由(2)得到的整數(shù)x,y都是方程的解.設(shè)x,y是(1)的任一整數(shù)解,于是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),設(shè)x-m=bt,tZ,a(x-m)=-b(y-n)得y-n=-at,這樣就得x=m-bt,y=n+at,t6Z.3. 例子與應(yīng)用例1求14x+8y=200的一切整數(shù)解和所有非負(fù)整數(shù)解.例2求111x-321y=75的一切整數(shù)解.例3甲物品每件12元，乙物品每件18元，現(xiàn)用100元錢去買這兩種物品，若要求每種物品至少買1件，且盡量不?；蛏偈ｅX，問甲乙物品各買多少件？作業(yè)P31:1(a),2.2多元一次不定方程其中a1,a2,L,an,N

26、Z.n2是整數(shù).n 元一次不定方程的一般形式為a1x1 a2x2 LanxnN(1)Th1不定方程(1)有整數(shù)解充分必要條件是,(a1,a2,L,an)|N.例1求9x+24y-5z=1000的一切整數(shù)解.解因(9,24,-5)=1,所以不定方程有整數(shù)解，因(9,24)=3,可設(shè)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寫成分母兩兩互質(zhì)的三個既約分?jǐn)?shù)之和17xyz解因60=3X4X5，設(shè)60

27、22不定方程x y z的一組整數(shù)解(x,y,z)稱為一組勾股數(shù).例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股數(shù).2224定理不定方程x y z ,(1)滿足 x>0,y>0,z>0,(x,y)=1,2 |x(2)2. 22. 2一切正整數(shù)解可由下式表出：x=2ab,y= a b ,z= a b,整理得20x+15y+12z=17.因(20,15,12=1,不定故方程有整數(shù)解，設(shè)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.當(dāng)t=s=0時,x=-y=z=1,此時有作業(yè):1求3x+6y-5z=15的一切整數(shù)解.S勾股數(shù)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求不定方程的全部整數(shù)解xy=6, xy-x+y-4=0.解x=±1且y=±6,或乂=±6,且y=±1,或乂=±2,且丫=±3,或x=±3,且丫=±2。原方程可變?yōu)?x+1)(y-1)-3=0,即(x+1)(y-1)=3.所以有x+1=±1且y-1=±3,或x+1=±3,且y-1=±1.故得不定方程的全部整數(shù)解為x=0,y=4;x=-2,y=-2;x=2,y=2,x=-4,y=0.222作業(yè):1.寫出不定方程xyz的滿足x>0,y>0,

30、z>0,(x,y)=1,2|x的2組正整數(shù)解2.求不定方程xy-x-y-4=0的全部整數(shù)解.第三章同余國同余的概念及其性質(zhì)1 .同余及性質(zhì)定義設(shè)m是正整數(shù)，稱m為模.a,b乙如果a,b被m除所得的余數(shù)相同，則稱a,b對模m同余，記為a書(modm).如果a,b被m除所得的余數(shù)不同,則稱a,b對模m不同余,記為a?b(modm).例如4目(mod3),6鳥1(mod5),4?5(mod3),6?8(mod5).定理1整數(shù)a,b對模m同余的充分必要條件是，m|a-b,即a=b+mt,t乙證明必要性，若a書(modm).可設(shè)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.充分性,設(shè)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).同余的性質(zhì)甲: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 .同余的應(yīng)用A.3(9)|a的條件設(shè)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的條件設(shè)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 設(shè) 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.作業(yè)：1.p53:2.§2剩余類及完全剩余系1 .模m的剩余類及完全剩余系設(shè)m是正整數(shù),Z是整數(shù)集，令Kr=mt+r|tCZ,r=0,1，,m-1,則K0,K1,，Km1稱為模m的剩余類.易知，a,bKr，則a書(modm).稱a為"中其它數(shù)

34、的剩余.設(shè)arKr,r=0,1,m-1,稱a0,a1,，am1為模m的完全剩余系.定義設(shè)m是正整數(shù),0,1,m-1稱為模m的非負(fù)最小完全剩余系.m,m1,L,1,0,1,L,m1,或-m1,L,1,0,1,L,-m為偶數(shù)時，22222稱為模m的絕對最小完全剩余系；m為奇數(shù)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的非負(fù)最小完全剩余系和絕對最小完全剩余系2 .完全剩余系的判定定理1m個整數(shù)a1,a2,，am為模m的完全剩余系的充分必要條件為，a1,a2,.,am對模m兩兩不同余.定理2設(shè)m是正整數(shù),(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的一組完全剩余系,它的每一個數(shù)都是偶數(shù);寫出模9的一組完全剩余系,它的每一個數(shù)都是奇數(shù)作業(yè)：1.分別寫出模7、模8的非負(fù)最小完全剩余系、絕對最小完全剩余系.3 簡化剩余系與歐拉函數(shù)1. 簡化剩余系、歐拉函數(shù)定義若模m的一個剩余類里的數(shù)與m互質(zhì),則稱這個剩余類為與模m互質(zhì)的.對與模m互質(zhì)的全部剩余類,從每一類里任取一數(shù)組成的集合,叫做模m的簡化剩余系.m=6時，K1,K5是全部與模m互質(zhì)的剩余類,1,5是模6的簡化剩余系.m=8時，K1,K3,K5,K7是模8的簡化剩余系.定義設(shè)a是正整數(shù)，歐拉函數(shù)(a)=0,1，,a-1中與a互質(zhì)的整數(shù)的個數(shù)

37、.例如(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,(7)=6.模m的一個簡化剩余系中含有(m)個數(shù)。2. 簡化剩余系的判定定理1模m的剩余類Kr與模m互質(zhì)的是a乙使得(a,m)=1.與模m互質(zhì)的剩余類的個數(shù)是(m).模m的每一個簡化剩余系是由與m互質(zhì)的對模m兩兩不同余的(m)個整數(shù)組成.定理3設(shè)m是正整數(shù)，(a,m)=1,x1,x2，,x(m)是模m的一個簡化剩余系，則ax1,ax2ax(m) 是模 m 的一個簡化剩余系定理4若m1,m2是互質(zhì)的兩個正整數(shù)，x1,x2分別通過模的簡化剩余系，則m1x2+m2x1通過模m1m2的簡化剩余系.推論若m1,0是互質(zhì)的兩個正

38、整數(shù)，則(m1m2)(mJ (m2)一1一2k定理5設(shè)正整數(shù)a的標(biāo)準(zhǔn)分解式為a=p1p2Lpk，則(a). p11 1( p1 1)p22 1( p2 1)L P1a(1kk 1( Pk1).力(11一)L (1p2p;)證明在數(shù)列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互質(zhì)的整數(shù)有P(p-1)個，即(P)P(P1)作業(yè)P60:3.勢歐拉定理費爾瑪定理及其應(yīng)用貝U a (m) 1(mod m)1 .歐拉定理費爾瑪定理定理1(Euler)設(shè)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推論(費爾瑪定理)設(shè)P是素數(shù)，則a1(modP),而且aeZ,aa(modP).證明若p|a,則aPa0(modP),若(a,m)=1,則aP11(modP),所以paa(modP).P1q1例1設(shè)p,q是不同的素數(shù)，證明qp1(modpq).P1q1證明因p,q是不同的素數(shù)

40、，所以(p,q)=1,由費爾瑪定理知,qp1(modp),P1q1P1q1qp1(modq).由同余的性質(zhì)得，qp1(modpq).例2設(shè)p*2,5為素數(shù)，整數(shù)a的十進(jìn)制數(shù)由p-1位，而且每一位上的數(shù)字都是9,證明p|a.P1證明因p*2,5為素數(shù)，所以(10,p)=1,由費爾瑪定理得,a=99-9=101目(modp),即p|a.例3若變量x取整數(shù)時，多項式P(x)=b0b1xLbnxn的值總為整數(shù)，則稱P(x)-(x13x)為整值多項式.證明，2730是整值多項式.證明2730=2X3X5X7X13，當(dāng)x取整數(shù)值時，由費爾瑪定理，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兩兩互質(zhì)，由整除的性質(zhì)知,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設(shè)106k4,k為正整數(shù)，于是1010106k10101034(mod7),這就是說，從今天起再過10天是星期五(1+4)。20112011例5求2011被8除的余數(shù)。作業(yè):P64:1.例32.分?jǐn)?shù)與循環(huán)小數(shù)定義如果無限小數(shù)0.a1a2LanL(an0,1,9)從任何一位數(shù)后不全為0,且能找到兩個整數(shù)s>0,t>0,使得asiasikt,i=1,2,t,k=0,1,2,(*)則稱它為循環(huán)小數(shù)，并簡記為0.a1a2Lggasas1Lastqbq10t對滿足(*)的最小正整數(shù)gt,稱as1Lgast為循環(huán)節(jié)，稱t為循環(huán)節(jié)的長度

43、.若最小的s=0,那小數(shù)就叫做純循環(huán)小數(shù)，否則叫做混循環(huán)小定理2有理數(shù)b,0<a<b,(a,b)=1,能表成純循環(huán)小數(shù)的充分必要條件是，(b,10)=1.推論證明有理數(shù)b,0<a<b,(a,b)=1,是純有限小數(shù)的充分必要條件是(b,10)w1.必要性：若有理數(shù)b能表成純循環(huán)小數(shù)，則由0<tb=0a1a2LataLatL=0QazLat+10BaazLataL10taa1a2Lata1a2Lata1LatLat=q+b.所以a(10充分性：如果(b,10)=1,由定理1知有一正整數(shù)ttat(10t1)a0q(101)b101令q=a110t10.a1a2Latb=

44、0.a1a2Lata1L定理3max(,a210t2L10at1，又由10taqb有理數(shù)b,0<a<b,(a,b)=1,b<1及定義知atL.于是1bq,因(a,b)=1,所以b|10使彳#10t1(modb),0<tat,顯然前比山，at不全為9,也不全為0.而且F1,設(shè)10t1=qb,<(b)，又有10taa貝-0tqb=1,故(b,10)=1.(modb),設(shè)10aqba,則q1a10t10tb0.a1a2Lat1a10tba反復(fù)利用b0.a1a2Lat1a10tb即得b1,不全為0910)=1,b11,則b能表成純循環(huán)小數(shù).其中不循環(huán)部分的位數(shù)是四章同余方程§1基本的概念及一次同余方程1.同余方程的概念n-c7定義設(shè)f(x)=a0a1xLanx,這里3iZ,i=0,1,n.m是正整數(shù)，則稱na。axLanxf(x)=01n0(modm).(1)為同余式，或模m的同余方程.若an/0(modm),n稱為同余方程(1)的次數(shù).若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