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

'19初等数论 以整数集为典型代数系统的数论知识一直被认为是既神秘又古老。虽然绝大多数人自小学生起就开始认识它，而一些数学家却一辈子踏着它往皇冠上攀。现在，计算机终于给数论这门再纯洁不过的数学分支扬起了应用的帆。我们这里介绍的虽然只是初等数论的基础知识，但它们在计算机的数据表示、数据传输以及电子商务应用中的数据保密等方面起着非常重要的作用。 第19章初等数论19.1素数19.2最大公约数与最小公倍数19.3同余19.4一次同余方程19.5欧拉定理和费马小定理19.6初等数论在计算机科学技术中的几个应用 素数与合数性质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.性质19.8a>1是合数当且仅当a=bc,其中11,则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. 例题例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. 素数的分布梅森数(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本身是素数，要么存在大于pn的素数整除m,矛盾. 素数的分布(续)(n):小于等于n的素数个数.例如(0)=(1)=0,(2)=1,(3)=(4)=2,(5)=3.n103104105106107(n)n/lnn(n)n/lnn168122995927849866457914510868686723826204211.1591.1321.1041.0851.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有素因子pD,注意到d|a,D|a,由(1),得m|a.同理,m|b.即,m是a和b的公因子,与D是a和b的最大公约数矛盾. 最大公约数与最小公倍数(续)例4求150和220的最大公约数和最小公倍数.解150=2×3×52,168=23×3×7.gcd(150,168)=21×31×50×70=6,lcm(150,168)=23×31×52×71=4200.利用整数的素因子分解,求最大公约数和最小公倍数.设其中p1,p2,…,pk是不同的素数,r1,r2,…,rk,s1,s2,…,sk是非负整数.则gcd(a,b)=lcm(a,b)= 辗转相除法定理19.6设a=qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r).证只需证a与b和b与r有相同的公因子.设d是a与b的公因子,即d|a且d|b.注意到,r=aqb,由性质11.1.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的公因子. 辗转相除法—欧几里得(Euclid)算法设整数a,b,且b≠0,求gcd(a,b).做带余除法a=qb+r,0≤r<|b|.若r=0,则gcd(a,b)=b;若r>0,再对b和r做带余除法b=qr+r,0≤r0是a和b的公因子,有d|xa+yb,即d|1.从而d=1,得证a和b互素.a和b互素:gcd(a,b)=1两两互素:任意两个都互素例如,8和15互素,而8和12不互素.4,9,11,35两两互素. 实例例6设a|c,b|c,且a与b互素,则ab|c.证根据定理11.8,存在整数x,y,使xa+yb=1.两边同乘以c,得cxa+cyb=c.又由a|xa和b|c,可得ab|cxa.同理,ab|cyb.于是,有ab|cxa+cyb,即ab|c. 11.3同余同余模算术运算模m等价类 同余定义19.3设m是正整数,a和b是整数.如果m|ab,则称a模m同余于b,或a与b模m同余,记作a≡b(modm).如果a与b模m不同余,则记作ab(modm).例如,15≡3(mod4),16≡0(mod4),14≡2(mod4),1516(mod4).下述两条都是a与b模m同余的充分必要条件:(1)amodm=bmodm.(2)a=b+km,其中k是整数. 同余(续)性质19.10同余关系是等价关系,即同余关系具有①自反性.a≡a(modm)②传递性.a≡b(modm)∧b≡c(modm)a≡c(modm).③对称性.a≡b(modm)b≡a(modm).缩写a1≡a2≡…≡ak(modm).性质19.11(模算术运算)若a≡b(modm),c≡d(modm),则a±c≡b±d(modm),ac≡bd(modm),ak≡bk(modm),其中k是非负整数.性质19.12设d≥1,d|m,则a≡b(modm)a≡b(modd).性质19.13设d≥1,则a≡b(modm)da≡db(moddm).性质19.14设c,m互素,则a≡b(modm)ca≡cb(modm). 模m等价类模m等价类:在模m同余关系下的等价类.[a]m,简记作[a].Zm:Z在模m同余关系下的商集在Zm上定义加法和乘法如下:a,b,[a]+[b]=[a+b],[a]·[b]=[ab].+[0][1][2][3][0][1][2][3]·[0][1][2][3][0][1][2][3]例1写出Z4的全部元素以及Z4上的加法表和乘法表.解Z4={[0],[1],[2],[3]},其中[i]={4k+i|k∈Z},i=0,1,2,3.[0][1][2][3][1][2][3][0][2][3][0][1][3][0][1][2][0][0][0][0][0][1][2][3][0][2][0][2][0][3][2][1] 实例例23455的个位数是多少?解设3455的个位数为x,则3455≡x(mod10).由34≡1(mod10),有3455=34113+3≡33≡7(mod10),故3455的个位数是7.例3日期的星期数y年m月d日星期数的计算公式:其中M=(m－3)mod12+1,Y=yM/11=100C+XY年M月:3月~下一年2月,C:Y年的世纪数ëûëûëûëûëû)7(mod12/2/)7/(224/4/dmMMMCCXXw+++++-++º 实例例3(续)例如,中华人民共和国成立日1949年10月1日,C=19,X=49,M=8,d=1,是星期六.中国人民抗日战争胜利日1945年8月15日,C=19,X=45,M=6,d=15,是星期三. 11.4一次同余方程一次同余方程模m逆 一次同余方程定理19.9方程ax≡c(modm)有解的充要条件是gcd(a,m)|c.证充分性.记d=gcd(a,m),a=da1,m=dm1,c=dc1,其中a1与m1互素.由定理11.8,存在x1和y1使得a1x1+m1y1=1.令x=c1x1,y=c1y1,得a1x+m1y=c1.等式两边同乘d,得ax+my=c.所以,ax≡c(modm).必要性.设x是方程的解,则存在y使得ax+my=c.由性质11.1.1,有d|c.一次同余方程:ax≡c(modm),其中m>0.一次同余方程的解:使方程成立的整数例如,2x≡0(mod4)的解为x≡0(mod2),2x≡1(mod4)无解 实例例1解一次同余方程6x≡3(mod9).解gcd(6,9)=3|3,方程有解.取模9等价类的代表x=4,3,2,1,0,1,2,3,4,检查它们是否是方程的解,计算结果如下:6×(4)≡6×(1)≡6×2≡3(mod9),6×(3)≡6×0≡6×3≡0(mod9),6×(2)≡6×1≡6×4≡6(mod9),得方程的解x=4,1,2(mod9),方程的最小正整数解是2. 模m逆定理19.10(1)a的模m逆存在的充要条件是a与m互素.(2)设a与m互素,则在模m下a的模m逆是惟一的.证(1)这是定理11.9的直接推论.(2)设ab1≡1(modm),ab2≡1(modm).得a(b1b2)≡0(modm).由a与m互素,b1b2≡0(modm),得证b1≡b2(modm).定义19.4如果ab≡1(modm),则称b是a的模m逆,记作a1(modm)或a1.a1(modm)是方程ax≡1(modm)的解. 实例例2求5的模7逆.解5与7互素,故5的模7逆存在.方法1.解方程5x≡1(mod7).检查x=3,2,1,0,1,2,3,得到51≡3(mod7).方法2.做辗转相除法,求得整数b,k使得5b+7k=1,则b是5的模7逆.计算如下:7=5+2,5=2×2+1.回代1=52×2=52×(75)=3×52×7,得51≡3(mod7). 实例例2(续)方法3.直接观察53=15,151(mod7),得51≡3(mod7). 11.5欧拉定理和费马小定理欧拉函数欧拉定理费马小定理 欧拉(Eular)定理欧拉函数(n):{0,1,…,n1}中与n互素的数的个数例如(1)=(2)=1,(3)=(4)=2.当n为素数时(n)=n1;当n为合数时(n)