最新19初等数论课件PPT.ppt

《最新19初等数论课件PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、19初等数论以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。第19章初等数论19.1素数19.2最大公约数与最小公倍数19.3同余19.4一次同余方程19.5欧拉定理和费马小定理19.6初等数论在计算机科学技术中的几个应用素数与合数性质19.6如果d>

2、1,p是素数且d

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

4、ab,则必有p

5、a或者p

6、b.设p是素数且p

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

8、ai.性质19.8a>1是合数当且仅当a=bc,其中1

9、ab不一定能推出d

10、a或d

11、b.定义19.1素数(质数):大于1且只能被1和自身整除的正整数合数:大于1且不是素数例如,2,3,5,7,11是素数,4,6,8,9是合数.算术基本定理定理19.1(算术基本定理)设a>1,则a=,其中p1,p2,…,

12、pk是不相同的素数,r1,r2,…,rk是正整数,并且在不计顺序的情况下,该表示是惟一的.该表达式称作整数a的素因子分解.例如30=2×3×5,117=32×13,1024=210推论设a=,其中p1,p2,…,pk是不相同的素数,r1,r2,…,rk是正整数,则正整数d为a的因子的充分必要条件是d=,其中0≤si≤ri,i=1,2,…,k.例题例121560有多少个正因子?解21560=23×5×72×11由推论,21560的正因子的个数为4×2×3×2=48.例210!的二进制表示中从最低位数起有多少个连续的0?解2,3

13、,4=22,5,6=2×3,7,8=23,9=32,10=2×5.得10!=28×34×52×7,故10!的二进制表示中从最低位数起有8个连续的0.素数的分布梅森数(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

14、百万位.定理19.2有无穷多个素数.证用反证法.假设只有有穷多个素数,设为p1,p2,…,pn,令m=p1p2…pn+1.显然,pim,1≤i≤n.因此,要么m本身是素数，要么存在大于pn的素数整除m,矛盾.素数的分布(续)(n):小于等于n的素数个数.例如(0)=(1)=0,(2)=1,(3)=(4)=2,(5)=3.n103104105106107(n)n/lnn(n)n/lnn168122995927849866457914510868686723826204211.1591.1321.1041.08

15、51.071素数的分布(续)补充定理当n≥67时,定理19.3(素数定理)素数测试定理19.4如果a是合数,则a必有小于等于的真因子.证由性质19.8,a=bc,其中1()2=a,矛盾.推论如果a是合数,则a必有小于等于的素因子.证由定理19.4,a有小于等于的真因子b.如果b是素数,则结论成立.如果b是合数,由性质19.9和性质19.5,b有素因子p

16、于13的素数有:2,3,5,7,11.检查结果如下:2157,3157,5157,7157,11157结论:157是素数.2161,3161,5161,7

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

18、0616263646566676869707172737475767778798081828384858687888990919293949596979899100123456789101112131415161718192021222324252627282930313233343536