離散數(shù)學(xué)1112初等數(shù)論

1、課件1第第1111章章 初等數(shù)論初等數(shù)論 課件2第第1111章章 初等數(shù)論初等數(shù)論 11.1 素數(shù)素數(shù) 11.2 最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù) 11.3 同余同余 11.4 一次同余方程與中國剩余定理一次同余方程與中國剩余定理 11.5 歐拉定理和費馬小定理歐拉定理和費馬小定理 課件311.1 素數(shù)素數(shù) 整除、倍數(shù)和因子整除、倍數(shù)和因子 帶余除法帶余除法 素數(shù)與合數(shù)素數(shù)與合數(shù) 算術(shù)基本定理算術(shù)基本定理 篩法篩法課件4整除、倍數(shù)和因子整除、倍數(shù)和因子今后只考慮正整數(shù)的正因子今后只考慮正整數(shù)的正因子.平凡因子平凡因子 : 1和自身和自身真因子真因子 : 除除1和自身之外的因子和自身

2、之外的因子例如例如, 2, 3 是是 6 的真因子的真因子設(shè)設(shè)a, b是兩個整數(shù)，且是兩個整數(shù)，且b0. 如果存在整數(shù)如果存在整數(shù)c 使使 a=bc，則則稱稱a 被被b 整除整除，或，或 b 整除整除a，記作記作 b|a. 此時此時, 又稱又稱 a 是是b 的的倍數(shù)倍數(shù)，b是是a 的的因子因子. 把把 b 不整除不整除 a 記作記作 b a.例如例如, 6有有8個因子個因子1, 2, 3和和6.課件5整除的性質(zhì)整除的性質(zhì)性質(zhì)性質(zhì)11.1.1 若若a |b且且a |c, 則則 x, y, 有有a | xb+yc.性質(zhì)性質(zhì)11.1.2 若若a |b且且b |c, 則則a |c.性質(zhì)性質(zhì)11.1.3

3、 設(shè)設(shè) m0, 則則 a |b 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ma | mb.性質(zhì)性質(zhì)11.1.4 若若a | b且且b | a, 則則a=b.性質(zhì)性質(zhì)11.1.5 若若a | b且且b0, 則則|a|b|. 帶余除法帶余除法: a=qb+r, 0r 1是合數(shù)當(dāng)且僅當(dāng)是合數(shù)當(dāng)且僅當(dāng)a=bc, 其中其中1ba, 1c1, p是素數(shù)且是素數(shù)且d | p, 則則d=p.性質(zhì)性質(zhì)11.1.9 設(shè)設(shè)p是素數(shù)且是素數(shù)且p | ab, 則必有則必有p | a 或者或者 p | b. 設(shè)設(shè)p是素數(shù)且是素數(shù)且p | a1a2ak, 則必存在則必存在1ik, 使得使得p| ai.注意注意:當(dāng)當(dāng)d不是素數(shù)時不是素數(shù)時,d |

4、ab不一定能推出不一定能推出d | a或或d | b. 素數(shù)素數(shù)(質(zhì)數(shù)質(zhì)數(shù)):大于大于1且只能被且只能被1和自身整除的正整數(shù)和自身整除的正整數(shù)合數(shù)合數(shù): 大于大于1且不是素數(shù)且不是素數(shù)例如例如, 2,3,5,7,11是素數(shù)是素數(shù), 4,6,8,9是合數(shù)是合數(shù). . 課件7算術(shù)基本定理算術(shù)基本定理定理定理11.1(算術(shù)基本定理算術(shù)基本定理) 設(shè)設(shè)a1, 則則 a= , 其中其中 p1,p2,pk是不相同的素數(shù)是不相同的素數(shù), r1,r2,rk是正整數(shù)是正整數(shù), 并且在不并且在不計順序的情況下計順序的情況下, 該表示是惟一的該表示是惟一的. 該表達式稱作整數(shù)該表達式稱作整數(shù)a的的素因子分解素因子分

5、解. 例如例如 30=235, 117=3213, 1024=210 推論推論 設(shè)設(shè)a= , 其中其中p1,p2,pk是不相同的素數(shù)是不相同的素數(shù), r1,r2,rk是正整數(shù)是正整數(shù), 則正整數(shù)則正整數(shù)d為為a的因子的充分必要條件的因子的充分必要條件是是d= , 其中其中0siri, i=1,2,k.krkrrppp2121krkrrppp2121kskssppp2121課件8例題例題例例1 21560有多少個正因子有多少個正因子?解解 21560=2357211由推論由推論, 21560的正因子的個數(shù)為的正因子的個數(shù)為4232=48.例例2 10!的二進制表示中從最低位數(shù)起有多少個連續(xù)的的二

6、進制表示中從最低位數(shù)起有多少個連續(xù)的0?解解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得得 10!=2834527,故故10!的二進制表示中從最低位數(shù)起有的二進制表示中從最低位數(shù)起有8 8個連續(xù)的個連續(xù)的0.課件9素數(shù)的分布素數(shù)的分布梅森數(shù)梅森數(shù)(marin mersenne): 2p 1, 其中其中p為素數(shù)為素數(shù) 當(dāng)當(dāng)n是合數(shù)時是合數(shù)時, 2n 1一定是合數(shù)一定是合數(shù), 2ab 1=(2a 1)(2a(b 1)+2a(b 2)+2a+1).梅森數(shù)可能是素數(shù)梅森數(shù)可能是素數(shù), 也可能是合數(shù)也可能是合數(shù): 22 1=3, 23 1=7, 25 1=31

7、, 27 1=127都是素數(shù)都是素數(shù), 而而211 1=2047=2389是合數(shù)是合數(shù).到到2002年找到的最大梅森素數(shù)是年找到的最大梅森素數(shù)是213466917 1, 有有4百萬位百萬位. 定理定理11.2 有無窮多個素數(shù)有無窮多個素數(shù).證證 用反證法用反證法. 假設(shè)只有有窮多個素數(shù)假設(shè)只有有窮多個素數(shù), 設(shè)為設(shè)為p1,p2,pn,令令m=p1p2pn+1. 顯然顯然, pi m, 1in. 因此因此, 要么要么m本身本身是素數(shù)，要么存在大于是素數(shù)，要么存在大于pn的素數(shù)整除的素數(shù)整除m, 矛盾矛盾.課件10素數(shù)的分布素數(shù)的分布(續(xù)續(xù)) (n): 小于等于小于等于n的素數(shù)個數(shù)的素數(shù)個數(shù). 例

8、如例如 (0)= (1)=0, (2)=1, (3)= (4)=2, (5)=3. n 103 104 105 106 107 (n)n/ln n (n)n/ln n 168 1229 9592 78498 664579 145 1086 8686 72382 6204211.159 1.132 1.104 1.085 1.071課件11素數(shù)的分布素數(shù)的分布(續(xù)續(xù))定理定理11.3 當(dāng)當(dāng)n67時時, ,推論推論( (素數(shù)定理素數(shù)定理) ) 21ln)(23ln nnnn 1ln/)(limnnnn 課件12素數(shù)測試素數(shù)測試aa定理定理11.4 如果如果a是合數(shù)是合數(shù), 則則a必有小于等于必有小

9、于等于 的真因子的真因子.證證 由性質(zhì)由性質(zhì)11.1.6, a=bc, 其中其中1ba, 1c( )2=a, 矛盾矛盾.推論推論 如果如果a是合數(shù)是合數(shù), 則則a必有小于等于必有小于等于 的素因子的素因子.證證 由定理由定理, a有小于等于有小于等于 的真因子的真因子b. 如果如果b是素數(shù)是素數(shù), 則結(jié)論成立則結(jié)論成立. 如果如果b是合數(shù)是合數(shù), 由性質(zhì)由性質(zhì)11.1.7和性質(zhì)和性質(zhì)11.1.5, b有有素因子素因子pb . 根據(jù)性質(zhì)根據(jù)性質(zhì)11.1.2, p也是也是a 的因子的因子, 結(jié)論也結(jié)論也成立成立.aaaa課件13實例實例157161例例3 判斷判斷157和和161是否是素數(shù)是否是素

10、數(shù).解解 , 都小于都小于13, 小于小于13的素數(shù)有的素數(shù)有: 2, 3, 5, 7, 11.檢查結(jié)果如下檢查結(jié)果如下: 2 157, 3 157, 5 157, 7 157, 11 157 結(jié)論結(jié)論: 157是素數(shù)是素數(shù). 2 161, 3 161, 5 161, 7|161（161=723）結(jié)論：結(jié)論：161是合數(shù)是合數(shù).課件14埃拉托斯特尼埃拉托斯特尼(eratosthene)篩法篩法 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

11、 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1

12、9 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

13、22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

14、 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2

15、7 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100課件1511.2 最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù) 公約數(shù)、最大公約數(shù)公約數(shù)、最大公約數(shù) 公倍數(shù)、最小公倍數(shù)公倍數(shù)、最小公倍數(shù) 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除

16、法 互素互素課件16最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)d是是a與與b的的公因子公因子(公約數(shù)公約數(shù)): d |a且且d |bm是是a與與b的的公倍數(shù)公倍數(shù): a | m且且b | m定義定義11.3 設(shè)設(shè)a和和b是兩個不全為是兩個不全為0的整數(shù)的整數(shù), 稱稱a與與b的公因子中的公因子中最大的為最大的為a與與b的的最大公因子最大公因子, 或或最大公約數(shù)最大公約數(shù), 記作記作gcd(a,b). 設(shè)設(shè)a和和b是兩個非零整數(shù)是兩個非零整數(shù), 稱稱a與與b最小的正公倍數(shù)為最小的正公倍數(shù)為a與與b的的最小公倍數(shù)最小公倍數(shù), 記作記作lcm(a,b). 例如例如 gcd(12,18)=6, lcm

17、(12,18)=36. 對任意的正整數(shù)對任意的正整數(shù)a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a. 課件17最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)(續(xù)續(xù))定理定理11.5 (1) 若若a | m, b | m, 則則 lcm(a,b)| m. (2) 若若d |a, d |b, 則則d | gcd(a,b).證證 (1) 記記m=lcm(a,b), 設(shè)設(shè)m=qm+r, 0rd, 注意到注意到d |a, d|a, 由由(1), 得得m |a. 同理同理, m |b. 即即, m是是a和和b的公因子的公因子, 與與d是是a和和b的最大公約數(shù)矛盾的最大公約數(shù)矛盾.

18、 課件18最大公約數(shù)與最小公倍數(shù)最大公約數(shù)與最小公倍數(shù)(續(xù)續(xù))例例4 求求150和和220的最大公約數(shù)和最小公倍數(shù)的最大公約數(shù)和最小公倍數(shù).解解 150=2352, 168=2337. gcd(150,168)=21315070=6, lcm(150,168)=23315271=4200. 利用整數(shù)的素因子分解利用整數(shù)的素因子分解, 求最大公約數(shù)和最小公倍數(shù)求最大公約數(shù)和最小公倍數(shù). 設(shè)設(shè) 其中其中p1,p2,pk是不同的素數(shù)是不同的素數(shù), r1,r2,rk,s1,s2,sk是非負(fù)是非負(fù)整數(shù)整數(shù). 則則 gcd(a,b)= lcm(a,b)=,2121krkrrpppa ,2121ksksspppb ,),min(),min(2),min(12211kksrksrsrppp),max(),max(2),max(12211kksrksrsrppp課件19輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法定理定理11.6 設(shè)設(shè)a=qb+r, 其中其中a, b, q, r 都是整數(shù)都是整數(shù), 則則 gcd(a,b) = gcd(b,r).證證 只需證只需證a與與b和和b與與r有相同的公因子有相同的公因子. 設(shè)設(shè)d是是a與與b的公因的公因子子, 即即d |a且且d |b. 注意到注意到, r=a qb, 由性質(zhì)由性質(zhì)1