离散数学--11.1-2初等数论

《离散数学--11.1-2初等数论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章初等数论1第11章初等数论11.1素数11.2最大公约数与最小公倍数11.3同余11.4一次同余方程与中国剩余定理11.5欧拉定理和费马小定理211.1素数整除、倍数和因子带余除法素数与合数算术基本定理筛法3整除、倍数和因子今后只考虑正整数的正因子.平凡因子: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.4整除的性质性质11.1.1若a

3、b且a

4、

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

6、xb+yc.性质11.1.2若a

7、b且b

8、c,则a

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

10、b当且仅当ma

11、mb.性质11.1.4若a

12、b且b

13、a,则a=±b.性质11.1.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=05素数与合数性质11.1.6a>1是合数当且仅当a=bc,其中11,p是素数且d

22、p,则d=p.性质11.1.

23、9设p是素数且p

24、ab,则必有p

25、a或者p

26、b.设p是素数且p

27、a1a2…ak,则必存在1≤i≤k,使得p

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

29、ab不一定能推出d

30、a或d

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

32、,其中p1,p2,…,pk是不相同的素数,r1,r2,…,rk是正整数,则正整数d为a的因子的充分必要条件是d=,其中0≤si≤ri,i=1,2,…,k.7例题例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.8素数的分布梅森数(MarinMersenne):2p1,其中p为素数当n是

33、合数时,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百万位.定理11.2有无穷多个素数.证用反证法.假设只有有穷多个素数,设为p1,p2,…,pn,令m=p1p2…pn+1.显然,pim,1≤i≤n.因此,要么m本身是素数，要么存在大于pn的素数整除m,矛盾.9素数的分布(续)(n):小于等于n的素数个数.例如

34、(0)=(1)=0,(2)=1,(3)=(4)=2,(5)=3.n103104105106107(n)n/lnn(n)n/lnn168122995927849866457914510868686723826204211.1591.1321.1041.0851.07110素数的分布(续)定理11.3当n≥67时,推论(素数定理)11素数测试定理11.4如果a是合数,则a必有小于等于的真因子.证由性质11.1.6,a=bc,其中1()2=a,矛盾.推论如果a是合数,则a必有小于等于的素

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

36、161（161=7×23）结论：161是合数.13埃拉托斯特尼(Eratosthene)筛法123456789101234567891012345678910123

37、456789101112