《代数与数论》课件第十九章

1主要内容素数最大公约数与最小公倍数同余一次同余方程欧拉定理与费马小定理初等数论在计算机科学技术中的几个应用第六部分初等数论

12第十九章初等数论主要内容素数最大公约数与最小公倍数同余一次同余方程欧拉定理与费马小定理初等数论在计算机科学技术中的几个应用

2319.1素数今后只考虑正整数的正因子.平凡因子:1和自身真因子:除1和自身之外的因子例如,2,3是6的真因子设a,b是两个整数，且b≠0.如果存在整数c使a=bc，则称a被b整除，或b整除a，记作b|a.此时,又称a是b的倍数，b是a的因子.把b不整除a记作ba.例如,6有8个因子±1,±|2,±3和±6.

34整除的性质性质19.1若a|b且a|c,则x,y,有a|xb+yc.性质19.2若a|b且b|c,则a|c.性质19.3设m≠0,则a|b当且仅当ma|mb.性质19.4若a|b且b|a,则a=±b.性质19.5若a|b且b≠0,则|a|≤|b|.带余除法:a=qb+r,0≤r<|b|,记余数r=amodb例如,20mod6=2,13mod4=3,10mod2=0b|a当且仅当amodb=0

45素数与合数性质19.6如果d>1,p是素数且d|p,则d=p.性质19.7设p是素数且p|ab,则必有p|a或者p|b.设|p是素数且p|a1a2…ak,则必存在1≤i≤k,使得p|ai.注意:当d不是素数时,d|ab不一定能推出d|a或d|b.性质19.8a>1是合数当且仅当a=bc,其中1

56算术基本定理定理19.1(算术基本定理)设a>1,则a=,其中p1,p2,…,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.

67例题例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,故1|0!的二进制表示中从最低位数起有8个连续的0.

78素数的分布梅森数(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…p|n+1.显然,pim,1≤i≤n.因此,要么m本身是素数，要么存在大于pn的素数整除m,矛盾.

89素数的分布(续)(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(素数定理)

910素数测试定理11.4如果a是合数,则a必有小于等于的真因子.证由性质19.8,a=|bc,其中1()2=a,矛盾.推论如果a是合数,则a必有小于等于的素因子.证由定理,a有小于等于的真因子b.如果b是素数,则结论成立.如果b是合数,由性质19.9和性质19.5,b有素因子p

1011例3判断157和161是否是素数.解,都小于13,小于13的素数有:2,3,5,7,11.检查结果如下:2157,3157,5157,7157,11157结论:157是素数.2161,3161,5161,7|161（161=7×2|3）结论：161是合数.例题

11121234567891012345678910123456789101234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001234567891011121314151617181920|2122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061|6263646566676869707172737475767778