初等數(shù)論復(fù)習(xí)

1、 作業(yè)要求：作業(yè)要求： 作業(yè)要及時(shí)完成，及時(shí)提交。作業(yè)要及時(shí)完成，及時(shí)提交。 作業(yè)（網(wǎng)絡(luò)作業(yè)、期中作業(yè)）要計(jì)入總分。作業(yè)（網(wǎng)絡(luò)作業(yè)、期中作業(yè)）要計(jì)入總分。 學(xué)習(xí)過程中的問題，可通過網(wǎng)上答疑系統(tǒng)提出。學(xué)習(xí)過程中的問題，可通過網(wǎng)上答疑系統(tǒng)提出。 考試說明：考試說明： 試題類型：填空題試題類型：填空題(40%)(40%)、計(jì)算題和證明題、計(jì)算題和證明題(60%)(60%)。 考試范圍考試范圍1-41-4章：其中第章：其中第1 1、2 2章各占章各占30%30%，第，第3 3、4 4章各占章各占2020（以光盤為準(zhǔn)）。（以光盤為準(zhǔn)）。 試題難度不超出習(xí)題、例題、模擬試卷。試題難度不超出習(xí)題、例題、模擬

2、試卷。第一章第一章 整數(shù)的整除性論整數(shù)的整除性論第二章第二章 同余理論同余理論第三章第三章 不定方程不定方程第四章第四章 同余式同余式第一章第一章 整數(shù)的整除性理論整數(shù)的整除性理論 本章主要從整數(shù)的整除性概念出發(fā)，本章主要從整數(shù)的整除性概念出發(fā)，介紹帶余除法、輾轉(zhuǎn)相除。然后以其為工介紹帶余除法、輾轉(zhuǎn)相除。然后以其為工具建立最大公因數(shù)和最小公倍數(shù)理論，最具建立最大公因數(shù)和最小公倍數(shù)理論，最后介紹算術(shù)基本定理，高斯函數(shù)等。后介紹算術(shù)基本定理，高斯函數(shù)等。 a|ab若b|a ，a0 則 若 b|a 且 a|b， 則 |a| = |b| 若 c | b , b | a , 則 c | a b|a 的充

3、要條件是 cb | ca 若 c|a, c|b, 則對(duì)于,m nc manb有niii=1(1,2, )k aikinm有 一般地若 m|ai（i=1 , 2 , ，n）,則一、一、 整除的概念與性質(zhì)整除的概念與性質(zhì)定理：,0a bb且，則, q r使得a=bq+r（0r0，c|a,c|b，則，則a,ba b,=c cc定理定理4 4：設(shè)：設(shè)a,ba,b是不全為零的整數(shù)。是不全為零的整數(shù)。(i)(i)若若 m0m0，則，則 (am,bm) = m(a,b)(am,bm) = m(a,b)(iii)(iii)若若 (a,b)= 1(a,b)= 1，t t是任意整數(shù)，是任意整數(shù)， 則則 (at,b

4、)=(t,b)(at,b)=(t,b)定理定理4 4：設(shè)：設(shè)a,ba,b是任給的兩個(gè)正整數(shù)，則是任給的兩個(gè)正整數(shù)，則(i) a , b(i) a , b的所有公倍數(shù)都是的所有公倍數(shù)都是a,ba,b的倍數(shù)。的倍數(shù)。(ii)a,b(a,b)=ab(ii)a,b(a,b)=ab推論：若推論：若(a,b)=1,(a,b)=1,則則a,b=aba,b=abm mm,=aba,b定理定理5 5：設(shè)正整數(shù)：設(shè)正整數(shù)m m是是a, ba, b的一個(gè)公倍數(shù)，則的一個(gè)公倍數(shù)，則證明：設(shè)證明：設(shè) (a-b , a+b)= d 則則 d | a-b, d | a+b d | a-b+a+b , d | a-b-(a+

5、b) 即即 d | 2a , d | 2b d | (2a , 2b) d | 2(a , b) (a , b) = 1 d | 2 d=1 或或 d=2 例：如果例：如果(a , b)=1，則，則 (a-b ,a+b) = 1 或或 2三、整數(shù)的唯一分解定理三、整數(shù)的唯一分解定理 ( (算術(shù)基本定理算術(shù)基本定理) ) 其中其中定理：對(duì)于任一大于定理：對(duì)于任一大于1 1的整數(shù)的整數(shù)a a，除因數(shù)的順序，除因數(shù)的順序 外都能唯一分解成：外都能唯一分解成：12k12ka=p pp1(, ,1,2, , )iijippij i jkp為 素 數(shù)且且(1)d(1)d是是a a的正因數(shù)的充分必要條件是的

6、正因數(shù)的充分必要條件是1k1kd=pp(0 i i i i i = 1, 2, , k)(2) a a 的正因數(shù)的個(gè)數(shù)為的正因數(shù)的個(gè)數(shù)為T(a)=( 1 1+1)( 2 2+1)( k k+1)ki=1 ( i i +1)12k+1+1+112k12kp-1 p-1p-1S(a)=p -1p -1p -1(3) a a的一切正因數(shù)之和的一切正因數(shù)之和T(a)T(a)為為a a的一切正因數(shù)的個(gè)數(shù)。的一切正因數(shù)的個(gè)數(shù)。 1T a2p(a)=a(4) a a 的一切正因數(shù)之積為的一切正因數(shù)之積為定理：若定理：若x x是正實(shí)數(shù)，是正實(shí)數(shù)，nn+ +，則不大于，則不大于x x，且為，且為xnn n的倍數(shù)

7、的自然數(shù)的個(gè)數(shù)是的倍數(shù)的自然數(shù)的個(gè)數(shù)是四、高斯函數(shù)四、高斯函數(shù) xx r=1np定理：在定理：在n!n!的標(biāo)準(zhǔn)分解式中素因數(shù)的標(biāo)準(zhǔn)分解式中素因數(shù)p p的指數(shù)是的指數(shù)是2rnnn+ppp p(n!)即即 200! 的標(biāo)準(zhǔn)式中素因數(shù)的標(biāo)準(zhǔn)式中素因數(shù)7的指數(shù)為的指數(shù)為32。例：求例：求200！標(biāo)準(zhǔn)分解式中素因數(shù)！標(biāo)準(zhǔn)分解式中素因數(shù)7的指數(shù)。的指數(shù)。r23200200200200=+7777 r=1解：解：7(200!)= 28 + 4 + 0 = 32第二章第二章 同余理論同余理論本章主要介紹同余的概念及其基本性質(zhì)，本章主要介紹同余的概念及其基本性質(zhì)，完全剩余系和互素剩余系，以及著名的歐拉完全剩余系

8、和互素剩余系，以及著名的歐拉定理、費(fèi)馬定理和威爾遜定理。定理、費(fèi)馬定理和威爾遜定理。一一、同余概念和基本性質(zhì)同余概念和基本性質(zhì)定理定理1 1：整數(shù)：整數(shù)a,ba,b關(guān)于模關(guān)于模m m同余的充要條件是同余的充要條件是m|a-bm|a-b定理定理2 2：若：若 a a1 1bb1 1(modm)(modm)，a a2 2bb2 2(modm)(modm) 則則 (1) a(1) a1 1+a+a2 2bb1 1+b+b2 2(modm)(modm) (2) a (2) a1 1-a-a2 2bb1 1-b-b2 2(modm)(modm) (3) a (3) a1 1a a2 2bb1 1b b2

9、 2(modm)(modm)推論：若推論：若a ak kbbk k(modm) k=1,2,(modm) k=1,2,n,n11modnnkkkkabm則則 (1)11modnnkkkkabm(2)推論：若推論：若ab(modm)ab(modm)，則，則a an nbbn n(modm) n(modm) n+ +定理：若定理：若acbc(modm)acbc(modm)且且(c(c，m)=1,m)=1, 則則ab(modm)ab(modm)定理定理: :若若m m1 100，m m1 1|m|m且且ab(modm)ab(modm)則則ab(modmab(modm1 1) )定理：若定理：若c0c

10、0，則，則ab(modm)ab(modm)acbc(modmc)acbc(modmc)定理：若定理：若ab(modmab(modmi i) (i=1) (i=1，2 2，, n), n)， 則則ab(modmab(modm1 1，,m,mn n)定理定理: : 若若acbc(modm)acbc(modm)且且(c(c，m)=dm)=d，md則則a a b(mod)解：解：47-2(mod7)47-2(mod7) 47 475050(-2)(-2)5050(mod7) 2(mod7) 25050(mod7) (mod7) 2 23 316+216+2(mod7)(mod7) (2 (23 3)

11、)16162 22 2(mod7) 8(mod7) 816162 22 2(mod7)(mod7) 1 12 22 2(mod7) 4(mod7)(mod7) 4(mod7) 7 7除除47475050的余數(shù)為的余數(shù)為4 4。例：求例：求7 7除除47475050的余數(shù)。的余數(shù)。定理：定理：k k個(gè)整數(shù)個(gè)整數(shù)a a1 1，a a2 2，a ak k形成模形成模m m的完全剩的完全剩 余系的充要條件是：余系的充要條件是： (1)k=m (2)ai aj(modm) ( i j )定理定理：若：若(a，m)=1,b，則當(dāng)則當(dāng)x x通過模通過模m m的完的完 全剩余系時(shí)，則全剩余系時(shí)，則ax+bax

12、+b也通過模也通過模m m的完全剩余系。的完全剩余系。二二、 完全剩余類和完全剩余系完全剩余類和完全剩余系解：解：0 0，2 2，2 22 2=4=4，2 23 3=8=8，2 24 45(mod11)5(mod11) 2 25 5225(mod11)10(mod11) 5(mod11)10(mod11) 2 26 610102(mod11)9(mod11)2(mod11)9(mod11) 2 27 77(mod11) 27(mod11) 28 83(mod11)3(mod11) 2 29 96(mod11)6(mod11) 2 21010662(mod11) 1(mod11)2(mod11)

13、 1(mod11) 是是 0 0，1 1，2 2，, 10 , 10 的一個(gè)排列。的一個(gè)排列。 0,20,21 1，2 22 2，2 23 3，,2,210 10 能構(gòu)成模能構(gòu)成模1111的的 一組完全剩余系。一組完全剩余系。 例：?jiǎn)柪簡(jiǎn)?,20,2，2 22 2，2 21010是否構(gòu)成模是否構(gòu)成模1111的完全剩余系？的完全剩余系？三、互素剩余類和互素剩余系。三、互素剩余類和互素剩余系。 定理：定理：k k個(gè)整數(shù)個(gè)整數(shù)a a1 1，a a2 2，a ak k構(gòu)成模構(gòu)成模m m的互素的互素 剩余系的充要條件是剩余系的充要條件是 (1) k=(m) (2) ai aj (modm)(i j)

14、(3) (ai, m)=1 (i=1，2，,( m)定理：若定理：若 (a,m)=1(a,m)=1，x x通過模通過模m m的互素剩余系，的互素剩余系，則則axax也通過模也通過模m m的互素剩余系。的互素剩余系。四、四、 歐拉定理、費(fèi)馬定理和威爾遜定理歐拉定理、費(fèi)馬定理和威爾遜定理 定理定理:(:(歐拉定理歐拉定理) )若若 (a,m)=1(a,m)=1，則，則a a(m) (m) 1(modm)1(modm)推論推論:(:(費(fèi)馬定理費(fèi)馬定理) )若若p p為素?cái)?shù)為素?cái)?shù),(a,(a，p)=1,p)=1, 則則a ap-1p-11(modp)1(modp)推論：若推論：若p p為素?cái)?shù)為素?cái)?shù)，a

15、 ， 則則 a ap p a(modp) 定理：定理：( (威爾遜定理威爾遜定理) )整數(shù)整數(shù)p p是素?cái)?shù)的充要條件是素?cái)?shù)的充要條件 是是(p-1)! -1(modp)(p-1)! -1(modp)例：假定例：假定a是任意整數(shù)，求是任意整數(shù)，求證證211(mod3)aa或或210(mod3)aa分析：對(duì)于任意的任意整數(shù)分析：對(duì)于任意的任意整數(shù)a，用模，用模3分類。分類。( )()1(mod)nmmnmn,m n(, )1m n 為正整數(shù)，為正整數(shù)，例：設(shè)例：設(shè)證明證明( n )( m )mn(mod n) 1(m,n), 1( n )m(mod n) 1證明證明：( m )n(mod m )

16、1同理同理1( n )( m )mn(mod m )( n )( m )mn(mod nm ) 1第三章第三章 不定方程不定方程 不定方程是指未知數(shù)的個(gè)數(shù)多于方程的個(gè)數(shù)，而且未知量又受某種限制(如正整數(shù)或整數(shù)解)的方程或方程組。 這一章主要討論一次不定方程整數(shù)解存在的條件，解的結(jié)構(gòu)及解法，還討論特殊的二次不定方程的解結(jié)構(gòu)及解法。一、二元一次不定方程二元一次不定方程 定理：不定方程定理：不定方程ax+by=cax+by=c有整數(shù)解的充要條件是有整數(shù)解的充要條件是 d|cd|c，其中，其中 d=(a,b)d=(a,b)，并且當(dāng)，并且當(dāng)x=xx=x0 0 , y=y, y=y0 0是它是它的一個(gè)解時(shí)

17、，則它的一切解可以表成的一個(gè)解時(shí)，則它的一切解可以表成00bx=x -tday=y +td(t=0，1，2，)二、多元一次不定方程二、多元一次不定方程 定理：定理：n n元一次不定方程元一次不定方程a a1 1x x1 1+ + +a +an nx xn n=b =b 有整數(shù)解的充要條件是有整數(shù)解的充要條件是 (a(a1 1，a a2 2，, a, an n) | b) | b然后消去然后消去t t2 2，t t3 3，t tn-1n-1即即 可可。3312,(,),(,)nnna addaddad122設(shè)（ , ）=na aaad12n-1n則（ , , ）=1 122nnnd ba xa

18、xa xb當(dāng)時(shí)，則可轉(zhuǎn)化為求解可轉(zhuǎn)化為求解: :1 1222 22 2333 322111111nnnnnnnnnna xa xd td ta xd tdtaxdtdta xb三、勾股數(shù)三、勾股數(shù)定理定理1 1：不定方程：不定方程 uv=wuv=w2 2，(u,v)=1 (u,v)=1 的一切正整數(shù)的一切正整數(shù) 解可以表成解可以表成 u=au=a2 2，v=bv=b2 2，w=abw=ab， 其中其中 a0a0，b0b0，(a,b)=1(a,b)=1定理定理2 2：不定方程：不定方程x x2 2+y+y2 2=z=z2 2滿足滿足x0 x0，y0y0，z0z0， (x,y)=1(x,y)=1，

19、2|x2|x的一切整數(shù)解可表為的一切整數(shù)解可表為 x=2abx=2ab，y=ay=a2 2-b-b2 2，z=az=a2 2+b+b2 2 其中其中ab0ab0，(a,b)=1(a,b)=1，a,ba,b一奇一偶。一奇一偶。定理定理3 3：不定方程：不定方程x x2 2+2y+2y2 2=z=z2 2滿足滿足(x,y)=1(x,y)=1的一切正的一切正 整數(shù)解可以表為整數(shù)解可以表為x=|ax=|a2 2-2b-2b2 2| |， y=2aby=2ab，z=az=a2 2+2b+2b2 2， 其中其中a0a0，b0b0，2 a，(a,b)=1第四章第四章 同余式同余式 本章主要研究一次同余式，一

20、次同余式組本章主要研究一次同余式，一次同余式組解存在的條件，解的數(shù)量及其求解的方法，最解存在的條件，解的數(shù)量及其求解的方法，最后討論高次同余式解存在的條件，解的數(shù)量及后討論高次同余式解存在的條件，解的數(shù)量及其解法。其解法。一、一元一次同余式一、一元一次同余式 定理：一元一次同余式定理：一元一次同余式(mod)axbm 有解的有解的充要條件是充要條件是( ,)a m b且有解時(shí)，且有解時(shí)，它的解的數(shù)目是它的解的數(shù)目是( ,)da m 若若(mod)axbm 有解，有解，111,( ,)( ,)( ,)abmabma ma ma m則則 化為化為111(mod)a xbm 求解求解. . 其中其中

21、從而求出同余式的解從而求出同余式的解解不定方程解不定方程111a xm yb例例1：解同余式：解同余式58x87(mod47)解：解： (47x+11x)(47+40)(mod47) 原余分式可化為原余分式可化為11x40(mod47) (11，47)=1 原同余式有解且僅有一解原同余式有解且僅有一解 解不定方程解不定方程 11x+47y=40 y0=6 ,x0=25是它的一個(gè)解是它的一個(gè)解 x25(mod47)是原同余式的解是原同余式的解解：解： (33(33，141)=3 141)=3 且且 3|1203|120 原同余式有且僅有三個(gè)解原同余式有且僅有三個(gè)解 原同余式化為原同余式化為 11

22、x11x40(mod47)40(mod47)求解。求解。 由由 例例1 1知，知，x x25(mod47)25(mod47) 是是 11x11x40(mod47)40(mod47)的一個(gè)解的一個(gè)解 例例2 2：解同余式：解同余式 33x33x120 (mod141)120 (mod141) 33x 33x120(mod141)120(mod141)的一切解為的一切解為 x x25(mod141)25(mod141)14125(mod141)72(mod141)3x 141 225(mod141)119(mod141)3x,即即33x33x120(mod141)120(mod141)的一切解為的一切解為 x x2525，7272，119 (mod141)119 (mod141) 二、二、 一元一次同余式組一元一次同余式組 11 122 2modnn nxM MbM M bMM bM 1 mod1,2,iiiM Mmin 其中其中 有且僅有解有且僅有解 1122modmodmodnnxbmxbmxbm