1、第11章 初等数论 1第11章 初等数论 11.1 素数 11.2 最大公约数与最小公倍数 11.3 同余 11.4 一次同余方程与中国剩余定理 11.5 欧拉定理和费马小定理 211.1 素数 整除、倍数和因子 带余除法 素数与合数 算术基本定理 筛法3整除、倍数和因子今后只考虑正整数的正因子.平凡因子 : 1和自身真因子 : 除1和自身之外的因子例如, 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个
2、因子1, 2, 3和6.4整除的性质性质11.1.1 若a |b且a |c, 则 x, y, 有a | xb+yc.性质11.1.2 若a |b且b |c, 则a |c.性质11.1.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, 则必存在
3、1ik, 使得p| ai.注意:当d不是素数时,d | ab不一定能推出d | a或d | b. 素数(质数):大于1且只能被1和自身整除的正整数合数: 大于1且不是素数例如, 2,3,5,7,11是素数, 4,6,8,9是合数. 6算术基本定理定理11.1(算术基本定理) 设a1, 则 a= , 其中 p1,p2,pk是不相同的素数, r1,r2,rk是正整数, 并且在不计顺序的情况下, 该表示是惟一的. 该表达式称作整数a的素因子分解. 例如 30=235, 117=3213, 1024=210 推论 设a= , 其中p1,p2,pk是不相同的素数, r1,r2,rk是正整数, 则正整数d
4、为a的因子的充分必要条件是d= , 其中0siri, i=1,2,k.7例题例1 21560有多少个正因子?解 21560=2357211由推论, 21560的正因子的个数为4232=48.例2 10!的二进制表示中从最低位数起有多少个连续的0?解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得 10!=2834527,故10!的二进制表示中从最低位数起有8个连续的0.8素数的分布梅森数(Marin Mersenne): 2p1, 其中p为素数 当n是合数时, 2n1一定是合数, 2ab1=(2a1)(2a(b1)+2a(b2)+2a+1).梅森数可能是
5、素数, 也可能是合数: 221=3, 231=7, 251=31, 271=127都是素数, 而2111=2047=2389是合数.到2002年找到的最大梅森素数是2134669171, 有4百万位. 定理11.2 有无穷多个素数.证 用反证法. 假设只有有穷多个素数, 设为p1,p2,pn,令m=p1p2pn+1. 显然, pi m, 1in. 因此, 要么m本身是素数，要么存在大于pn的素数整除m, 矛盾.9素数的分布(续)(n): 小于等于n的素数个数. 例如 (0)=(1)=0, (2)=1, (3)=(4)=2, (5)=3. n 103 104 105 106 107(n)n/ln
6、 n(n)n/ln n 168 1229 9592 78498 664579 145 1086 8686 72382 6204211.159 1.132 1.104 1.085 1.07110素数的分布(续)定理11.3 当n67时,推论(素数定理) 11素数测试定理11.4 如果a是合数, 则a必有小于等于 的真因子.证 由性质11.1.6, a=bc, 其中1ba, 1c( )2=a, 矛盾.推论 如果a是合数, 则a必有小于等于 的素因子.证 由定理, a有小于等于 的真因子b. 如果b是素数, 则结论成立. 如果b是合数, 由性质11.1.7和性质11.1.5, b有素因子pb . 根
7、据性质11.1.2, p也是a 的因子, 结论也成立.12实例例3 判断157和161是否是素数.解 , 都小于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是合数.13埃拉托斯特尼(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 1
8、3 14 15 16 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
9、16 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
10、 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 19 20 2
11、1 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
12、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 1001411.2 最大公约数与最小公倍数 公约数、最大公约数 公倍数、最小公倍数 辗转相除法 互素15最大公约数与最小公倍数d是a与b的公因子
13、(公约数): 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(12,18)=36. 对任意的正整数a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a. 16最大公约数与最小公倍数(续)定理11.5 (1) 若a | m, b | m, 则 lcm(a,b)| m. (2) 若d |a, d
14、 |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的最大公约数矛盾. 17最大公约数与最小公倍数(续)例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是非负
15、整数. 则 gcd(a,b)= lcm(a,b)=18辗转相除法定理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=aqb, 由性质11.1.1, 有d |r. 从而, d |b且d |r, 即d也是b与r的公因子. 反之一样, 设d是b与r的公因子, 即d |b且d |r. 注意到, a=qb+r, 故有d |a. 从而, d |a且d |b, 即d也是a与b的公因子. 19辗转相除法欧几里得(Euclid)算法设整数a, b,
16、 且b0, 求gcd(a,b).做带余除法 a=qb+r, 0r0, 再对b和r做带余除法 b=qr+r, 0r0是a和b的公因子, 有 d |xa+yb, 即 d |1. 从而 d=1, 得证a和b互素. a和b互素: gcd(a,b)=1两两互素: 任意两个都互素 例如, 8和15互素,而8和12不互素.4, 9, 11, 35两两互素.23实例例6 设a |c, b |c, 且a与b互素, 则ab |c.证 根据定理11.8, 存在整数x,y,使xa+yb=1. 两边同乘以c,得cxa+cyb=c. 又由a |xa和b |c, 可得ab |cxa. 同理, ab |cyb. 于是, 有ab |cxa+cyb, 即ab|c. 24
