初等数论整除理论优秀课件.ppt

《初等数论整除理论优秀课件.ppt》由会员分享，可在线阅读，更多相关《初等数论整除理论优秀课件.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、初等数论整除理论第1页，本讲稿共19页v1、素数、素数 (1)、素因子、素因子 (2)、素数分布、素数分布 (3)、素数搜寻、素数搜寻 (4)、素性判定、素性判定v2、GCD和和LCM第2页，本讲稿共19页定义定义 若整数若整数a 0，1，并且只有约数，并且只有约数 1和和 a，则称，则称a是是素数素数（或（或质数质数）；）；否则称否则称a为为合数合数。定理定理 任何大于任何大于1的整数的整数a都至少有一个素约数。都至少有一个素约数。推论推论 任何大于任何大于1的合数的合数a必有一个不超过必有一个不超过a1/2的素约数。的素约数。定理定理(算术基本定理算术基本定理)任何大于任何大于1的整数的整

2、数n可以可以唯一唯一地表示成地表示成(标准分解式标准分解式)其中其中p1,p2,pk 是素数，是素数，p1 p2 1)是素数，则是素数，则a=2，并且，并且n是素数。是素数。(3+k)ab-1 必非素数。必非素数。4)、形如、形如2(2n)+1(n=0,1,2,)的数称为的数称为Fermat数数。Fermat曾猜测是素数：曾猜测是素数：F0,F1,F2,F3,F4是素数，是素数，F5=641*6700417是合数。是合数。5)、形如形如4n 3的素数有无限多个。的素数有无限多个。6)、越往后越越往后越稀疏稀疏：在正整数序列中：在正整数序列中,有任意长的区间中不含有素数。有任意长的区间中不含有素

3、数。对于大于等于对于大于等于2的整数的整数n，连续，连续n-1个整数个整数n!2,n!3,n!n都不是素数。都不是素数。第5页，本讲稿共19页素数分布素数分布7)、素数大小粗糙的估计、素数大小粗糙的估计 pn p1p2pn-1 1，n 1。pn 22n。(n)(log2n)/2。8)、素数定理素数定理：第6页，本讲稿共19页素数搜寻素数搜寻寻找素数寻找素数的方法：的方法：Eratosthenes筛法筛法。第7页，本讲稿共19页素性判定素性判定确定型算法确定型算法试除法试除法 尝试从尝试从2到到N的整数是否整除的整数是否整除N。威廉斯方法、艾德利曼、鲁梅利法、马宁德拉威廉斯方法、艾德利曼、鲁梅利

4、法、马宁德拉.阿格拉瓦法阿格拉瓦法(log(n)的多项式级算法的多项式级算法)随机算法随机算法费马测试费马测试 利用费马小定理来测试。利用费马小定理来测试。若存在若存在a，(a,n)=1，使得，使得a n 1 1 mod n成立，则称成立，则称n是关于基数是关于基数a的伪素数（的伪素数（Fermat伪素数，伪素数，Carmichael 数数）。）。米勒米勒-拉宾法、拉宾法、第8页，本讲稿共19页GCD和和LCM定义定义 整数整数a1,a2,ak的公共约数称为的公共约数称为a1,a2,ak 的的公约数公约数。不全为零的整数不全为零的整数a1,a2,ak 的公约数中最大一个叫做的公约数中最大一个叫

5、做a1,a2,ak 的的最大公约数最大公约数（或（或最大最大公因数公因数），记为），记为(a1,a2,ak)。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果如果(a1,a2,ak)=1，则称，则称a1,a2,ak 是是互素的互素的。如果如果(ai,aj)=1，1 i,j k，i j，则称，则称a1,a2,ak 是是两两互素的两两互素的。a1,a2,ak 两两互素可以推出两两互素可以推出(a1,a2,ak)=1，反之则不然。，反之则不然。定义定义 整数整数a1,a2,ak 的公共倍数称为

6、的公共倍数称为a1,a2,ak 的的公倍数公倍数。整数整数a1,a2,ak 的正公倍数中最小的一个叫做的正公倍数中最小的一个叫做a1,a2,ak 的的最小公倍数最小公倍数，记为，记为a1,a2,ak。第9页，本讲稿共19页GCD和和LCMn的标准分解式：的标准分解式：n的正因数：的正因数：n的正倍数的正倍数：第10页，本讲稿共19页带余数除法带余数除法 设设a与与b是两个整数，是两个整数，b 0，则存在唯一的两个整数，则存在唯一的两个整数q和和r，使得，使得 a=bq r，0 r|b|。定理定理 若若a=bq r，则，则(a,b)=(b,r)。实际上给出一个求最大公因子的方法。实际上给出一个求

7、最大公因子的方法。推论推论 设设a1,a2,an为不全为零的整数，以为不全为零的整数，以y0表示集合表示集合 A=y：y=a1x1 anxn，xi Z，1 i n 中的中的最小正数最小正数，则，则 对于任何对于任何y A，y0 y；特别地，特别地，y0 ai，1 i n。证明：证明：设设y0=a1x1 anxn，对任意的对任意的y=a1x1 anxn A，存在，存在q,r0 Z，使得，使得 y=qy0 r0，0 r0 y0。因此因此 r0=y qy0=a1(x1 qx1)an(xn qxn)A。如果如果r0 0，那么，因为，那么，因为0 r0 y0，所以，所以r0是是A中比中比y0还小的正数，

8、还小的正数，这与这与y0的定义矛盾。所以的定义矛盾。所以r0=0，即，即y0 y。显然显然ai A（1 i n），所以），所以y0整除每个整除每个ai（1 i n）。）。GCD和和LCM第11页，本讲稿共19页定理定理 设设a1,a2,ak Z，记，记 A=y：y=，xi Z，i k。如果如果y0是集合是集合A中最小的正数，则中最小的正数，则y0=(a1,a2,ak)。推论推论 设设d是是a1,a2,ak的一个公约数，则的一个公约数，则d(a1,a2,ak)。最大公约数最大公约数不但是公约数中的最大的，而且是所有不但是公约数中的最大的，而且是所有公约数的倍数公约数的倍数。定理定理 记记d=(a

9、1,a2,ak)，则，则(a1/d,a2/d,ak/d)=1。特别地特别地,(a/(a,b),b/(a,b)=1。定理定理 (a1,a2,ak)=1的充要条件是存在整数的充要条件是存在整数x1,x2,xk，使得使得 a1x1 a2x2 akxk=1。定理定理 对于任意的整数对于任意的整数a，b，c，下面的结论成立：，下面的结论成立：()由由b ac及及(a,b)=1可以推出可以推出b c；()由由b c，a c及及(a,b)=1可以推出可以推出ab c。推论推论 若若p是素数，则下述结论成立：是素数，则下述结论成立：()p ab p a或或p b；()p a2 p a。GCD和和LCM第12页

10、，本讲稿共19页推论推论 若若(a,b)=1，则，则(a,bc)=(a,c)。（备注（备注1）推论推论 若若(a,bi)=1，1 i n，则，则(a,b1b2bn)=1。定理定理 对于任意的对于任意的n个整数个整数a1,a2,an，记，记 （备注（备注2）(a1,a2)=d2，(d2,a3)=d3，(dn-2,an-1)=dn-1，(dn-1,an)=dn，则则 dn=(a1,a2,an)。GCD和和LCM第13页，本讲稿共19页定理定理 下面的等式成立：下面的等式成立：()a,1=|a|，a,a=|a|；()a,b=b,a；()a1,a2,ak=|a1|,|a2|,|ak|；()若若a b，

11、则，则a,b=|b|。推论推论 由由a,b=ab/(a,b)有：两个整数的任何公倍数可以被它们的最小公倍数整除。有：两个整数的任何公倍数可以被它们的最小公倍数整除。定理定理 对于任意的对于任意的n个整数个整数a1,a2,an，记，记 a1,a2=m2，m2,a3=m3，mn 2,an 1=mn 1，mn 1,an=mn，则，则 a1,a2,an=mn。推论推论 若若m是是a1,a2,an的公倍数，则的公倍数，则a1,a2,an|m。GCD和和LCM第14页，本讲稿共19页定理定理 整数整数a1,a2,an 两两互素，即两两互素，即(ai,aj)=1，1 i,j n，i j的充要条件是的充要条件

12、是 a1,a2,an=a1 a2 an。如果如果m1,m2,mk是两两互素的整数，是两两互素的整数，那么那么 要证明要证明m=m1m2mk整除某个整数整除某个整数Q，只需证明对于每个只需证明对于每个i，1 i k，都有，都有mi Q。这一点在实际计算中是很有用的。这一点在实际计算中是很有用的。对于多项式对于多项式f(x)，要验证命题，要验证命题“m f(n)，n Z”是否成立，是否成立，可以验证可以验证“m f(r)，r=0,1,m 1”是否成立。是否成立。这需要做这需要做m次除法次除法。但是，若分别验证但是，若分别验证“mi f(ri)，ri=0,1,mi 1，1 i k”是否成立，是否成立

13、，则总共需要做则总共需要做m1 m2 mk次除法次除法，显然远远少于，显然远远少于m1m2mk=m。GCD和和LCM第15页，本讲稿共19页辗转相除法辗转相除法/Euclid算法算法 设设a与与b是两个整数，是两个整数，b 0，依次做带余数除法：，依次做带余数除法：a=bq1 r1，0 r1|b|，b=r1q2 r2，0 r2 r1，rk 1=rkqk+1 rk+1，0 rk+1 rk，(1)rn 2=rn 1qn rn，0 rn r1 r2 ，所以式，所以式(1)中只包含有限个等式。中只包含有限个等式。GCD和和LCM第16页，本讲稿共19页辗转相除法辗转相除法/Euclid算法算法 引理引

14、理 用下面的方式定义用下面的方式定义Fibonacci数列数列Fn：F1=F2=1，Fn=Fn 1 Fn 2，n 3，那么对于任意的整数那么对于任意的整数n 3，有，有 Fn n 2，(2)其中其中 =(1+51/2)/2。定理定理(Lame)设设a,b N，a b，使用在式，使用在式(1)中的记号，则中的记号，则 n 5log10b。定理定理 使用式使用式(1)中的记号，记中的记号，记P0=1，P1=q1，Pk=qkPk 1 Pk 2，k 2，Q0=0，Q1=1，Qk=qkQk 1 Qk 2，k 2，则则aQk bPk=(1)k 1rk，k=1,2,n。(3)利用辗转相除法可以求出整数利用辗

15、转相除法可以求出整数x，y，使得，使得ax by=(a,b)。(4)为此所需要的除法次数是为此所需要的除法次数是O(log10b)。GCD和和LCM第17页，本讲稿共19页辗转相除法辗转相除法/Euclid算法算法 但是，如果只需要计算但是，如果只需要计算(a,b)而不需要求出使式而不需要求出使式(4)成立的整数成立的整数x与与y，则，则所需要的除法次数还可更少一些。所需要的除法次数还可更少一些。设设a和和b是正整数，基于下面的四个基本事实，只使用是正整数，基于下面的四个基本事实，只使用被被2除的除法运算除的除法运算和和减法运算减法运算就可以计算就可以计算出出(a,b)。()若若a b，则，则(a,b)=a；()若若a=2 a1，2|a1，b=2 b1，2|b1 1，则，则 (a,b)=2 (2 a1,b1)；()若若 2|a，b=2 b1，2|b1，则，则(a,b)=(a,b1)；()若若2|a，2|b，则，则(a,b)=(|(a-b)/2|,b)。（见备注）（见备注）在实际计算过程中，若再灵活运用在实际计算过程中，若再灵活运用最大公约数的性质最大公约数的性质，则可使得求最大公约数的过程更为简单。则可使得求最大公约数的过程更为简单。GCD和和LCM第18页，本讲稿共19页第19页，本讲稿共19页