《离散数学ppt19》由会员分享，可在线阅读，更多相关《离散数学ppt19（51页珍藏版）》请在金锄头文库上搜索。
1、主要内容 l 素数 l 最大公约数与最小公倍数 l 同余 l 一次同余方程 l 欧拉定理与费马小定理 l 初等数论在计算机科学技术中的几个应用第六部分 初等数论1第十九章 初等数论 主要内容 l 素数 l 最大公约数与最小公倍数 l 同余 l 一次同余方程 l 欧拉定理与费马小定理 l 初等数论在计算机科学技术中的几个应用219.1 素数今后只考虑正整数的正因子.平凡因子 : 1 和自身真因子 : 除 1 和自身之外的因子例如, 2, 3 是 6 的真因子设a, b是两个整数，且b0. 如果存在整数c 使 a=bc，则 称a 被b 整除，或 b 整除a，记作 b|a. 此时, 又称 a 是b
2、的 倍数，b是a 的因子. 把 b 不整除 a 记作 b a. 例如, 6有8个因子1, 2, 3和6.3整除的性质性质19.1 若a |b且a |c, 则 x, y, 有a | xb+yc.性质19.2 若a |b且b |c, 则a |c.性质19.3 设 m0, 则 a |b 当且仅当 ma | mb.性质19.4 若a | b且b | a, 则a=b.性质19.5 若a | b且b0, 则|a|b|. 带余除法: a=qb+r, 0r 1, p是素数且d | p, 则d=p.性质19.7 设p是素数且p | ab, 则必有p | a 或者 p | b. 设p是素数且p | a1a2ak,
3、 则必存在1ik, 使得p| ai.注意:当d不是素数时,d | ab不一定能推出d | a或d | b. 性质19.8 a1是合数当且仅当a=bc, 其中11, 则 a= , 其中p1,p2,pk是不相同的素数, r1,r2,rk是正整数, 并且在 不计顺序的情况下, 该表示是惟一的. 该表达式称作整数 a 的素因子分解. 例如 30=235, 117=3213, 1024=210 推论 设a= , 其中 p1, p2,pk 是不相同的素数, r1,r2,rk是正整数, 则正整数d为a的因子的充分必要条件是d= , 其中0siri, i=1,2,k.6例题例1 21560有多少个正因子?解
4、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.7素数的分布梅森数(Marin Mersenne): 2p1, 其中p为素数 当n是合数时, 2n1一定是合数,2ab1=(2a1)(2a(b1)+2a(b2)+2a+1). 梅森数可能是素数, 也可能是合数: 221=3, 231=7, 251=31, 271=127都是素数, 而2111=20
5、47=2389是合数. 到2002年找到的最大梅森素数是2134669171, 有4百万位. 定理19.2 有无穷多个素数. 证 用反证法. 假设只有有穷多个素数, 设为p1,p2,pn, 令m=p1p2pn+1. 显然, pi m, 1in. 因此, 要么m本身 是素数，要么存在大于pn的素数整除m, 矛盾.8素数的分布(续)(n): 小于等于n的素数个数. 例如 (0)=(1)=0, (2)=1, (3)=(4)=2, (5)=3. 168 1229 9592 78498 664579 145 1086 8686 72382 620421 1.159 1.132 1.104 1.085 1
6、.071(n ) n/ln n (n ) n/ln n 103 104 105 106 107 n定理19.3 (素数定理) 9素数测试定理11.4 如果a是合数, 则a必有小于等于 的真因子.证 由性质19.8, a=bc, 其中1( )2=a, 矛盾.推论 如果a是合数, 则a必有小于等于 的素因子.证 由定理, a有小于等于 的真因子b. 如果b是素数, 则结论成立. 如果b是合数, 由性质19.9和性质19.5, b有素因子pD, 注意到d |a, D|a, 由(1), 得m |a. 同理, m |b. 即, m是a和b的公因子, 与D是a和b的最大公约数矛盾. 最大公约数与最小公倍数
7、的性质14最大公约数与最小公倍数(续)例4 求150和220的最大公约数和最小公倍数.利用整数的素因子分解, 求最大公约数和最小公倍数. 设其中p1,p2,pk是不同的素数, r1,r2,rk,s1,s2,sk是非负整数. 则gcd(a,b)=lcm(a,b)=解 150=2352, 168=2337.gcd(150,168)=21315070=6,lcm(150,168)=23315271=4200. 15辗转相除法定理19.6 设a=qb+r, 其中a, b, q, r 都是整数, 则gcd(a,b) = gcd(b,r).证 只需证a与b和b与r有相同的公因子. 设d是a与b的公因子,
8、即d |a且d |b. 注意到, r=aqb, 由性质19.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的公因子. 16辗转相除法欧几里得(Euclid)算法辗转相除法 设整数a, b, 且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互素. 定义19.2 如果gcd(a
9、,b)=1, 则称a和b互素. 如果a1,a2,an中 的任意两个都互素, 则称它们两两互素. 例如, 8和15互素,而8和12不互素.4, 9, 11, 35两两互素.20例题例6 设a |c, b |c, 且a与b互素, 则ab |c.证 根据定理19.8, 存在整数x,y,使xa+yb=1. 两边同乘以c,得cxa+cyb=c. 又由a |xa和b |c, 可得ab |cxa. 同理, ab |cyb. 于是, 有ab |cxa+cyb, 即ab|c. 2119.3 同余定义19.3 设m是正整数, a和b是整数. 如果m|ab, 则称a模 m同余于b, 或a与b模m同余, 记作ab(m
10、od m). 如果a与b模 m不同余, 则记作a b(mod m). 例如, 153(mod 4), 160(mod 4), 14 2(mod 4), 15 16(mod 4). 下述两条都是a与b模m同余的充分必要条件: (1) a mod m = b mod m. (2) a=b+km, 其中k是整数.22同余的性质性质19.10 同余关系是等价关系, 即同余关系具有 自反性. aa(mod m) 传递性. ab(mod m)bc(mod m) ac(mod m). 对称性. ab(mod m) ba(mod m).缩写 a1a2ak (mod m). 性质19.11 模算术运算 若ab(
11、mod m), cd(mod m), 则acbd(mod m), acbd(mod m), akbk(mod m), 其中k是非负整数. 性质19.12 设d1, d | m, 则ab(mod m) ab(mod d). 性质19.13 设d1, 则ab(mod m) dadb(mod dm). 性质19.14 设c,m互素, 则ab(mod m) cacb(mod m).23模m等价类模m等价类: 在模m同余关系下的等价类. am, 简记作a. Zm: Z在模m同余关系下的商集 在Zm上定义加法和乘法如下: a, b,a+b=a+b, ab=ab. 例7 写出Z4的全部元素以及Z4上的加法表
12、和乘法表.解 Z4=0,1,2,3, 其中i=4k+i |kZ, i=0,1,2,3. 0 1 2 3 0 1 2 3 +0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2 0 1 2 3 0 1 2 3 0 0 0 0 0 1 2 3 0 2 0 2 0 3 2 124例8 3455的个位数是多少? 解 设3455的个位数为x,则3455x(mod10). 由341(mod 10), 有 3455=34113+3337(mod 10), 故3455的个位数是7.例9 日期的星期数y年m月d日星期数的计算公式:其中M=(m3)mod12 +1, Y=y M/11=100C+X Y年
13、M月:3月下一年2月, C:Y年的世纪数 )7(mod12/2/ )7/(224/4/dmMMMCCXXw +例题25例题例9 (续) 例如, 中华人民共和国成立日1949年10月1日,C=19, X=49, M=8, d=1,是星期六. 中国人民抗日战争胜利日1945年8月15日,C=19, X=45, M=6, d=15,是星期三. 2619.4 一次同余方程定理19.9 方程axc(mod m)有解的充要条件是gcd(a,m)|c. 证 充分性. 记d=gcd(a,m), a =da1, m =dm1, c =dc1, 其中a1与 m1互素. 由定理11.8, 存在x1和y1使得a1x1
14、+m1y1=1. 令x=c1x1, y=c1y1, 得a1x+m1y=c1. 等式两边同乘d, 得ax+my=c. 所以, axc(mod m).必要性. 设x是方程的解, 则存在y使得ax+my=c. 由性质19.1, 有d | c. 一次同余方程: axc(mod m), 其中m0. 一次同余方程的解: 使方程成立的整数例如, 2x0(mod 4)的解为x0(mod 2), 2x1(mod 4)无解27例题例10 解一次同余方程 6x3(mod 9).解 gcd(6,9)=3 | 3, 方程有解.取模9等价类的代表x= 4, 3, 2, 1, 0, 1, 2, 3, 4, 检查它们是否是方程的解, 计算结果如下:6(4)6(1)623(mod 9),6(3)60630(mod 9),6(2)61646(mod 9),得方程的解 x= 4, 1, 2(mod 9), 方程的最小正整数解是2. 28模m逆定理19.10 (1) a的模m逆存在的充要条件是a与m互素. (2)设a与
