版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
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整除的簡單性質(zhì)(
2、1) 如果c|b,b|a,那么c|a;(2) 如果d|a,d|b,那么對任意整數(shù)m,n,都有d|ma+nb.如果ai,a2,L,an都是m的倍數(shù),qi,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<r<b.(1)這里q稱為
3、b除a的商,r稱為b除a的余數(shù).例如-5=3義(-2)+15=3義1+2-5=(-3)義2+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.可用計算器進行.具體操作:輸入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ì)能被2整除的整數(shù)稱為偶數(shù).如,0
4、,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ù)=(禺?dāng)?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ù),試證實8|a1.例6設(shè)n是正整數(shù),證實形如3n-1整數(shù)不是完全平方數(shù).證實對任意整a,設(shè)
5、a=3q或a=3q±1,于是2c2222a=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è)ai,02,L,a,d都是整數(shù),dW0,如果dai,i=1,2,n,稱d是a1,a
6、2,L,an的公因數(shù),a1,L,an的公因數(shù)中最大的整數(shù)稱為最大公因數(shù).記為(a,電L,an).如果(ai2,L©)=1,那么稱a1,a2,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ù),而且有abqr1,0r1b;b肌r2,0r21;rir%r3,0r3(*)n2.14n,0rnrnl;rn1NnI-(a,b)n.例2用輾轉(zhuǎn)相除法求(123,78),練習(xí):用輾轉(zhuǎn)相除法求
7、(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).由(*)式知b1r2Ln1n0,而n是有限正整數(shù),再由性質(zhì)1得(a,b)(.1)(1,2)=(n2,n1)(n1,n)(n,.)n.2 .最大公因數(shù)的性質(zhì)最大公因數(shù)的幾個性質(zhì)
8、:性質(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ù),證實;7是既約分?jǐn)?shù).5n2證實設(shè)d=(3n+1,5n+2),WJd|3(5n+2)-5(3n+1),即d|1,d=1,作業(yè)1.利用輾轉(zhuǎn)相除法求(84,90).2.求(120,36).3n13 .設(shè)n是整數(shù),證實是既約
9、分?jǐn)?shù).7n2§3整除的進一步性質(zhì)及最小公倍數(shù)1 .整除的進一步性質(zhì)推論1設(shè)a,b不全為零,那么有s,tZ使得as+bt=(a,b).證實將(*)中每式中的余數(shù)解出得rnrn2rn1qn,rn1rn3rn2qn1,r2brq2,r1abql,再將rn1,rn,L,2,r1的表達式依次代入到rnrn2rn1.中就得au+bv=rn=(a,b尸d,u,vZ.例1用輾轉(zhuǎn)相除法求(120,54),并求整數(shù)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.練習(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ù)都是d的因數(shù).證實如果d=(a,b),由性質(zhì)2有u,vCZ使得au+bv=d.設(shè)s是a,b的任一公因數(shù),那么s|au,s|bv,且s|au+bv,即s|d.ab性質(zhì)2如果d=(a,b),那么(-,二-)=
11、1.dd性質(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是a1,02,L,an中每一個數(shù)的倍數(shù),那么稱m是整數(shù)a,a2,L,an的一個公倍數(shù).aba2,L,an的公倍中最小正整數(shù)稱為al,a2,L,an的最小公倍數(shù).用a1,a2,L,an來表示.例如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的任
12、一公倍數(shù)是a,b的倍數(shù);ab(ii)a,b=(ab).而且假設(shè)(a,b)=1,那么a,b=ab.證實(i)設(shè)m是a,b的任一公倍數(shù),而且m=ta,b+r,0<r<a,babb,因m,a,b都是a,b的公倍數(shù),由r=m-ta,b知r也是a,b的公倍數(shù),假設(shè)0<r<a,b,那么這與a,b的最小性矛盾.故r=0,m=ta,b.ab(ii)記d=ab,那么d是整數(shù),由a|a,b,a|a,bb就da知d|a,d|b,即d是a,b的公因數(shù).ab設(shè)h是a,b的任一公因數(shù),由habab的公倍數(shù)及TH16知a,b|卜,即abhZ,所以h|d,ab(a,b)=d,從而(a,b尸ab.定理5
13、設(shè)d,%,1,an都是正整數(shù),令qg3,觀自觀,n1自辦,那么3,&,L,斗R定理19設(shè)a1,a2,L,an是n(>2)個正整數(shù),且兩兩互素,那么&,a2,L,ana1a2Lan例2求123,456,-789例3求正整數(shù)a,b,滿足:a+b=120,(a,b)=24,a,b=144.例14設(shè)a,b,c是正整數(shù),那么a,b,c=abc(ab,bc,ca)作業(yè):P14:1.2 .求(84,45),并求整數(shù)u,v使得84u+45v=(84,45)§4質(zhì)數(shù)算術(shù)根本定理1.質(zhì)數(shù)定義設(shè)整數(shù)a>1,如果a除了1和a外再無其它正因數(shù),那么稱a為質(zhì)數(shù),也稱為素數(shù).否那么,稱
14、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<VO.證實假定q是合數(shù),設(shè)q=bc,1<b,c<q.因b|q,q|a,得b|a,但1<b<q,這與q是a的最小正因數(shù)矛盾.故q是素數(shù).假設(shè)a是合數(shù),設(shè)a=qm,由q的最小性知a=qm>qq,即q&Ja.素數(shù)判定定理設(shè)整數(shù)a>1,不超過Va所有素數(shù)為pl,p2
15、,L,戰(zhàn),如果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ù).當(dāng)p較大時,(p-1)!+1的數(shù)值非常大,在實際運用時不可行.定理2設(shè)P是素數(shù),a為任一整數(shù),那么或P|a,或(P,a)=1.證實因(P,a)|P,P為素數(shù),所以(P,a尸P,或(P,a)=1.即P|a,或(P,a)=1.2.整數(shù)的唯一分解定理12k定理3任彳a>1的整數(shù)都有標(biāo)準(zhǔn)分解式:a=p1p2Lpk(3)這里pl,p2,L,Pk為不同素數(shù)
16、,整數(shù)i0,i=1,k.推論1假設(shè)正整數(shù)a>1的標(biāo)準(zhǔn)分解式為a=p11p22Lpkk,那么a的正因數(shù)d為d=p1p2Lpk,0ii,i=1,k.而且a有不同的正因數(shù)(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共有正公因數(shù)(11)(12)L(1k)個;(3)a,b共有公因數(shù)2(11)(12)L(1k)個.例3求725760,154200的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍數(shù)832解因725
17、760=2X5X11X41,154200=2X3X5X257,所以(725760,154200)=2X5,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|pq.3質(zhì)數(shù)的多少和質(zhì)數(shù)的求法定理4素數(shù)有無窮多個.證實反證法,設(shè)質(zhì)數(shù)只有k個:R,P2,L,%,令Mp1p2Lpk1,M>1,于是M有素數(shù)因數(shù)p.因pi?M,i=1,2,k,p|M,所以pwpi,i=1.
18、2, ,k.這就是說,pl,p2,L,pk,p是k+1個不同素數(shù).這與假設(shè)矛盾.1-n之間的所有素數(shù)怎樣求出來123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以下步驟進行:(1) 刪去1,剩下的后面的第一個數(shù)是2,2是素數(shù);(2) 刪去2后面被2整除的數(shù)(從4開
19、始),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.判別1577是否為素數(shù);:5t;3.求725760,154200的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍
20、數(shù),并求它們的所有公因數(shù)的個數(shù).§5函數(shù)x,x及其應(yīng)用1.函數(shù)x,x的定義定義1設(shè)x是實數(shù),以岡表示不超過x的最大整數(shù),稱它為x的整數(shù)局部,又稱x=x?x為x的小數(shù)局部.例1=3,=-4,=-1,=0,=3,-=-4.性質(zhì)設(shè)x與y是實數(shù),那么x?y?x?y;(2)假設(shè)m是整數(shù),?m?x=m?x;(3)假設(shè)0?x<1,貝Ux=0;(4)(帶余除法)設(shè)a,b是整數(shù),且b>0,那么a=b+bar設(shè)a=bq?r,0?r<b得.q.,故bb葩總bba(5)設(shè)a與b是正整數(shù),那么1-a中能被b整除的整數(shù)有1b個.證實能被b整除的正整數(shù)是b,2b,3b,?,因此,假設(shè)數(shù)1,2,?
21、,a中能被b整除的整數(shù)有k個,那么kb?a<(k+1)b?k?-<k+1?k=-.例2不超過101且是5的倍數(shù)的正整數(shù)有二1=20個,100-500的整數(shù)中7的倍數(shù)的正整數(shù)有工-:7=71-14=57.5772.函數(shù)x的應(yīng)用k設(shè)P是素數(shù),n是整數(shù),如果p|n,k1kP?n,那么稱p恰好整除n.k例3設(shè)P是素數(shù),那么在1-n的整數(shù)中,恰好被P整除的整數(shù)有多少個定理1在n!的標(biāo)準(zhǔn)分解式中,質(zhì)因數(shù)p的指數(shù)是nnnh=-+-T+F+pppnn恰被p整除的整數(shù)有%-肅個;ppnn恰被p整除的整數(shù)有三-=個;PPnn恰被p整除的整數(shù)有-F個;,ppnn恰被p整除的整數(shù)有T-TT個,于是ppnn
22、nnnnnnnnnh=Z-7+2(-2-3)+3(-3-4)+-+r(-)+=、+幣+之+.pppppppppppnn性質(zhì)/HI/".pp例3求50!的標(biāo)準(zhǔn)分解式中,素數(shù)2,3,5的指數(shù),并確定50!的十進制數(shù)的末尾0的個數(shù).練習(xí)1:200-300的整數(shù)中,求11的倍數(shù)的整數(shù)的個數(shù)練習(xí)2:60!的十進制數(shù)的末尾0的個數(shù).作業(yè)P23:1t.2t,求100!的十進制數(shù)的末尾0的個數(shù).習(xí)題課第二章不定方程§1二元一次不定方程1 .二元一次不定方程概念例1百雞問題:“雞翁一,值錢五,雞母一,值錢3,雞雛三,值錢一.百錢買百雞,問雞翁、雞母、雞雛各幾何設(shè)百錢買雞翁、雞母、雞雛分別x只
23、、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,cCZ).如果整數(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.證實假設(shè)不定方程ax+by=c有整數(shù)解m,n,那么am+bn=cJ3為(a,b)|a,(a,b)|b,所以(a,b)|am
24、+bn,即(a,b)|c.反之,假設(shè)(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,tCZ,或x=m+bt,y=n-at,tZ.(2)證實易知tZ,由(2)得到的整數(shù)x,y都是方程的解.設(shè)x,y是(1)的任一整數(shù)解,于是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),設(shè)x-m=bt,tZ,a(x-m)=-b(y-n)得y-n=-at,這樣就得x=m-bt,y=n+at,tZ.3 .例子與應(yīng)用例1求14x+8y=200的一切整數(shù)解和所有非負(fù)整數(shù)解.例2求111x-321y=75的一切整數(shù)解.例3甲物品每件12元,乙物品每件18元,現(xiàn)用100元錢去買這兩種物品,假設(shè)要求每種物品至少買1件,且盡量不?;蛏偈eX,問甲乙物品各買多少件作業(yè)P31:1(a),2.§2多元一次不定方程n元一次不定方程的一般形式為a1x1a2x2Lan4N(1)其中a1,a2,L,an,NZ.n?2是整數(shù).Th1不定方程(1)
26、有整數(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,sZ,的通解為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è)60345,整理得20x+15y+12z=17.因20,15,12=1,不定故方程有整數(shù)解,設(shè)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.當(dāng)t=s=0時,x=-y=z=1,此時有作業(yè):1求3x+6y-5z=15的一切整數(shù)解.§3勾股數(shù)2221 .不定方程xyz2 22不定方程xyz的一組整數(shù)解x,y,z稱為一組勾股數(shù)例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股數(shù).222定理不定方程xyz,(1)滿足x>0,y>0,z>0,(x,y)=1
28、,2|x(2),乙f2,22,2一切正整數(shù)解可由下式表出: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求不定方程的全部整數(shù)解xy=6,xy-x+y-4=0.解x=±1且y=±6,或x=±6,且y=±1,或x=±2,且
29、y=±3,或x=±3,且y=±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,z>0,(x,y)=1,2|x的2組正整數(shù)解2.求不定方程xy-x-y-4=0的全部整數(shù)解.AfV*弟二早1同余的概念及其性質(zhì)1. 同余及性質(zhì)定義設(shè)m是正整數(shù),稱m為模.a,b乙如果a,b被
30、m除所得的余數(shù)相同,那么稱a,b對模m同余,記為amb(modm).如果a,b被m除所得的余數(shù)不同,那么稱a,b對模m不同余,記為a?b(modm).例如4三7(mod3),6三11(mod5),4?5(mod3),6?8(mod5).定理1整數(shù)a,b對模m同余的充分必要條件是,m|a-b,即a=b+mt,tZ.證實必要性,假設(shè)amb(modm).可設(shè)a=msa=r,b=mua=r,s,uZ,貝Ua-b=m(s-u)=mt,T=s-uCZ.所以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
31、|<m.從而r1=r2,即a三b(modm).同余的性質(zhì)甲:a三b(modm).乙:假設(shè)a三b(modm),bma(modm).丙:假設(shè)amb(modm),bmc(modm),貝Uamc(modm).丁、戊:abi(modm),a2b2(modm),那么a1a2b1b2(modm),a1a2b1b2(modm)bk(modm)那么,假設(shè)a1b1(modm),a2b2(modm),L,aka1a2Lakb1b2Lbk(modm),a1a2Lakb1b2Lbk(modm).由此可得定理2.2. 同余的應(yīng)用(9)|a的條件設(shè)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的條件設(shè)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設(shè)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假設(shè)a=637693,a04L(1)n
33、an=693-637=56,7|56,11?56,13?56,所以7|5a,11?a6,13?a.作業(yè):2.§2剩余類及完全剩余系1 .模m的剩余類及完全剩余系設(shè)m是正整數(shù),Z是整數(shù)集,令Kr=mt+巾CZ,r=0,1,m-1,那么心,K1,Km1稱為模m的剩余類.易知,a,bKr,那么amb(modm).稱a為Kr中其它數(shù)的剩余.設(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
34、為奇數(shù)時,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的非負(fù)最小完全剩余系和絕對最小完全剩余系2.完全剩余系的判定定理1m個整數(shù)a1,a2,am為模m的完全剩余系的充分必要條件為,a1,a2,am對模m兩兩不同余.定理2設(shè)m是正整數(shù),(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的一組完全剩余系,它的每一個數(shù)都是偶數(shù);寫出模9的一組完全剩余系,它的每一個數(shù)都是奇數(shù).作業(yè):1.分別寫出模7、模8的非負(fù)最小完全剩余系、絕對最小完全剩余系.3簡化剩余系與歐拉函數(shù)2 .簡化剩余系、歐拉函數(shù)定義假設(shè)模m的一個剩余類里的數(shù)與m互質(zhì),那
36、么稱這個剩余類為與模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ù).例如(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,(7)=6.模m的一個簡化剩余系中含有(m)個數(shù).(m).模m的每一個簡化剩余系,是3 .簡化剩余系的判定定理1模m的剩余類Kr與模m互質(zhì)的是aCZ,使得(a,m)=1.與模m互質(zhì)的剩余類的個數(shù)是由與mZL質(zhì)的對模m兩兩
37、不同余的(m)個整數(shù)組成.定理3設(shè)m是正整數(shù),(a,m)=1,x1,x2,x(m)是模m的一個簡化剩余系,那么ax1ax2,ax(m)是模m的一個簡化剩余系.定理4假設(shè)3,m2是互質(zhì)的兩個正整數(shù),x1x2分別通過模的簡化剩余系,那么m1x2+m2通過模m1m2的簡化剩余系.推論假設(shè)色,m2是互質(zhì)的兩個正整數(shù),那么Em2)(m1)(m2).一1一2k定理5設(shè)正整數(shù)a的標(biāo)準(zhǔn)分解式為a=p1p2Lpk,那么111,、11/八21/八1k1/八a(1-)(1A(1一)(a)=p1(p11)p2(p21)Lpk(pk1)=p1p2pk證實在數(shù)列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互質(zhì)的整數(shù)有p(p-1)個,即(p)p(p1).作業(yè)P60:3.§4歐拉定理費爾瑪定理及其應(yīng)用1 .歐拉定理費爾瑪定理定理1(Euler)設(shè)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推論(費爾瑪定理)設(shè)p是素數(shù),那么a1(modP),而且aez,aa(modP).證實假設(shè)p|a,那么aPa0(modP),假設(shè)(a,m)=1,那么a1(modP),所以paa(modP).P1q1例1設(shè)p,q是不同的素數(shù),證實qp1(modpq).P1q1證實因p,q是不同的素數(shù),所以(p,q)=1,由費爾瑪定理知,qp1(modp),P1q1dP1q1Aqp1(modq).由同余的性質(zhì)得,qp1(modpq).例2設(shè)pw2,5為素數(shù),整數(shù)a的十進制數(shù)由p-1位,而且每一位上的數(shù)字都是9,證實p|a.P1.證實因
40、p*2,5為素數(shù),所以(10,p)=1,由費爾瑪止理得,a=99-9=101034(mod7),這就是說,從今天起再過10天是星期五(1+4).1=0(modp),即p|a.例3假設(shè)變量x取整數(shù)時,多項式P(x)=bob1xLbnxn的值總為整數(shù),那么稱P(x)為整值多項式.證實,2730(x13x)是整值多項式.證實2730=2X3X5X7X13,當(dāng)x取整數(shù)值時,由費爾瑪定理,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兩兩互質(zhì),由整除的性質(zhì)知,2X3X5X7X13|xx,即2730|例4今天是星期一,問從今天起再過10101010天是星期幾103332g361(mod7),所以1021061(mod7)o又因10-2(mod6),21022(mod6),故1024(mod6)0101010設(shè)106k4,k為正整數(shù),于是106k410例5求202120212021被8除的余數(shù).作業(yè):P64:1.例32.分?jǐn)?shù)與循環(huán)小數(shù)定義如果無限小數(shù)0.a1
42、a2LanL(an0,1,9)從任何一位數(shù)后不全為0,且能找到兩個整數(shù)s>0,t>0,使得asiasikt,i=1,2,t,k=0,1,2,(*)那么稱它為循環(huán)小數(shù),并簡記為g0a向Lasasg1Last對滿足(*)的最小正整數(shù)ggt,稱as1Last為循環(huán)節(jié),稱t為循環(huán)節(jié)的長度.假設(shè)最小的s=0,那小數(shù)就叫做純循環(huán)小數(shù),否那么叫做混循環(huán)小數(shù).定理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è)有理數(shù)b能表成純循
43、環(huán)小數(shù),那么由0<b<1及定義知qbq10tab=0.10tba1a2LaLatL=0a1a2Lat+10tg3.a1a2LataLa1a2Lat+0a1a2Lata1LatL.t=q+b.所以a(10充分性:如果(b,10)=1,由定理1知有一正整數(shù)(10t1)a0,q=a110t10.a1a2Latb=0.aa2LataLatL.于是1)bq,因(a,b)=1,所以b|10t1,設(shè)10t1=qb,那么10qb=1,故(b,10)=1.t使彳#10t1(modb),0<t<(b),又有10taa(modb),設(shè)10aqba,那么q(10t1)a10tba210t2L1
44、0at110taqbatL=0.aLat定理3有理數(shù)b,0<a<b,(a,b)=1,max(,)at,顯然a1,a2,L,at不全為9,也不全為0.而且a_q_a得b10tb2g5b1,四章同余方程§1根本的概念及一次同余方程1a10tb0.a1a2Lat10tba反復(fù)利用b0.a1a2Lat10tb即得不全為0,(b1,10)=1,bl1,那么b能表成純循環(huán)小數(shù).其中不循環(huán)局部的位數(shù)是1.同余方程的概念nc7定義設(shè)f(x)=a0a1xLanx,這里aiZ,i=0,1,是正整數(shù),那么稱nf(x)=a0alXLanx0(modm).(1)為同余式,或模m的同余方程.假設(shè)an/0(modm),n稱為同余方程(1)的次數(shù).假設(shè)aZ而且f(a)三0(modm),那么稱xma(modm歷同余方程(1)的解.-2例1f(x)=xx3m0(mod5)是模5的2次同余方程,由于f(1)=5三0(m
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 人教版七年級數(shù)學(xué)上冊:2.1《整式》聽評課記錄5
- 五年級上冊數(shù)學(xué)聽評課記錄《4.5 探索活動:梯形的面積》(3)-北師大版
- 中圖版地理七年級下冊《第五節(jié) 黃土高原》聽課評課記錄5
- 青島版八年級上冊數(shù)學(xué)聽評課記錄《3-3分式的乘法與除法》
- 小學(xué)二年級數(shù)學(xué)口算速算試題
- 小學(xué)二年級第一學(xué)期班主任工作總結(jié)
- 五年級口算題帶答案
- 浙教版數(shù)學(xué)七年級下冊3.2《單項式的乘法》聽評課記錄
- 粵人版地理八年級下冊《第一節(jié) 地理區(qū)域》單元整體聽課評課記錄2
- 聽評課記錄三年級語文
- 云南省普通初中學(xué)生成長記錄模板-好ok
- SB/T 10415-2007雞粉調(diào)味料
- JB/T 20036-2016提取濃縮罐
- 考古繪圖基礎(chǔ)
- GB/T 3452.4-2020液壓氣動用O形橡膠密封圈第4部分:抗擠壓環(huán)(擋環(huán))
- GB/T 32574-2016抽水蓄能電站檢修導(dǎo)則
- 《社會主義市場經(jīng)濟理論(第三版)》第十三章社會主義市場經(jīng)濟標(biāo)準(zhǔn)論
- 變更索賠案例分析
- 2022年4月自學(xué)考試06093《人力資源開發(fā)與管理》歷年真題及答案
- 《花婆婆》兒童繪本故事
- DB44∕T 2149-2018 森林資源規(guī)劃設(shè)計調(diào)查技術(shù)規(guī)程
評論
0/150
提交評論