初等数论1-整除理论.ppt

整除理论,1、素数(1)、素因子(2)、素数分布(3)、素数搜寻(4)、素性判定2、GCD和LCM,定义若整数a0，1，并且只有约数1和a，则称a是素数（或质数）；否则称a为合数。定理任何大于1的整数a都至少有一个素约数。推论任何大于1的合数a必有一个不超过a1/2的素约数。定理(算术基本定理)任何大于1的整数n可以唯一地表示成(标准分解式)其中p1,p2,pk是素数，p1p21)是素数，则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)、形如4n3的素数有无限多个。6)、越往后越稀疏：在正整数序列中,有任意长的区间中不含有素数。对于大于等于2的整数n，连续n-1个整数n!2,n!3,n!n都不是素数。,素数分布,7)、素数大小粗糙的估计pnp1p2pn-11，n1。pn22n。(n)(log2n)/2。8)、素数定理：,素数搜寻,寻找素数的方法：Eratosthenes筛法。,素性判定,确定型算法试除法尝试从2到N的整数是否整除N。威廉斯方法、艾德利曼、鲁梅利法、马宁德拉.阿格拉瓦法(log(n)的多项式级算法)随机算法费马测试利用费马小定理来测试。若存在a，(a,n)=1，使得an11modn成立，则称n是关于基数a的伪素数（Fermat伪素数，Carmichael数）。米勒-拉宾法、,GCD和LCM,定义整数a1,a2,ak的公共约数称为a1,a2,ak的公约数。不全为零的整数a1,a2,ak的公约数中最大一个叫做a1,a2,ak的最大公约数（或最大公因数），记为(a1,a2,ak)。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果(a1,a2,ak)=1，则称a1,a2,ak是互素的。如果(ai,aj)=1，1i,jk，ij，则称a1,a2,ak是两两互素的。a1,a2,ak两两互素可以推出(a1,a2,ak)=1，反之则不然。定义整数a1,a2,ak的公共倍数称为a1,a2,ak的公倍数。整数a1,a2,ak的正公倍数中最小的一个叫做a1,a2,ak的最小公倍数，记为a1,a2,ak。,GCD和LCM,n的标准分解式：n的正因数：n的正倍数：,带余数除法设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得a=bqr，0r|b|。定理若a=bqr，则(a,b)=(b,r)。实际上给出一个求最大公因子的方法。推论设a1,a2,an为不全为零的整数，以y0表示集合A=y：y=a1x1anxn，xiZ，1in中的最小正数，则对于任何yA，y0y；特别地，y0ai，1in。证明：设y0=a1x1anxn，对任意的y=a1x1anxnA，存在q,r0Z，使得y=qy0r0，0r0y0。因此r0=yqy0=a1(x1qx1)an(xnqxn)A。如果r00，那么，因为0，所以式(1)中只包含有限个等式。,GCD和LCM,辗转相除法/Euclid算法引理用下面的方式定义Fibonacci数列Fn：F1=F2=1，Fn=Fn1Fn2，n3，那么对于任意的整数n3，有Fnn2，(2)其中=(1+51/2)/2。定理(Lame)设a,bN，ab，使用在式(1)中的记号，则n5log10b。定理使用式(1)中的记号，记P0=1，P1=q1，Pk=qkPk1Pk2，k2，Q0=0，Q1=1，Qk=qkQk1Qk2，k2，则aQkbPk=(1)k1rk，k=1,2,n。(3)利用辗转相除法可以求出整数x，y，使得axby=(a,b)。(4)为此所需要的除法次数是O(log10b)。,GCD和LCM,辗转相除法/Euclid算法但是，如果只需要计算(a,b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。设a和b是正整数，基于下面的四个基本事实，只使用被2除的除法运算和减法运算就可以计算出(a,b)。()若ab，则(a,b)=a；()若a=2a1，2|a1，b=2b1，2|b11，则(a,b)=2(2a1,b1)；()若2|a，b=2b1，2|b1，则(a,b)=(a