初等數(shù)論復習 (1)

1、初等數(shù)論復習,完全數(shù),6 全部因數(shù)(除本身) 1,2,36=1+2+328 全部因數(shù)(除本身) 1, 2,4,7,1428=1+2+4+7+14,一個數(shù)若等于它的全部因數(shù)之和(不包括自身)，就叫做完全數(shù),親和數(shù),親和數(shù)的定義是：對于自然致m和n，若m的全部因數(shù)(不包括自身)之和恰好等于n．而n的全部因數(shù)(不包括自身)之和又恰好等于m，則m和n是一對親和數(shù)．,例如，220的全部因數(shù)之和 1+2+4+5+10+11+20+22

2、+44+55+110=284而248的全部因數(shù)之和1+2+4+71+142＝220，所以220和284是一對親和數(shù)．,費馬數(shù),也叫費馬質(zhì)數(shù).當年費馬發(fā)現(xiàn)F1=2^(2^1)+1=5 F2=2^(2^2)+1=17 F3=2^(2^3)+1=257 F4=2^(2^4)+1=65537F5=2^(2^5)+1=4294967297前4個是質(zhì)數(shù),因為第5個數(shù)實在太大了,費馬認為是質(zhì)數(shù),并提出(費馬沒給出證明),梅森數(shù)馬林

3、·梅森（Marin Mersenne,1588–1648）是17世紀法國著名的數(shù)學家和修道士,形如2p－1的正整數(shù)，其中p是素數(shù)，常記為Mp  。若Mp是素數(shù)，則稱為梅森素數(shù)。p＝2，3，5，7時，Mp都是素數(shù)，但M11＝2047＝23×89不是素數(shù) 。已發(fā)現(xiàn)的最大梅森素數(shù)是p＝24036583的情形，此時 Mp 是一個7235733位數(shù)。是否有無窮多個梅森素數(shù)是數(shù)論中未解決的難題之一。

4、,任何一個大于2的偶數(shù)都是兩個素數(shù)之和。中國的陳景潤證明了"1+2“質(zhì)因數(shù)個數(shù)較少的數(shù)稱為殆質(zhì)數(shù),哥德巴赫猜想,,1.1 奇數(shù)與偶數(shù),整數(shù)中能被2整除的整數(shù)稱為偶數(shù)，　　　　一般表示為 ２k整數(shù)中不能被2整除的整數(shù)稱為奇數(shù)。　　　　　一般表示為 ２k+1偶數(shù)集：｛0, ±2, ± 4, ± 6｝奇數(shù)集： ｛±1, ±3, ± 5｝0 是偶數(shù)而且 0

5、 是任何整數(shù)的倍數(shù),基本性質(zhì)1.1,（1） 偶數(shù)±偶數(shù)=偶數(shù)（2） 奇數(shù)±奇數(shù)=偶數(shù)（3） 偶數(shù)±奇數(shù)=奇數(shù)? 奇數(shù)個奇數(shù)的和是奇數(shù); 偶數(shù)個奇數(shù)的和是偶數(shù)； 任意正整數(shù)個偶數(shù)的和是偶數(shù),基本性質(zhì)1.2,（1） 奇數(shù)×奇數(shù)=奇數(shù)（2） 奇數(shù)×偶數(shù)=偶數(shù)（3） 偶數(shù)×偶數(shù)=偶數(shù)? 任意多個奇數(shù)的積是奇數(shù); 至少有一個乘數(shù)是偶數(shù)的積是偶

6、數(shù),基本性質(zhì)1.3,（1） 如果一個偶數(shù)能被奇數(shù)整除，那么商必是偶數(shù).（2） 兩個連續(xù)整數(shù)的積 n(n+1)是偶數(shù).,1.2.1 帶余除法,(帶余數(shù)除法) 設(shè)a與b是兩個整數(shù)，b ? 0，則存在唯一的兩個整數(shù)q和r，使得 a = bq ? r，0 ? r < |b|。 (1)定義1 稱式(1)中的q是a被b除的商，r是a被b除的余數(shù),,,例 若n是奇數(shù)，則8?n2 ? 1。解 設(shè)n =

7、2k ? 1，則n2 ? 1= (2k ? 1)2 ? 1 = 4k(k ? 1)。在k和k ? 1中有一個是偶數(shù)，所以8?n2 ? 1。,1.2.2 最小公倍數(shù)與最大公約數(shù),定義 整數(shù)a1, a2, ?, ak的公共倍數(shù)稱為a1, a2, ?, ak的公倍數(shù)。a1, a2, ?, ak的正公倍數(shù)中的最小的一個叫做a1, a2, ?, ak的 最小公倍數(shù)，記為[a1, a2, ?, ak]。定義 整數(shù)a1, a2, ?,

8、ak的公共約數(shù)稱為a1, a2, ?, ak的公約數(shù)。不全為零的整數(shù)a1, a2, ?, ak的公約數(shù)中最大的一個叫做a1, a2, ?, ak的 最大公約數(shù)（或最大公因數(shù)），記為(a1, a2, ?, ak)。,定理 下面的等式成立：(ⅰ) [a, 1] = |a|，[a, a] = |a|；(ⅱ) [a, b] = [b, a]；(ⅲ) [a1, a2, ?, ak] = [|a1|, |a2| ?, |ak|

9、]；(ⅳ) 若a?b，則[a, b] = |b|。,輾轉(zhuǎn)相除法,定義1 下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法。設(shè)a和b是整數(shù)，b ? 0，依次做帶余數(shù)除法： a = bq1 ? r1， 0 r1 > r2 > ? ，所以式(1)中只包含有限個等式。,1.2.3 裴蜀恒等式,(a,b)=ua+vb 其中 u,v是兩個整數(shù),rn ? 2 = rn ? 1qn ? rn,(a,b)= rn =r

10、n ? 2 ? rn ? 1qn,rn-1 =rn ? 3 ? rn ? 2qn-1,代入上式得 (a,b)= u1rn ? 2 ? v1rn ? 3,… … …,可得: (a,b)=ua+vb,對于任意的正整數(shù) a1,a2,…,an，存在整數(shù) k1,k2,…,kn, 使得k1a1+k2a2+…+knan=(a1,a2,…,an),當 a,b 互質(zhì)時，就有整數(shù) u,v，滿足,,1=ua-vb 1<u≤b，0&

11、lt;v≤ a,例 用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得125x ? 17y = (125, 17)。解 做輾轉(zhuǎn)相除法：125 = 7?17 ? 6，q1 = 7，r1 = 6， 17 = 2?6 ? 5， q2 = 2，r2 = 5， 6 = 1?5 ? 1， q3 = 1，r3 = 1， 5 = 5?1， q4 = 5。(125, 17) = r3 = 1。,125?3 ? 17?(?2

12、2) = (125, 17) = 1,§1.3 質(zhì)因數(shù)分解定理,正整數(shù)分類1質(zhì)數(shù)(素數(shù))合數(shù),定理1(算術(shù)基本定理) 任何大于1的整數(shù)n可以唯一地表示成n = ， (2)其中p1, p2, ?, pk是素數(shù)，p1 < p2 < ? < pk，?1, ?2, ?, ?k是正整數(shù)。,,定義 使用定理1中的記號，稱

13、 n =是n的標準分解式，其中pi（1 ? i ? k）是素數(shù)，p1 < p2 < ? < pk，? i（1 ? i ? k）是正整數(shù)。,例 寫出51480的標準分解式。 解 我們有 51480 = 2?25740 = 22?12870 = 23?6435 = 23?5?1287 = 23?5?3?429 = 23?5?32?143 = 23?32?5?11?13,例 求使 1989m為

14、平方數(shù)的最小m,P24 練習1.3 3 4,§1.4 質(zhì)數(shù),1.4.1 質(zhì)數(shù)的無限性,基本結(jié)論1.4 質(zhì)數(shù)有無限多個。,例 形如4n – 1的素數(shù)有無限多個。,解 若不然，假設(shè)只有k個形如4n – 1的素數(shù)p1, p2, ?, pk。記N = 4p1p?pk – 1。,N 的質(zhì)因數(shù)一定是奇數(shù),形如 4n+1 或4n – 1,如果全是形如 4n+1 積也是形如 4n+1,所以，N必有形如 4n-1的質(zhì)因數(shù) p

15、,且 p 不同于p1, p2, ?, pk,設(shè): n=2k j (k為非負整數(shù)，j為正奇數(shù))若 j≠1，則2n+1=(22k)j+1j =(22k+1)((22k)j-1-(22k)j-2+…+1j-1)22k+1是2n+1的真因數(shù)所以2n+1是合數(shù),例 若a > 1，a n ? 1是素數(shù)，則a = 2，并且n是素數(shù)。,解 若a > 2，則由an ? 1 = (a ? 1)(an ? 1 ?

16、an ? 2 ? ? ? 1)可知a n ? 1是合數(shù)。所以a = 2。若n是合數(shù)，則n = xy，x > 1，y > 1，于是由2xy ? 1 = (2x ? 1)(2x(y ? 1) ? 2x(y ? 2) ? ? ? 1)以及2x ? 1 > 1可知2n ? 1是合數(shù)，所以2n ? 1是素數(shù)時，n必是素數(shù)。,注：若n是素數(shù)，則稱2n ? 1是Mersenne數(shù),第二章 同余,§2.1 基本性質(zhì)

17、§2.2 同余的應(yīng)用§2.3 費馬小定理§2.4 中國剩余定理,定義: 給定正整數(shù)m，如果整數(shù)a與b之差被m整除，(存在 q 使得 a-b=qm)則稱a與b對于模m同余，或稱a與b同余，模m，記為a ? b (mod m)，此時也稱b是a對模m的同余。 如果整數(shù)a與b之差不能被m整除，則稱a與b對于模m不同余，或稱a與b不同余，模m，記為a ? b (mod m)。如 62 ?

18、48 (mod 7) 12 ?60 (mod 8),,下面的三個敘述是等價的：(ⅰ) a ? b (mod m)；(ⅱ) 存在整數(shù)q，使得a = b ? qm；(ⅲ) 存在整數(shù)q1，q2，使得a = q1m ? r，b = q2m ? r，0 ? r < m。,§2.1 基本性質(zhì),2.1.1 同余的基本性質(zhì)性質(zhì)2.1(1) 反身性 a ?a (mod m)(2) 對稱性

19、 若 a ?b (mod m)，則 b ?a(mod m)(3) 傳遞性 若 a ?b (mod m)， b ?c (mod m)，則 a ?b (mod m)(4) 若a ?b (mod m)， c ?d (mod m)，則 a±c ?b±d (mod m),(5) 若 a ?b (mod m), c ?d (mod m)，則 ac ?bd (mod m)(6) 若 a ?

20、b (mod m), 且 n∈N，則 an ?bn (mod m)(7) 若 ac ?bc (mod m) ，且c≠0，則 a ?b (mod m/(c,m)) (8) 若 a ?b (mod m), m=qn ，則 a ?b (mod n)(9)若 a ?b (mod mi),i=1,2,…,n ，則 a ?b (

21、mod [m1,m2,…,mn]),,2.1.2 完全剩余系,定義 給定正整數(shù)m，對于每個整數(shù)i，0 ? i ? m ? 1，稱集合Ri(m) = { n；n ? i (mod m)，n?Z }。是模m的一個剩余類。也可表示為 Mi={i+km|k ?Z}，i=0,1,2,…,m-1,m＝2時，Z可以分為2類，一類是奇數(shù)，一類是偶數(shù)。m=3時，Z可以分為3類，3k-1,3k,3k+1m=4時，Z可以分為4類，4k,

22、4k+1,4k+2,4k+3,定義 設(shè)m是正整數(shù)，從模m的每一個剩余類中任取一個數(shù)xi（0 ? i ? m ? 1），稱集合{x0, x1, ?,xm ? 1}是模m的一個完全剩余系（或簡稱為完系）。由于xi的選取是任意的，所以模m的完全剩余系有無窮多個，通常稱(ⅰ) {0, 1, 2, ?, m ? 1}是模m的最小非負完全剩余系；(ⅱ),,,是模m的絕對最小完全剩余系。,例如，集合{0, 6, 7, 13, 24}是模5

23、的一個完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非負完全剩余系。,定理1 整數(shù)集合A是模m的完全剩余系的充要條件是(ⅰ) A中含有m個整數(shù)；(ⅱ) A中任何兩個整數(shù)對模m不同余。,例如，模 5的五個剩余類是R0(5) = { ? , ?10, ?5, 0 , 5, 10, ? }，R1(5) = { ? , ?9 , ?4 , 1 , 6 , 11, ? }，R2(5) = { ? , ?8 , ?3

24、, 2 , 7 , 12, ? }，R3(5) = { ? , ?7 , ?2 , 3 , 8 , 13, ? }，R4(5) = { ? , ?6 , ?1 , 4 , 9 , 14, ? }。,§2.2 同余的應(yīng)用,對于模 2，下列基本同余式成立： -a≡a （mod 2） ｜a｜≡a （mod 2）,定理 設(shè)ai，bi（0 ? i ? n）以及x，y都是整數(shù)，并且x ? y (

25、mod m)，ai ? bi (mod m)，0 ? i ? n，則 (mod m)。,,(4) 若a ?b (mod m)， c ?d (mod m)，則 a±c ?b±d (mod m)(5) 若 a ?b (mod m), c ?d (mod m)，則 ac ?bd (mod m)(

26、6) 若 a ?b (mod m), 且 n∈N，則 an ?bn (mod m),例 求(25733 ? 46)26被50除的余數(shù)。,解 利用定理有(25733 ? 46)26 ? (733 ? 4)26 = [7?(72)16 ? 4]26? [7?( ?1)16 ? 4]26 = (7 ? 4)26? 326 = 3?(35)5 ? 3?(?7)5 = ?3?7?(72)2? ?21 ? 29 (m

27、od 50)，,因為82 ? ?1(mod 13)，所以81234 = (82)617 ? (?1)617 ? ?1 ? 12 (mod 13)，即81234被13除的余數(shù)是12。,求81234被13除的余數(shù),解 我們有,71 ? ?3，72 ? ?1，74 ?1 (mod 10)，,因此，若,77 ? r (mod 4)，,則,現(xiàn)在 77 ? (?1)7 ? ?1 ? 3 (mod 4)，,所以,解 因為792 = 8?9?11

28、，故792?n ? 8?n，9?n及11?n。我們有 8?n ? 8? ? z = 6， 9?n ? 9?1 ? 3 ? x ? y ? 4 ? 5 ? z = 19 ? x ? y ? 9?x ? y ? 1， (1)11?n ? 11?z ? 5 ? 4 ? y ? x ? 3 ? 1 = 3 ? y ? x

29、? 11?3 ? y ? x。 (2)由于0 ? x, y ? 9，所以由式(1)與式(2)分別得出,,x ? y ? 1 = 9或18，3 ? y ? x = 0或11。這樣得到四個方程組： 其中a取值9或18，b取值0或11。在0 ? x, y ? 9的條件下解這四個方程組，得到x = 8，y = 0，z = 6。,,,P41 練習2.2 5,§2.3 費馬小定理,P

30、47 練習2.3 6.證明： 若 a和b均不被質(zhì)數(shù)n+1整除，則 被n+1整除.,證明,,,P47 練習2.3 1, 2,2.4 中國剩余定理,同余方程,定義1 設(shè)f(x) = anxn ? ? ? a1x ? a0是整系數(shù)多項式，稱f(x) ? 0 (mod m) (1)是關(guān)于未知數(shù)x的模m的同余方程，簡稱為模m的同余方程。若an ? 0 (mod m)

31、，則稱為n次同余方程。,,定義2 設(shè)x0是整數(shù)，當x = x0時式(1)成立，則稱x0是同余方程(1)的解。凡對于模m同余的解，被視為同一個解。同余方程(1)的解數(shù)是指它的關(guān)于模m互不同余的所有解的個數(shù)，也即在模m的一個完全剩余系中的解的個數(shù)。由定義2，同余方程(1)的解數(shù)不超過m,定理2.3 設(shè)a，b是整數(shù)，a ? 0 (mod m)。則同余方程 ax ? b (mod m) 有解的充要條件是(a, m)?b。若有解，則

32、恰有d = (a, m)個解。,,一次同余方程的解法,同余變形法,一次同余方程的解法,同余變形法,一次同余方程的解法,同余變形法,,P53 練習2.4 1,2,3,第三章 數(shù)論函數(shù),§3.1 [x]§3.2 τ(n)與σ(n)§3.3 φ(n),§3.1 [x],取整函數(shù)設(shè)x為實數(shù)，[x]表示不超過x的最大整數(shù)，通常稱[x]為高斯函數(shù)或取整函數(shù)[π]=3基本性質(zhì) [x] ≤

33、x＜ [x] +1,性質(zhì)3.1 [x]是單調(diào)增加的。性質(zhì)3.2 在m∈Z時，[x+m]=m+[x]性質(zhì)3.3 對于所有實數(shù)x，y，有[x]+[y] ≤[x+y]證明：令{x}=x-[x]，則{x} ≥0， 同理{y} ≥0。于是[x+y]=[[x] + {x}+ [y] + {y}]= [x]+ [y] +[{x}+ {y} ] ≥ [x]+ [y],性質(zhì)3.4證明：x為整數(shù)時顯然成立

34、 x不是整數(shù)時，{x}=x-[x]>0, 有x= [x]+ {x} [-x]=[-[x]-{x}]= -[x]+[-{x}]= -[x] -1,n!中質(zhì)數(shù)p的次數(shù),記n！中質(zhì)數(shù)p出現(xiàn)的次數(shù)為vp(n!)vp(n!)=,§3.2 τ(n)與σ(n),τ(n)表示正整數(shù)n的因數(shù)個數(shù),則n的因數(shù)為：,σ(n),σ(n)表示正整數(shù)n的所有因數(shù)的和,積性函數(shù),定義：如果f(n)為數(shù)論

35、函數(shù)，并且對于任何一對互質(zhì)的自然數(shù)a，b，有 f(ab)=f(a)f(b),τ(n)與σ(n)都是積性函數(shù),τ(ab)= τ(a) τ(b),σ(ab)= σ(a) σ(b),完全數(shù),如果自然數(shù)n的因數(shù)的和是n的兩倍，即σ(n)=2n，那么稱n為完全數(shù)。6=1+2+328=1+2+4+7+14,φ(n),歐拉函數(shù)φ(n)設(shè)n為正整數(shù)， φ(n)表示不大于n并且與n互質(zhì)的自然數(shù)個數(shù)，稱φ(n)為歐拉函數(shù)φ(1)=1，

36、 φ(2)=1， φ(10)=4,φ(n),性質(zhì)3.5 對質(zhì)數(shù)p， φ(p)=p-1.性質(zhì)3.6 對質(zhì)數(shù)p及正整數(shù)k， φ(pk)=pk-1(p-1).性質(zhì)3.7 φ(n)是積性函數(shù)，也就是(a,b)=1,則φ(a b)= φ(a) φ(b),φ(n),性質(zhì)3.8 設(shè)則,第4章 不定方程,§4.1 一次不定方程§4.2 費馬方程,§4.1 一次不定方程,設(shè)a1, a2,

37、?, an是非零整數(shù)，b是整數(shù)，稱關(guān)于未知數(shù)x1, x2, ?, xn的方程a1x1 ? a2x2 ? ? ? anxn = b (1)是n元一次不定方程。若存在整數(shù)x10, x20, ?, xn0滿足方程(1)，則稱(x10, x20, ?, xn0)是方程(1)的解，或說x1 = x10，x2 = x20，?，xn = xn0是方程(1)的解。,定理1 方程(1)有解的充要條件是(a1

38、, a2, ?, an)?b。 (2),定理1’ 設(shè)a，b，c是整數(shù)，二元一次不定方程ax ? by = c (3)有解的充要條件是(a,b)|c.,定理2 設(shè)a，b，c是整數(shù)，方程ax ? by = c (3)若有解(x0, y0)，則它的一切解具有,,t?Z (4)

39、,的形式，其中,,解二元一次不定方程的一般步驟,（1）判斷方程是否有解（2）如果方程有解，那么先求方程,的一組特解，從而得到方程 ax+by=c 的一組特解。,（3）寫出方程的通解,定理1和定理2說明了解方程(3)的步驟：(ⅰ) 判斷方程是否有解，即(a, b)?c是否成立；(ⅱ) 利用輾轉(zhuǎn)相除法求出x0，y0，使得ax0 ? by0 = (a, b) ；(ⅲ) 寫出方程(3)的解,,,,無解,例 求不定方程3x ?

40、6y = 15的解。,解 (3, 6) = 3?15，所以方程有解。由輾轉(zhuǎn)相除法（或直接觀察），可知x = ?1，y = 1是 3x ? 6y = 3的解，所以x0 = ?5，y0 = 5是原方程的一個解。由定理2，所求方程的解是,,例 求不定方程3x ? 6y = 15的解。,解 (3, 6) = 3?15，所以方程有解。,,比較,4.2 費馬方程,商高不定方程,容易看出，(x, y, z) = (0, 0

41、, 0)，(0, ?a, ?a)以及(?a, 0, ?a)都是方程(1)的解。若(x, y, z)是方程(1)的解，則對于任何整數(shù)k，(kx, ky, kz)也是方程(1)的解。此外，若(x, y) = k，則k?z，(x, y, z) = k。因此，我們只需研究方程(1)的滿足下述條件的解：x > 0，y > 0，z >0，(x, y) = 1。 (2),定理1 若(x, y, z)是方程(

42、1)的滿足條件(2)的解，則下面的結(jié)論成立：(ⅰ) x與y有不同的奇偶性；(ⅱ) x與y中有且僅有一個數(shù)被3整除；(ⅲ) x，y，z中有且僅有一個數(shù)被5整除。,定理2 方程(1)的滿足式(2)和2?x的一切正整數(shù)解具有下面的形式： x = 2ab，y = a2 ? b2，z = a2 ? b2， (8)其中a > b > 0，(a, b) = 1，a與b有不同的奇偶性。,x =

43、2ab，y = a2 ? b2，z = a2 ? b2， (8)其中a > b > 0，(a, b) = 1，a與b有不同的奇偶性,,P85 習題4.3 1 ,2,第5章 連分數(shù),5.1 連分數(shù)及其漸近分數(shù)5.2 有理連分數(shù)與有理數(shù)5.3 無限連分數(shù)與無理數(shù),5.1 連分數(shù)及其漸近分數(shù),設(shè) v>1并且分母小于 v 的有理數(shù) a 都能表成連分數(shù),,,? ?,得到,= ? 2, 1,