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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,整 除 理 论,1,、素数,(1),、素因子,(2),、素数分布,(3),、素数搜寻,(4),、素性判定,2,、,GCD,和,LCM,定义,若整数,a,0,，,1,，并且只有约数,1,和,a,，则称,a,是,素数,（或,质数,）；,否则称,a,为,合数,。,定理,任何大于,1,的整数,a,都至少有一个素约数。,推论,任何大于,1,的合数,a,必有一个不超过,a,1/2,的素约数。,定理,(,算术基本定理,),任何大于,1,的整数,n,可以,唯一,地表示成,(,标准分解式,),其中,p,1,p,2,p,k,是素数，,p,1,p,2,1),是素数，则,a,=2,，并且,n,是素数。,(3+k),ab,-1,必非素数。,4),、形如,2(2,n,)+1(,n,=0,1,2,),的数称为,Fermat,数,。,Fermat,曾猜测是素数：,F,0,F,1,F,2,F,3,F,4,是素数，,F,5,=641*6700417,是合数。,5),、,形如,4,n,3,的素数有无限多个。,6),、,越往后越,稀疏,：在正整数序列中,有任意长的区间中不含有素数。,对于大于等于,2,的整数,n,，连续,n,-1,个整数,n,!,2,n,!,3,n,!,n,都不是素数。,素数分布,7),、素数大小粗糙的估计,p,n,p,1,p,2,p,n-1,1,，,n,1,。,p,n,2,2,n,。,(,n,),(,log,2,n,),/2,。,8),、,素数定理,：,素数搜寻,寻找素数,的方法：,Eratosthenes,筛法,。,素性判定,确定型算法,试除法,尝试从,2,到,N,的整数是否整除,N,。,威廉斯方法、艾德利曼,、鲁梅利法、,马宁德拉.阿格拉瓦法,(,log(n)的多项式级算法,),随机算法,费马测试,利用费马小定理来测试。,若存在,a,，,(,a,n,)=1,，使得,a,n,1,1 mod,n,成立，则称,n,是关于基数,a,的伪素数（,Fermat,伪素数，,Carmichael,数）。,米勒,-,拉宾法、,GCD,和,LCM,定义,整数,a,1,a,2,a,k,的公共约数称为,a,1,a,2,a,k,的,公约数,。,不全为零的整数,a,1,a,2,a,k,的公约数中最大一个叫做,a,1,a,2,a,k,的,最大公约数,（或,最大公因数,），记为,(,a,1,a,2,a,k,),。,由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。,如果,(,a,1,a,2,a,k,),=,1,，则称,a,1,a,2,a,k,是,互素的,。,如果,(,a,i,a,j,),=,1,，,1,i,j,k,，,i,j,，则称,a,1,a,2,a,k,是,两两互素的,。,a,1,a,2,a,k,两两互素可以推出,(,a,1,a,2,a,k,)=,1,，反之则不然。,定义,整数,a,1,a,2,a,k,的公共倍数称为,a,1,a,2,a,k,的,公倍数,。,整数,a,1,a,2,a,k,的正公倍数中最小的一个叫做,a,1,a,2,a,k,的,最小公倍数,，记为,a,1,a,2,a,k,。,GCD,和,LCM,n,的标准分解式：,n,的正因数：,n,的正倍数,：,带余数除法,设,a,与,b,是两个整数，,b,0,，则存在唯一的两个整数,q,和,r,，使得,a,=,bq,r,，,0,r,|,b,|,。,定理,若,a,=,bq,r,，则,(,a,b,),=,(,b,r,),。,实际上给出一个求最大公因子的方法。,推论,设,a,1,a,2,a,n,为不全为零的整数，以,y,0,表示集合,A,=,y,：,y,=,a,1,x,1,a,n,x,n,，,x,i,Z,，,1,i,n,中的,最小正数,，则,对于任何,y,A,，,y,0,y,；,特别地，,y,0,a,i,，,1,i,n,。,证明：,设,y,0,=,a,1,x,1,a,n,x,n,，,对任意的,y,=,a,1,x,1,a,n,x,n,A,，存在,q,r,0,Z,，使得,y,=,qy,0,r,0,，,0,r,0,y,0,。,因此,r,0,=,y,qy,0,=,a,1,(,x,1,qx,1,),a,n,(,x,n,qx,n,),A,。,如果,r,0,0,，那么，因为,0,r,0,y,0,，所以,r,0,是,A,中比,y,0,还小的正数，,这与,y,0,的定义矛盾。所以,r,0,=0,，即,y,0,y,。,显然,a,i,A,（,1,i,n,），所以,y,0,整除每个,a,i,（,1,i,n,）。,GCD,和,LCM,定理,设,a,1,a,2,a,k,Z,，记,A=y,：,y=,，,x,i,Z,，,i,k,。,如果,y,0,是集合,A,中最小的正数，则,y,0,=(,a,1,a,2,a,k,),。,推论,设,d,是,a,1,a,2,a,k,的一个公约数，则,d,(,a,1,a,2,a,k,),。,最大公约数,不但是公约数中的最大的，而且是所有,公约数的倍数,。,定理,记,d,=(,a,1,a,2,a,k,),，则,(,a,1,/,d,a,2,/,d,a,k,/,d,)=1,。,特别地,(,a,/(,a,b,),b,/(,a,b,)=1,。,定理,(,a,1,a,2,a,k,),=1,的充要条件是存在整数,x,1,x,2,x,k,，,使得,a,1,x,1,a,2,x,2,a,k,x,k,=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,a,2,p,a,。,GCD,和,LCM,推论,若,(,a,b,)=1,，则,(,a,bc,)=(,a,c,),。,（备注,1,）,推论,若,(,a,b,i,)=1,，,1,i,n,，则,(,a,b,1,b,2,b,n,)=1,。,定理,对于任意的,n,个整数,a,1,a,2,a,n,，记,（备注,2,）,(,a,1,a,2,)=,d,2,，,(,d,2,a,3,)=,d,3,，,，,(,d,n-2,a,n-1,)=,d,n-1,，,(,d,n-1,a,n,)=,d,n,，则,d,n,=(,a,1,a,2,a,n,),。,GCD,和,LCM,定理,下面的等式成立：,(),a,1=|,a,|,，,a,a,=|,a,|,；,(),a,b,=,b,a,；,(),a,1,a,2,a,k,=|,a,1,|,|,a,2,|,|,a,k,|,；,(),若,a,b,，则,a,b,=|,b,|,。,推论,由,a,b=ab/(a,b),有：两个整数的任何公倍数可以被它们的最小公倍数整除。,定理,对于任意的,n,个整数,a,1,a,2,a,n,，记,a,1,a,2,=,m,2,，,m,2,a,3,=,m,3,，,，,m,n,2,a,n,1,=,m,n,1,，,m,n,1,a,n,=,m,n,，则,a,1,a,2,a,n,=,m,n,。,推论,若,m,是,a,1,a,2,a,n,的公倍数，则,a,1,a,2,a,n,|,m,。,GCD,和,LCM,定理,整数,a,1,a,2,a,n,两两互素，即,(,a,i,a,j,)=1,，,1,i,j,n,，,i,j,的充要条件是,a,1,a,2,a,n,=,a,1,a,2,a,n,。,如果,m,1,m,2,m,k,是两两互素的整数，,那么 要证明,m,=,m,1,m,2,m,k,整除某个整数,Q,，,只需证明对于每个,i,，,1,i,k,，都有,m,i,Q,。,这一点在实际计算中是很有用的。,对于多项式,f,(,x,),，要验证命题“,m,f,(,n,),，,n,Z”,是否成立，,可以验证“,m,f,(,r,),，,r,=0,1,m,1”,是否成立。,这需要做,m,次除法,。,但是，若分别验证“,m,i,f,(,r,i,),，,r,i,=0,1,m,i,1,，,1,i,k,”,是否成立，,则总共需要做,m,1,m,2,m,k,次除法,，显然远远少于,m,1,m,2,m,k,=m,。,GCD,和,LCM,辗转相除法,/Euclid,算法,设,a,与,b,是两个整数，,b,0,，依次做带余数除法：,a,=,bq,1,r,1,，,0,r,1,|,b,|,，,b,=,r,1,q,2,r,2,，,0,r,2,r,1,，,r,k,1,=,r,k,q,k,+1,r,k,+1,，,0,r,k,+1,r,k,，,(1),r,n,2,=,r,n,1,q,n,r,n,，,0,r,n,r,1,r,2,，所以式,(1),中只包含有限个等式。,GCD,和,LCM,辗转相除法,/Euclid,算法,引理,用下面的方式定义,Fibonacci,数列,F,n,：,F,1,=,F,2,=1,，,F,n,=,F,n,1,F,n,2,，,n,3,，,那么对于任意的整数,n,3,，有,F,n,n,2,，,(2),其中,=(1+5,1/2,)/2,。,定理,(Lame),设,a,b,N,，,a,b,，使用在式,(1),中的记号，则,n,5log,10,b,。,定理,使用式,(1),中的记号，记,P,0,=1,，,P,1,=q,1,，,P,k,=q,k,P,k,1,P,k,2,，,k,2,，,Q,0,=0,，,Q,1,=1,，,Q,k,=q,k,Q,k,1,Q,k,2,，,k,2,，,则,aQ,k,bP,k,=(,1),k,1,r,k,，,k=1,2,n,。,(3),利用辗转相除法可以求出整数,x,，,y,，使得,ax,by,=(,a,b,),。,(4),为此所需要的除法次数是,O(log,10,b,),。,GCD,和,LCM,辗转相除法,/Euclid,算法,但是，如果只需要计算,(,a,b,),而不需要求出使式,(4),成立的整数,x,与,y,，则,所需要的除法次数还可更少一些。,设,a,和,b,是正整数，基于下面的四个基本事实，只使用,被,2,除的除法运算,和,减法运算,就可以计算出,(,a,b,),。,(),若,a,b,，则,(,a,b,)=,a,；,(),若,a,=2,a,1,，,2|,a,1,，,b=2,b,1,，,2|,b,1,1,，则,(,a,b,)=2,(2,a,1,b,1,),；,(),若,2|,a,，,b=2,b,1,，,2|,b,1,，则,(,a,b,)=(,a,b,1,),；,(),若,2|,a,，,2|b,，则,(a,b)=(|(a-b)/2|,b),。,（见备注）,在实际计算过程中，若再灵活运用,最大公约数的性质,，,则可使得求最大公约数的过程更为简单。,GCD,和,LCM,