离散数学1112初等数论

1、课件1第第1111章章 初等数论初等数论 课件2第第1111章章 初等数论初等数论 11.1 素数素数 11.2 最大公约数与最小公倍数最大公约数与最小公倍数 11.3 同余同余 11.4 一次同余方程与中国剩余定理一次同余方程与中国剩余定理 11.5 欧拉定理和费马小定理欧拉定理和费马小定理 课件311.1 素数素数 整除、倍数和因子整除、倍数和因子 带余除法带余除法 素数与合数素数与合数 算术基本定理算术基本定理 筛法筛法课件4整除、倍数和因子整除、倍数和因子今后只考虑正整数的正因子今后只考虑正整数的正因子.平凡因子平凡因子 : 1和自身和自身真因子真因子 : 除除1和自身之外的因子和自身

2、之外的因子例如例如, 2, 3 是是 6 的真因子的真因子设设a, b是两个整数，且是两个整数，且b0. 如果存在整数如果存在整数c 使使 a=bc，则则称称a 被被b 整除整除，或，或 b 整除整除a，记作记作 b|a. 此时此时, 又称又称 a 是是b 的的倍数倍数，b是是a 的的因子因子. 把把 b 不整除不整除 a 记作记作 b a.例如例如, 6有有8个因子个因子1, 2, 3和和6.课件5整除的性质整除的性质性质性质11.1.1 若若a |b且且a |c, 则则 x, y, 有有a | xb+yc.性质性质11.1.2 若若a |b且且b |c, 则则a |c.性质性质11.1.3

3、 设设 m0, 则则 a |b 当且仅当当且仅当 ma | mb.性质性质11.1.4 若若a | b且且b | a, 则则a=b.性质性质11.1.5 若若a | b且且b0, 则则|a|b|. 带余除法带余除法: a=qb+r, 0r 1是合数当且仅当是合数当且仅当a=bc, 其中其中1ba, 1c1, p是素数且是素数且d | p, 则则d=p.性质性质11.1.9 设设p是素数且是素数且p | ab, 则必有则必有p | a 或者或者 p | b. 设设p是素数且是素数且p | a1a2ak, 则必存在则必存在1ik, 使得使得p| ai.注意注意:当当d不是素数时不是素数时,d |

4、ab不一定能推出不一定能推出d | a或或d | b. 素数素数(质数质数):大于大于1且只能被且只能被1和自身整除的正整数和自身整除的正整数合数合数: 大于大于1且不是素数且不是素数例如例如, 2,3,5,7,11是素数是素数, 4,6,8,9是合数是合数. . 课件7算术基本定理算术基本定理定理定理11.1(算术基本定理算术基本定理) 设设a1, 则则 a= , 其中其中 p1,p2,pk是不相同的素数是不相同的素数, r1,r2,rk是正整数是正整数, 并且在不并且在不计顺序的情况下计顺序的情况下, 该表示是惟一的该表示是惟一的. 该表达式称作整数该表达式称作整数a的的素因子分解素因子分

5、解. 例如例如 30=235, 117=3213, 1024=210 推论推论 设设a= , 其中其中p1,p2,pk是不相同的素数是不相同的素数, r1,r2,rk是正整数是正整数, 则正整数则正整数d为为a的因子的充分必要条件的因子的充分必要条件是是d= , 其中其中0siri, i=1,2,k.krkrrppp2121krkrrppp2121kskssppp2121课件8例题例题例例1 21560有多少个正因子有多少个正因子?解解 21560=2357211由推论由推论, 21560的正因子的个数为的正因子的个数为4232=48.例例2 10!的二进制表示中从最低位数起有多少个连续的的二

6、进制表示中从最低位数起有多少个连续的0?解解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得得 10!=2834527,故故10!的二进制表示中从最低位数起有的二进制表示中从最低位数起有8 8个连续的个连续的0.课件9素数的分布素数的分布梅森数梅森数(marin mersenne): 2p 1, 其中其中p为素数为素数 当当n是合数时是合数时, 2n 1一定是合数一定是合数, 2ab 1=(2a 1)(2a(b 1)+2a(b 2)+2a+1).梅森数可能是素数梅森数可能是素数, 也可能是合数也可能是合数: 22 1=3, 23 1=7, 25 1=31

7、, 27 1=127都是素数都是素数, 而而211 1=2047=2389是合数是合数.到到2002年找到的最大梅森素数是年找到的最大梅森素数是213466917 1, 有有4百万位百万位. 定理定理11.2 有无穷多个素数有无穷多个素数.证证 用反证法用反证法. 假设只有有穷多个素数假设只有有穷多个素数, 设为设为p1,p2,pn,令令m=p1p2pn+1. 显然显然, pi m, 1in. 因此因此, 要么要么m本身本身是素数，要么存在大于是素数，要么存在大于pn的素数整除的素数整除m, 矛盾矛盾.课件10素数的分布素数的分布(续续) (n): 小于等于小于等于n的素数个数的素数个数. 例

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素数的分布素数的分布(续续)定理定理11.3 当当n67时时, ,推论推论( (素数定理素数定理) ) 21ln)(23ln nnnn 1ln/)(limnnnn 课件12素数测试素数测试aa定理定理11.4 如果如果a是合数是合数, 则则a必有小于等于必有小

9、于等于 的真因子的真因子.证证 由性质由性质11.1.6, a=bc, 其中其中1ba, 1c( )2=a, 矛盾矛盾.推论推论 如果如果a是合数是合数, 则则a必有小于等于必有小于等于 的素因子的素因子.证证 由定理由定理, a有小于等于有小于等于 的真因子的真因子b. 如果如果b是素数是素数, 则结论成立则结论成立. 如果如果b是合数是合数, 由性质由性质11.1.7和性质和性质11.1.5, b有有素因子素因子pb . 根据性质根据性质11.1.2, p也是也是a 的因子的因子, 结论也结论也成立成立.aaaa课件13实例实例157161例例3 判断判断157和和161是否是素数是否是素

10、数.解解 , 都小于都小于13, 小于小于13的素数有的素数有: 2, 3, 5, 7, 11.检查结果如下检查结果如下: 2 157, 3 157, 5 157, 7 157, 11 157 结论结论: 157是素数是素数. 2 161, 3 161, 5 161, 7|161（161=723）结论：结论：161是合数是合数.课件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 最大公约数与最小公倍数最大公约数与最小公倍数 公约数、最大公约数公约数、最大公约数 公倍数、最小公倍数公倍数、最小公倍数 辗转相除法辗转相除

16、法 互素互素课件16最大公约数与最小公倍数最大公约数与最小公倍数d是是a与与b的的公因子公因子(公约数公约数): d |a且且d |bm是是a与与b的的公倍数公倍数: a | m且且b | m定义定义11.3 设设a和和b是两个不全为是两个不全为0的整数的整数, 称称a与与b的公因子中的公因子中最大的为最大的为a与与b的的最大公因子最大公因子, 或或最大公约数最大公约数, 记作记作gcd(a,b). 设设a和和b是两个非零整数是两个非零整数, 称称a与与b最小的正公倍数为最小的正公倍数为a与与b的的最小公倍数最小公倍数, 记作记作lcm(a,b). 例如例如 gcd(12,18)=6, lcm

17、(12,18)=36. 对任意的正整数对任意的正整数a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a. 课件17最大公约数与最小公倍数最大公约数与最小公倍数(续续)定理定理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), 设设m=qm+r, 0rd, 注意到注意到d |a, d|a, 由由(1), 得得m |a. 同理同理, m |b. 即即, m是是a和和b的公因子的公因子, 与与d是是a和和b的最大公约数矛盾的最大公约数矛盾.

18、 课件18最大公约数与最小公倍数最大公约数与最小公倍数(续续)例例4 求求150和和220的最大公约数和最小公倍数的最大公约数和最小公倍数.解解 150=2352, 168=2337. gcd(150,168)=21315070=6, lcm(150,168)=23315271=4200. 利用整数的素因子分解利用整数的素因子分解, 求最大公约数和最小公倍数求最大公约数和最小公倍数. 设设 其中其中p1,p2,pk是不同的素数是不同的素数, r1,r2,rk,s1,s2,sk是非负是非负整数整数. 则则 gcd(a,b)= lcm(a,b)=,2121krkrrpppa ,2121ksksspppb ,),min(),min(2),min(12211kksrksrsrppp),max(),max(2),max(12211kksrksrsrppp课件19辗转相除法辗转相除法定理定理11.6 设设a=qb+r, 其中其中a, b, q, r 都是整数都是整数, 则则 gcd(a,b) = gcd(b,r).证证 只需证只需证a与与b和和b与与r有相同的公因子有相同的公因子. 设设d是是a与与b的公因的公因子子, 即即d |a且且d |b. 注意到注意到, r=a qb, 由性质由性质1