离散数学第十九章

《离散数学第十九章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容素数最大公约数与最小公倍数同余一次同余方程欧拉定理与费马小定理初等数论在计算机科学技术中的几个应用第六部分初等数论1第十九章初等数论主要内容素数最大公约数与最小公倍数同余一次同余方程欧拉定理与费马小定理初等数论在计算机科学技术中的几个应用219.1素数今后只考虑正整数的正因子.平凡因子:1和自身真因子:除1和自身之外的因子例如,2,3是6的真因子设a,b是两个整数，且b≠0.如果存在整数c使a=bc，则称a被b整除，或b整除a，记作b

2、a.此时,又称a是b的倍数，b是a的因子.把b不整除a记作ba.例如,6有8个因子±1,±2,±3和±6.3

3、整除的性质性质19.1若a

4、b且a

5、c,则x,y,有a

6、xb+yc.性质19.2若a

7、b且b

8、c,则a

9、c.性质19.3设m≠0,则a

10、b当且仅当ma

11、mb.性质19.4若a

12、b且b

13、a,则a=±b.性质19.5若a

14、b且b≠0,则

15、a

16、≤

17、b

18、.带余除法:a=qb+r,0≤r<

19、b

20、,记余数r=amodb例如,20mod6=2,13mod4=3,10mod2=0b

21、a当且仅当amodb=04素数与合数性质19.6如果d>1,p是素数且d

22、p,则d=p.性质19.7设p是素数且p

23、ab,则必有p

24、a或者p

25、b.设p是素数且p

26、a1a2…ak,则必

27、存在1≤i≤k,使得p

28、ai.注意:当d不是素数时,d

29、ab不一定能推出d

30、a或d

31、b.性质19.8a>1是合数当且仅当a=bc,其中11,则a=,其中p1,p2,…,pk是不相同的素数,r1,r2,…,rk是正整数,并且在不计顺序的情况下,该表示是惟一的.该表达式称作整数a的素因子分解.例如30=2×

32、3×5,117=32×13,1024=210推论设a=,其中p1,p2,…,pk是不相同的素数,r1,r2,…,rk是正整数,则正整数d为a的因子的充分必要条件是d=,其中0≤si≤ri,i=1,2,…,k.6例题例121560有多少个正因子?解21560=23×5×72×11由推论,21560的正因子的个数为4×2×3×2=48.例210!的二进制表示中从最低位数起有多少个连续的0?解2,3,4=22,5,6=2×3,7,8=23,9=32,10=2×5.得10!=28×34×52×7,故10!的二进制表示中从最低位数起有8个连续的0.7素数的分布

33、梅森数(MarinMersenne):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,271=127都是素数,而2111=2047=23×89是合数.到2002年找到的最大梅森素数是2134669171,有4百万位.定理19.2有无穷多个素数.证用反证法.假设只有有穷多个素数,设为p1,p2,…,pn,令m=p1p2…pn+1.显然,pim,1≤i≤n.因此,要么m本身是素数，要么存在大于

34、pn的素数整除m,矛盾.8素数的分布(续)(n):小于等于n的素数个数.例如(0)=(1)=0,(2)=1,(3)=(4)=2,(5)=3.168122995927849866457914510868686723826204211.1591.1321.1041.0851.071(n)n/lnn(n)n/lnn103104105106107n定理19.3(素数定理)9素数测试定理11.4如果a是合数,则a必有小于等于的真因子.证由性质19.8,a=bc,其中1()2=a

35、,矛盾.推论如果a是合数,则a必有小于等于的素因子.证由定理,a有小于等于的真因子b.如果b是素数,则结论成立.如果b是合数,由性质19.9和性质19.5,b有素因子p

36、161（161=7×23）结论：161是合数.例题111234567891012345678910123456789101

37、234567891011121314151617181920212223242526272829303132