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

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

2、939?整除的簡(jiǎn)單性質(zhì)(1)如果c|b,b|a,那么c|a; (2)如果d|a,d|b,那么對(duì)任意整數(shù)m,n,都有d|ma+nb.(3)如果都是m的倍數(shù),是任意整數(shù),那么是m的倍數(shù).(4)如果c|a,d|b,那么cd|ab。例如： 2|4,2|(-6),那么2|4+(-6),2|4-(-6). 2|4,3|(-6),那么2×3|4×(-6).例2證明任意2個(gè)連續(xù)整數(shù)的乘積,一定可被2整除.練習(xí) 證明任意3個(gè)連續(xù)整數(shù)的乘積,一定可被3整除.2.帶余除法設(shè)a,b是整數(shù),且b>0,那么有唯一一對(duì)整數(shù)q,r使得 a=bq+r,0r b. (1)這里q稱為b除a的商,r稱為b除

3、a的余數(shù).例如-5=3×(-2)+1 5=3×1+2 -5=(-3)×2+15=(-3)×(-1)+2 15=(-5)×(-3), -24=(-2)×12.事實(shí)上,以b除a的余數(shù)也可以是負(fù)的.例如 -5=3×(-1)-2=3×(-2)+1.求b除a的余數(shù),也稱為模運(yùn)算(取余):mod.可用計(jì)算器進(jìn)行.具體操作:輸入a-按mod(取余)鍵-輸入b-按=鍵得出余數(shù).如果b除a的余數(shù)=0,則b|a;如果b除a的余數(shù)0,則ba.例3 利用計(jì)算器求余數(shù):(1) 7除127;(2)11除-129 ;(3)46除-9529;(4

4、)-29除5939奇數(shù)、偶數(shù)及性質(zhì)能被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ù)×偶數(shù)=偶數(shù),偶數(shù)×奇數(shù)=偶數(shù),奇數(shù)×奇數(shù)=奇數(shù).例如 2+4,2-4,3+1,3-1,3+4,6+5設(shè)a,b是任意兩個(gè)整數(shù),則a+b與a-b同奇同偶.例如3+5,3-5,6+3,6-3,例4設(shè)a,b,n是任意3個(gè)整數(shù),而且,證明n是

5、偶數(shù).例5設(shè)a是任一奇數(shù),試證明8|.例6設(shè)n是正整數(shù),證明形如3n-1整數(shù)不是完全平方數(shù).證明 對(duì)任意整a,設(shè)a=3q或a=3q±1,于是=9或 =9±6q+1=3(3±2q)+1.即3n-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ù)的概念：幾個(gè)數(shù)的公有因數(shù)叫做這幾個(gè)數(shù)的公因數(shù).公因數(shù)中最大的整數(shù)稱為這幾個(gè)數(shù)的最大公因數(shù).(1)幾個(gè)數(shù):不能確定;(2)因數(shù)、公因數(shù):都是正整數(shù); 最大公因數(shù):沒(méi)

6、有專門的符號(hào).定義設(shè),d都是整數(shù),d0,如果,i=1,2,n,稱d是的公因數(shù),的公因數(shù)中最大的整數(shù)稱為最大公因數(shù).記為.如果=1,則稱互質(zhì)。例1 (-6,8)=2,(-3,6,-9,15)=3,(1,2,3,-4)=1.在中小學(xué)數(shù)學(xué)里,求正整數(shù)a,b的最大公因數(shù)主要有這個(gè)樣幾種方法：(1)觀察法；(2)將a,b的所有公因數(shù)都求出來(lái),再?gòu)闹刑糇畲蟮模?3)用短除法.輾轉(zhuǎn)相除法:設(shè)a,b是正整數(shù),而且有 （*）。例2用輾轉(zhuǎn)相除法求(123,78),練習(xí):用輾轉(zhuǎn)相除法求(66,54).下面說(shuō)明輾轉(zhuǎn)相除法的正確性.先證明性質(zhì)1設(shè)整數(shù)a,b,c不全為0,而且有整數(shù)q使得a=bq+c則(a,b)=(b,c

7、).證明 由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). 由(*)式知而n是有限正整數(shù),再由性質(zhì)1得=.2.最大公因數(shù)的性質(zhì)最大公因數(shù)的幾個(gè)性質(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

8、|,|b|).性質(zhì)4 (a,b,c)=(a,b),c).例4求(-84,120),(-120,-72),(24,-60,-96).例5設(shè)n是任意整數(shù),證明是既約分?jǐn)?shù).證明 設(shè)d=(3n+1,5n+2),則d|3(5n+2)-5(3n+1),即d|1,d=1，所以3n+1與5n+2互質(zhì).作業(yè) 1.利用輾轉(zhuǎn)相除法求(84,90). 2.求(120,36). 3.設(shè)n是整數(shù)，證明是既約分?jǐn)?shù)。§3整除的進(jìn)一步性質(zhì)及最小公倍數(shù)1.整除的進(jìn)一步性質(zhì)推論1設(shè)a,b不全為零,那么有s,tZ使得as+bt=(a,b).證明 將(*)中每式中的余數(shù)解出得,再將的表達(dá)式依次代入到中就得au+bv=(a,b

9、)=d,u,vZ.例1用輾轉(zhuǎn)相除法求(120,54),并求整數(shù)u,v使得120u+54v=(120,54).解120=2×54+12,54=12×4+6,12=6×2,(120,54)=6.12=120-2×54,6=54-12×4=54-(120-2×54)×4=120×(-4)+54×9. u=-4,v=9.練習(xí)用輾轉(zhuǎn)相除法求(84,45),并求整數(shù)u,v使得84u+45v=(84,45).設(shè)a,b都是正整數(shù),問(wèn)a,b的公因數(shù)與最大公因數(shù)有什么關(guān)系？ 例2 求(12,18)及12與18的所有正的公因數(shù)

10、；通過(guò)這個(gè)例子,請(qǐng)同學(xué)們觀察最大公因數(shù)與公因數(shù)有何關(guān)系？能否提出自己的猜想？能否證明自己的猜想？性質(zhì)1 設(shè)d 是a,b的最大公因數(shù),那么,a,b的任一公因數(shù)都是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.性質(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證明 三個(gè)連續(xù)整數(shù)的積一定可被6整除.2最小公倍數(shù)定義 如果m是中每一個(gè)數(shù)的倍數(shù),則稱m是

11、整數(shù)的一個(gè)公倍數(shù).的公倍中最小正整數(shù)稱為的最小公倍數(shù).用來(lái)表示. 例如 2,4,-3=12,15,12,20=60,6,10,15=30. 定理3 =|,|,|.定理4 設(shè)a,b是兩個(gè)正整數(shù),則(i)a,b的任一公倍數(shù)是a,b的倍數(shù)；(ii)a,b=.而且若(a,b)=1,則a,b=ab.證明(i)設(shè)m是a,b的任一公倍數(shù),而且m=ta,b+r,0r<a,b,因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.(ii)記d=,則d是整數(shù),由a|a,b,a|a,b及,知d|a,d|b,即d

12、是a,b的公因數(shù). 設(shè)h是a,b的任一公因數(shù),由是a,b的公倍數(shù)及TH16知a,b|,即,所以h|d, (a,b)=d,從而(a,b)=.定理5 設(shè)都是正整數(shù),令,則.定理19設(shè)是n(2)個(gè)正整數(shù),且兩兩互素,則例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=作業(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外再無(wú)其它正因數(shù),則稱a為質(zhì)數(shù),也稱為素?cái)?shù).否則,稱a為合數(shù).

13、 2,3,5,7,11都是質(zhì)數(shù)，4,6,8,9,10都是合數(shù). 1-100內(nèi)有素?cái)?shù)25個(gè),1-1000內(nèi)有素?cái)?shù)168個(gè),1-10000內(nèi)有素?cái)?shù)1229,10萬(wàn)內(nèi)有素?cái)?shù)9592個(gè),100萬(wàn)之內(nèi)78498個(gè). 定理1設(shè)整數(shù)a>1,則a除1外的最小正因數(shù)q是素?cái)?shù),而且當(dāng)a是合數(shù)時(shí),q. 證明 假定q是合數(shù),設(shè)q=bc,1<b,c<q.因b|q,q|a,得b|a,但1<b<q,這與q是a的最小正因數(shù)矛盾.故q是素?cái)?shù).若a是合數(shù),設(shè)a=qm,由q的最小性知a=qmqq,即q. 素?cái)?shù)判定定理 設(shè)整數(shù)a>1,不超過(guò)所有素?cái)?shù)為,如果a,i=1,k,則a為素?cái)?shù). 例1 以下正

14、整數(shù)哪個(gè)是素?cái)?shù)？哪個(gè)是合數(shù)？ 231,89,103,169.素?cái)?shù)判別威爾遜定理:設(shè)整數(shù)p>1,那么p是素?cái)?shù)的充分必要條件是 p|(p-1)!+1.例2 利用威爾遜定理判別3,5,7,11都是素?cái)?shù).當(dāng)p較大時(shí),(p-1)!+1的數(shù)值非常大,在實(shí)際運(yùn)用時(shí)不可行。定理2 設(shè)P是素?cái)?shù),a為任一整數(shù),則或P|a,或(P,a)=1.證明 因(P,a)|P,P為素?cái)?shù),所以(P,a)=P,或(P,a)=1.即P|a,或(P,a)=1.2.整數(shù)的唯一分解定理定理3 任何a>1的整數(shù)都有標(biāo)準(zhǔn)分解式:a= (3)這里為不同素?cái)?shù),整數(shù),i=1,k. 推論1 若正整數(shù)a>1的標(biāo)準(zhǔn)分解式為a=,則a的正

15、因數(shù)d為d=,i=1,k.而且a有不同的正因數(shù)個(gè).推論2設(shè)a=,b=,i=1,k.則(1)(a,b)=,a,b=，其中,i=1,k.(2)a,b共有正公因數(shù)個(gè);(3)a,b共有公因數(shù)個(gè). 例3 求725760,154200的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍數(shù).解 因725760=×5×11×41, 154200=×3××257,所以(725760,154200)=×5, 725760,154200=×3××11×41×257. 例4求下列各組數(shù)的最大公因數(shù)及其公因數(shù)

16、的個(gè)數(shù):(1)123,78；(2)120,54.練習(xí):求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個(gè)數(shù):(1)125,70；(2)140,56.例8設(shè)p,q都是大于3的素?cái)?shù),證明24|.3質(zhì)數(shù)的多少和質(zhì)數(shù)的求法定理4 素?cái)?shù)有無(wú)窮多個(gè).證明 反證法,設(shè)質(zhì)數(shù)只有k個(gè):,令,M>1,于是M有素?cái)?shù)因數(shù)p.因M,i=1,2,k,p|M,所以p,i=1,2,k.這就是說(shuō),p是k+1個(gè)不同素?cái)?shù).這與假設(shè)矛盾.1-n之間的所有素?cái)?shù)怎樣求出來(lái)？1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33

17、 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98 99 100按以下步驟進(jìn)行：(1)刪去1，剩下的后面的第一個(gè)數(shù)是2，2是素?cái)?shù)；(2)刪去2后面被2整除的數(shù)(從4開(kāi)始),2后面剩下的第一個(gè)數(shù)3是素?cái)?shù)；(3)刪去3后面的被3整除的數(shù)(從9開(kāi)始),3后面剩下的第一個(gè)數(shù)5是素

18、數(shù)；(4)刪去5后面的被5整除的數(shù)(從25開(kāi)始),5后面剩下的第一個(gè)數(shù)7是素?cái)?shù)； L L現(xiàn)在表中剩下的就全為素?cái)?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.對(duì)較小范圍內(nèi)的素?cái)?shù)以上求法方便,對(duì)較大范圍內(nèi)的素?cái)?shù),需要編程求素?cái)?shù)了.現(xiàn)在運(yùn)行程序,求較大范圍內(nèi)的素?cái)?shù).找兩個(gè)同學(xué)來(lái)求.作業(yè):1.判別1577是否為素?cái)?shù);2.P19:5t；3.求725760,154200的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍數(shù),并求它們的所有公因數(shù)的個(gè)數(shù)。§5 函數(shù)x,x及其應(yīng)用1. 函數(shù)x,x的定義定義1

19、 設(shè)x是實(shí)數(shù),以x表示不超過(guò)x的最大整數(shù)，稱它為x的整數(shù)部分，又稱x = x - x為x的小數(shù)部分。例1 3.5=3,-3.5=-4,-0.1=-1,0.1=0,=3,-=-4.性質(zhì) 設(shè)x與y是實(shí)數(shù),則(1)x£yÞx£y；(2)若m是整數(shù),Þm+x=m+x；(3)若0£x<1,則x=0；(4)(帶余除法)設(shè)a,b是整數(shù),且b>0,則a=b+b.設(shè)a=bq+r,0£r<b得,故=q,所以a=b+b.(5)設(shè)a與b是正整數(shù),則1-a中能被b整除的整數(shù)有個(gè)。證明 能被b整除的正整數(shù)是b,2b,3b,L,因此,若數(shù)1,2,

20、L,a中能被b整除的整數(shù)有k個(gè),則kb£a<(k+1)bÞk£<k+1Þk=.例2 不超過(guò)101且是5的倍數(shù)的正整數(shù)有=20個(gè),100-500的整數(shù)中7的倍數(shù)的正整數(shù)有-=71-14=57.2. 函數(shù)x的應(yīng)用設(shè)是素?cái)?shù),n是整數(shù),如果n,n,則稱恰好整除n.例3設(shè)是素?cái)?shù),那么在1-n的整數(shù)中,恰好被整除的整數(shù)有多少個(gè)？定理1 在n!的標(biāo)準(zhǔn)分解式中,質(zhì)因數(shù)p的指數(shù)是 h=+ 證明 在1,2,3,n中, 恰被p整除的整數(shù)有-個(gè); 恰被p整除的整數(shù)有-個(gè); 恰被p整除的整數(shù)有-個(gè);, 恰被p整除的整數(shù)有-個(gè),于是h=-+2(-)+3(-)+r(-)+

21、=+.性質(zhì) =/r. 例3 求50!的標(biāo)準(zhǔn)分解式中,素?cái)?shù)2,3,5的指數(shù),并確定50!的十進(jìn)制數(shù)的末尾0的個(gè)數(shù). 練習(xí)1:200-300的整數(shù)中,求11的倍數(shù)的整數(shù)的個(gè)數(shù). 練習(xí)2:60!的十進(jìn)制數(shù)的末尾0的個(gè)數(shù).作業(yè)P23:1t.2t,求100!的十進(jìn)制數(shù)的末尾0的個(gè)數(shù).習(xí)題課第二章 不定方程 §1二元一次不定方程1.二元一次不定方程概念例1百雞問(wèn)題:“雞翁一,值錢五,雞母一,值錢3,雞雛三,值錢一.百錢買百雞,問(wèn)雞翁、雞母、雞雛各幾何？”設(shè)百錢買雞翁、雞母、雞雛分別x只、y只、z只.依題意得 x+y+z=100,且5x+3y+z/3=100.整理得 14x+8y=200且x+y+

22、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. 證明 若不定方程ax+by=c有整數(shù)解m,n,則am+bn=c,因?yàn)?a,b)|a,(a,b)|b,所以(a,b)|am+bn,即(a,b)|c.反之,若(a,b)|c,設(shè)c=t(a,b).由第一章§3定理1知,有整數(shù)

23、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,tZ,或x=m+bt,y=n-at,tZ. (2) 證明 易知tZ,由(2)得到的整數(shù)x,y都是方程(1)的解. 設(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|a(x-m).因?yàn)?a,b)=1,所以b|(x-m),設(shè)x-m=bt,tZ,a(x-m)=-

24、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元錢去買這兩種物品，若要求每種物品至少買1件，且盡量不?；蛏偈ｅX，問(wèn)甲乙物品各買多少件？ 作業(yè)P31:1(a),2. §2多元一次不定方程 n元一次不定方程的一般形式為 (1)其中.n2是整數(shù).Th1 不定方程(1)有整數(shù)解充分必要條件是,() |N.例1求9x+24y-5z=1000的一切整數(shù)解.解 因(9,24,-5)=1,所以不定方程有

25、整數(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寫(xiě)成分母兩兩互質(zhì)的三個(gè)既約分?jǐn)?shù)之和.解 因60=3×4×5,設(shè),整理得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

26、. 故原不定方程的通解為x=1-12t-3s,y=-1+12t+4s,z=1+5t,s,tZ.所以，.當(dāng)t=s=0時(shí),x=-y=z=1,此時(shí)有. 作業(yè):1求3x+6y-5z=15的一切整數(shù)解.§3 勾股數(shù)1.不定方程不定方程的一組整數(shù)解(x,y,z)稱為一組勾股數(shù).例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股數(shù). 定理 不定方程， (1)滿足x>0,y>0,z>0,(x,y)=1,2 |x (2)一切正整數(shù)解可由下式表出：x=2ab,y=,z= (3)其中a>b>0,(a,b)=1,a,b一奇一偶. (4) a

27、=2,b=1,x=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 求不定方程的全部整數(shù)解 xy=6, xy-x+y-4=0.解 x=±1且y=±6,或x=±6,且y=±1,或x=±2,且y=±3,或x=±3,且y=±2。原方程可變?yōu)?x+1)(y-1)-3=0,即(x+1)(y-1)=3.所以

28、有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.作業(yè):1.寫(xiě)出不定方程的滿足x>0,y>0,z>0,(x,y)=1,2 |x的2組正整數(shù)解。2.求不定方程xy-x-y-4=0的全部整數(shù)解.第三章 同 余§1同余的概念及其性質(zhì)1.同余及性質(zhì)定義 設(shè)m是正整數(shù),稱m為模.a,bZ,如果a,b被m除所得的余數(shù)相同,則稱a,b對(duì)模m同余,記為ab(modm).如果a,b被m除所得的余數(shù)不同,則稱a,b對(duì)模m不同余,記為ab(m

29、odm).例如 47(mod3),611(mod5),45(mod3),68(mod5).定理1 整數(shù)a,b對(duì)模m同余的充分必要條件是,m|a-b,即a=b+mt,tZ.證明 必要性,若ab(modm).可設(shè)a=msa=r,b=mua=r,s,uZ,則a-b=m(s-u)=mt,T=s-uZ.所以m|a-b,且a=b+mt.充分性,設(shè)a=ms+,b=mu+,a-b=m(s-u)+-.因m|a-b,所以m|-,但|-|<m.從而=,即ab(modm). 同余的性質(zhì)甲:ab(modm).乙:若ab(modm),ba(modm).丙:若ab(modm),bc(modm),則ac(modm).丁

30、、戊:則 由此可得,若則.由此可得定理2.2.同余的應(yīng)用 A.3(9)|a的條件設(shè)a=,.則因(mod3(9),i=1,n,則a(modm),于是3(9)|a是3(9)|. B.7(11,13)|a的條件設(shè)a=,.因(mod7(11,13),則a(modm),于是7(11,13)|a是7(11,13)|. 例1 設(shè)a=5874192,b=435693,=5+8+7+4+1+9+2=36,=4+3+5+6+9+3=30,所以9|a,3|b. 例2若a=637693,=693-637=56, 7|56,1156,1356,所以7|5a,11a6,13a. 作業(yè)：1.p53:2.§2 剩余

31、類及完全剩余系1.模m的剩余類及完全剩余系設(shè)m是正整數(shù),Z是整數(shù)集,令=mt+r|tZ,r=0,1,m-1,則,稱為模m的剩余類.易知,a,b,則ab(modm).稱a為中其它數(shù)的剩余.設(shè),r=0,1,m-1,稱,為模m的完全剩余系.定義 設(shè)m是正整數(shù),0,1,m-1稱為模m的非負(fù)最小完全剩余系.m為偶數(shù)時(shí),稱為模m的絕對(duì)最小完全剩余系；m為奇數(shù)時(shí),稱為模m的絕對(duì)最小完全剩余系.例1 m=6,模6的剩余類為,0,1,2,3,4,5是模6的一個(gè)完全剩余系,1,2,3,4,5,6也是模6的一個(gè)完全剩余系.-3,-2,-1,0,1,2;-2,-1,0,1,2,3都是模6的完全剩余系,稱為模6的絕對(duì)最

32、小完全剩余系.例2 m=5時(shí),0,1,2,3,4;-2，-1,0,1,2分別叫做模5的非負(fù)最小完全剩余系和絕對(duì)最小完全剩余系.2.完全剩余系的判定定理1 m個(gè)整數(shù),為模m的完全剩余系的充分必要條件為，,對(duì)模m兩兩不同余. 定理2 設(shè)m是正整數(shù),(a,m)=1,bZ,是模m的一個(gè)完全剩余系,則, 是模m的一個(gè)完全剩余系.證明 對(duì)ji,m,因?yàn)?且(a,m)=1,于是m,所以m.（modm）,i,j=1,2,m, ji,從而,是模m的一個(gè)完全剩余系.例3 寫(xiě)出模9的一組完全剩余系,它的每一個(gè)數(shù)都是偶數(shù); 寫(xiě)出模9的一組完全剩余系,它的每一個(gè)數(shù)都是奇數(shù).作業(yè)：1.分別寫(xiě)出模7、模8的非負(fù)最小完全剩余

33、系、絕對(duì)最小完全剩余系.3 簡(jiǎn)化剩余系與歐拉函數(shù)1.簡(jiǎn)化剩余系、歐拉函數(shù) 定義若模m的一個(gè)剩余類里的數(shù)與m互質(zhì),則稱這個(gè)剩余類為與模m互質(zhì)的. 對(duì)與模m互質(zhì)的全部剩余類,從每一類里任取一數(shù)組成的集合,叫做模m的簡(jiǎn)化剩余系. m=6時(shí),是全部與模m互質(zhì)的剩余類,1,5是模6的簡(jiǎn)化剩余系.m=8時(shí), ,是模8的簡(jiǎn)化剩余系. 定義設(shè)a是正整數(shù),歐拉函數(shù)=0,1,a-1中與a互質(zhì)的整數(shù)的個(gè)數(shù). 例如=1,=1,=2,=2,=4,=2,=6. 模m的一個(gè)簡(jiǎn)化剩余系中含有個(gè)數(shù)。2.簡(jiǎn)化剩余系的判定 定理1 模m的剩余類與模m互質(zhì)的是aZ,使得(a,m)=1.與模m互質(zhì)的剩余類的個(gè)數(shù)是.模m的每一個(gè)簡(jiǎn)化剩余

34、系,是由與m互質(zhì)的對(duì)模m兩兩不同余的個(gè)整數(shù)組成.定理3設(shè)m是正整數(shù),(a,m)=1,是模m的一個(gè)簡(jiǎn)化剩余系,則,是模m的一個(gè)簡(jiǎn)化剩余系.定理4若,是互質(zhì)的兩個(gè)正整數(shù),分別通過(guò)模的簡(jiǎn)化剩余系,則+通過(guò)模的簡(jiǎn)化剩余系. 推論 若,是互質(zhì)的兩個(gè)正整數(shù),則.定理5 設(shè)正整數(shù)a的標(biāo)準(zhǔn)分解式為a=,則 =證明 在數(shù)列1,2,p-1,p,p+1,p+p-1,2p,p(-1)+1, p(-1)+p-1,p中與互質(zhì)的整數(shù)有(p-1)個(gè)，即. 作業(yè)P60:3. §4歐拉定理 費(fèi)爾瑪定理及其應(yīng)用1.歐拉定理 費(fèi)爾瑪定理 定理1(Euler)設(shè)a,mZ,m>1,(a,m)=1,則.證明取模的一個(gè)簡(jiǎn)化剩

35、余系,由于(,)=1,由§3定理3知,也是模的一個(gè)簡(jiǎn)化剩余系，于是,即,因(m,)=1,i=1,2,所以(m,)=1,從而.證畢。 推論(費(fèi)爾瑪定理)設(shè)P是素?cái)?shù),則,而且aZ,.證明 若p |a,則(modP)，若(,)=1，則，所以. 例1 設(shè)p,q是不同的素?cái)?shù),證明(modpq).證明 因p,q是不同的素?cái)?shù),所以(p,q)=1,由費(fèi)爾瑪定理知,(modp),(modq).由同余的性質(zhì)得,(modpq).例2設(shè)p2,5為素?cái)?shù),整數(shù)a的十進(jìn)制數(shù)由p-1位,而且每一位上的數(shù)字都是9,證明p |a.證明因p2,5為素?cái)?shù),所以(10,p)=1,由費(fèi)爾瑪定理得,a=999=0(modp),即

36、p |a.例3 若變量x取整數(shù)時(shí),多項(xiàng)式P(x)=的值總為整數(shù),則稱P(x)為整值多項(xiàng)式.證明,是整值多項(xiàng)式.證明 2730=2×3×5×7×13,當(dāng)x取整數(shù)值時(shí),由費(fèi)爾瑪定理,(mod13),即13|.(mod7),即7|.(mod5),即5|.(mod3),即3|.(mod2),即2|.因2,3,兩兩互質(zhì),由整除的性質(zhì)知,2×3×5×7×13|，即2730|.故是整值多項(xiàng)式.例4 今天是星期一，問(wèn)從今天起再過(guò)天是星期幾？解 103(mod7),(mod7), (mod7),所以(mod7)。又因10-2(mod

37、6), (mod6),故(mod6)。設(shè)，k為正整數(shù),于是(mod7),這就是說(shuō)，從今天起再過(guò)天是星期五（1+4）。例5求被8除的余數(shù)。作業(yè):P64:1.例32.分?jǐn)?shù)與循環(huán)小數(shù)定義 如果無(wú)限小數(shù)0.（0,1，,9）從任何一位數(shù)后不全為0,且能找到兩個(gè)整數(shù)s0,t0,使得 ,i=1,2,t,k=0,1,2,. (*)則稱它為循環(huán)小數(shù)，并簡(jiǎn)記為0. 對(duì)滿足(*)的最小正整數(shù)t,稱為循環(huán)節(jié)，稱t為循環(huán)節(jié)的長(zhǎng)度.若最小的s=0,那小數(shù)就叫做純循環(huán)小數(shù)，否則叫做混循環(huán)小數(shù)。定理2有理數(shù),0<a<b,(a,b)=1,能表成純循環(huán)小數(shù)的充分必要條件是,(b,10)=1.推論 有理數(shù),0<a

38、<b,(a,b)=1,是純有限小數(shù)的充分必要條件是(b,10)1.證明 必要性：若有理數(shù)能表成純循環(huán)小數(shù)，則由0<<1及定義知=0.=0.+.于是+0.=q+.所以,因(a,b)=1,所以b|,設(shè)=qb,則=1,故(b,10)=1.充分性：如果(b,10)=1,由定理1知有一正整數(shù)t使得(modb),0<t,又有(modb),設(shè),則,.令q=,顯然不全為9,也不全為0.而且,又由得=，反復(fù)利用 即得=0.=.定理3有理數(shù),0<a<b,(a,b)=1,不全為0,=1,則能表成純循環(huán)小數(shù).其中不循環(huán)部分的位數(shù)是,四章 同余方程§1基本的概念及一次同余方

39、程 1.同余方程的概念定義 設(shè)f(x)=,這里,i=0,1,n.m是正整數(shù),則稱 f(x)=0(modm). (1)為同余式,或模m的同余方程.若0(modm),n稱為同余方程(1)的次數(shù).若aZ而且f(a)0(modm),則稱xa(modm)為同余方程(1)的解.例1 f(x)=0(mod5)是模5的2次同余方程,由于f(1)=50(mod5),因此x1(mod5)是同余方程的一個(gè)解.另外x x=，,t=0,±1,±2, (mod5)也是同余方程的一個(gè)解.2一次同余方程一次同余方程的一般形式：axb(modm),a0(modm) (2)例如 2x3(mod5), 4x8(mod7), 3x9(mod11),定理1