第十一讲 初等数论-2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,如何求出1n中的所有素数？,筛法,1,：,Eraosthenes（爱拉托斯尼筛法）筛法：每次求出一个新的素数，就把n以内的它的所有倍数都筛去。,经典的,Eraosthenes,筛法（核心代码）：,for(,int,i=2;i*i N;i+)if(,tagi,)continue;for(,int,j=i;i*j N;j+),tagi,*j=1;for(,int,i=2;i N;i+)if(!,tagi,),primetol,+=i;,素数求法,1,筛法,2,：,一种线性筛素数的方法（复杂度是,O(n,),）：,void,get_prime,(),int,cnt,=0;for(,int,i=2;i N;i+)if(!,tagi,),pcnt,+=i;for(,int,j=0;j,cnt,&,pj,*i N;j+),tagi,*,pj,=1;if(i%,pj,=0)break;,2,最大公约数,gcd,（最大公因子）,Euclidean,算法求两个正整数,a,和,b,的,gcd,。先令,r,0,为,a,，,r,1,为,b,，接着执行如下运算：,3,最大公约数,GCD,递归定理：对任意非负整数,a,和任意正整数,b,，,gcd(a,b)=gcd(b,a mod b),。,4,Extended-Euclidean,算法,定理：对于不完全为,0,的非负整数,a,，,b,，,gcd,（,a,，,b,）表示,a,，,b,的最大公约数,d,，必然存在整数对,x,，,y,，使得,gcd,（,a,，,b,）,=d=ax+by,。,5,扩展欧几里德算法,对于,gcd(a,b)=d,，对,(a,b),用欧几里德辗转相除会最终得到,(d,0),。此时对于把,a=d,b=0,代入,a*x+b*y=d,，显然,x=1,，,y,可以为任意值。,我们可以用,a=d,b=0,的情况逆推出来任何,gcd(a,b)=d,满足,a*x+b*y=d,的解。如果,x,0,，,y,0,是,b*x+(a%b)*y=d,的解，那么对于,a*x+b*y=d,的解呢？,6,扩展欧几里德算法,b*x+(a%b)*y=d,b*x+(a-a/b*b)*y=a*y+b*(x-a/b*y)，,所以a*x+b*y=d的解x,1,=y,0,，y,1,=x,0,-a/b*y,0,;,这样我们可以程序迭代了。,注：,a,b,为正整数，设集合,A=x*a+y*b|x,y,是整数,，则,A,中最小正元素是,gcd(a,b),7,扩展欧几里德算法,程序代码如下：,int,extended_,gcd(int,a,int,b,int,&x,int,&y),int,t,gcd,;,if(b=0),x=1;,y=0;,return a;,gcd,=extended_,gcd,(b,a%b,x,y);,t=x;x=y;y=t a/b*y;,return,gcd,;,8,二元一次不定方程,利用扩展欧几里得算法，很容易求得诸如,ax+by,=c(1),这样二元一次不定方程的整数解问题。,设,a,b,的最大公约数为,d=,（,a,b,），则,a=a,1,d,，,b=b,1,d,，,(a,1,b,1,)=1,，因此,(1),可表示为：,d(a1x+b1y)=c,于是，当且仅当,d|c,时,(1),方有整数解,9,二元一次不定方程,显然，若,x0,y0,为,(1),的解，那么对任意整数,t,有,x=x0-bt,y=y0+at,均为该方程的解,因此，可设计一个求解出特解的算法，然后利用这条性质得到该方程的通解,步骤如下：,求解,a,、,b,的最大公约数,d=(,a,b,),，若,d c,，则方程无整数解，否则，将方程两边同时除以,d,，得到,:,a0 x+b0y=c0 (2),使用扩展欧几里得算法计算上述方程的解,x0,y0,，求得特解,x1=x0c0,，,y1=y0c0,。,代入通解得,x=x0c0-a0t,，,y=y0c0+b0t,10,POJ 1061,青蛙的约会,两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。,11,我们把这两只青蛙分别叫做青蛙,A,和青蛙,B,，并且规定纬度线上东经,0,度处为原点，由东往西为正方向，单位长度,1,米，这样我们就得到了一条首尾相接的数轴。设青蛙,A,的出发点坐标是,x,，青蛙,B,的出发点坐标是,y,。青蛙,A,一次能跳,m,米，青蛙,B,一次能跳,n,米，两只青蛙跳一次所花费的时间相同。纬度线总长,L,米。现在要你求出它们跳了几次以后才会碰面。,12,分析：,先明确下各个变量代表的意思：,x,：青蛙,A,的出发点坐标,y,：青蛙,B,的出发点坐标,m,：青蛙,A,一次能跳,m,米,n,：青蛙,B,一次能跳,n,米,L,：纬度线总长,L,米,求：需要几步可以相遇,13,假设需要,s,步可以相遇，则必有以下关系成立,(x+,sm,)(y+,sn,)=,kL,(k Z),变形为：,(n,m)s,+,Lk,=x y,（,2,）,于是我们的题目就变成了求（,2,）式中,s,的最小非负整数解,14,第三章 同 余,同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一,.,本章介绍同余的基本概念，剩余类和完全剩余系,.,15,16,求出整数,k,，使,a,k,1(mod,m,),；,求出正整数,r,，,r,1,，则,p,a,，,所以,a,p,0,a,(mod,p,),a,m,),1(mod,m,),47,二、定理的应用举例,例,1,求,313,159,被,7,除的余数。,解：,313,159,所以由欧拉定理得,a,m,),1(mod,m,),从而,5,159,=(5,6,),26,5,3,5,3,(mod 7),5,3,=25,5,4,5,6(mod 7),。,即,313,159,被,7,除的余数为,6,。,48,例,3,设,x,1,x,2,x,(,m,),是模,m,的简化剩余系，,则,(,x,1,x,2,x,(,m,),),2,1,(,mod,m,).,证：,记,P,=,x,1,x,2,x,(,m,),，,则,(,P,m,)=1.,1,i,(,m,),，,则,y,1,y,2,y,(,m,),也是模,m,的简化剩余系，,再由,Eule,r,定理得证,.,a,m,),1(mod,m,),49,例,4,设,a,，,b,，,c,，,m,是正整数，,m,1,，,(,b,m,)=1,，,并且,b,a,1(mod,m,),，,b,c,1(mod,m,),，,记,d,=(,a,c,),，则,b,d,1(mod,m,),。,证,利用辗转相除法可以求出整数,x,，,y,，,使得,ax,cy,=,d,，,显然,xy,0,，,y,0,，,则,1,b,ax,=,b,d,b,cy,=,b,d,(,b,c,),y,b,d,(mod,m,),若,x,0,，,则,1,b,cy,=,b,d,b,ax,=,b,d,(,b,a,),x,b,d,(mod,m,),。,50,例,5,设,n,是正整数，记,F,n,=,证：,容易验证，当,n,4,时,F,n,是素数，,由,Fermat,定理可知结论显然成立。,a,p,a,(mod,p,),。,当,n,5,时，有,n,1 0,，且,(,a,m,)=1,，,a,1,是,m,对模,a,的最小,非负剩余，则同余方程,等价于同余方程,ax,b,(mod,m,),证：设,x,是,ax,b,(mod,m,),的解，,即,x,是同余方程,的解。,由假设条件知：这两个同余方程都有且只有一个解，,所以这两个同余方程等价。,65,例,3,解同余方程,6,x,7(mod 23),。,解 由定理,4,，依次得到,6,x,7(mod 23),5,x,7,3,2(mod 23),3,x,2,4,8(mod 23),2,x,87,10(mod 23),x,5(mod 23),。,ax,b,(mod,m,),66,定理,5,四、其他解法,应用欧拉定理,设,(,a,m,)=1,，并且有整数,0,使得,a,1,(,mod,m,),，,则同余方程,ax,b,(mod,m,),的解是,x,ba,1,(,mod m,).,注,1,：直接验证即可。,注,2,：由定理,5,及,Euler,定理可知，若,(,a,m,)=1,，则,x,ba,(,m,),1,(,mod m,),是同余方程,ax,b,(mod,m,),的解。,例,4,解同余方程,解：,x,ba,(21),1,67,4.2,孙子定理,68,问题：,今有物不知其数，三三数之剩二，五五数之,剩三，七七数之剩二，问物几何。,孙子算经,分析：,设所求物数为,x,，则有,称之为同余式组。,即要求这些同余式的公共解。,69,问题：,今有物不知其数，三三数之剩二，五五数之,剩三，七七数之剩二，问物几何。,孙子算经,除数,余数,最小公倍数,衍数,乘率,各 总,答 数,最小,答数,3,2,3,5,7,=105,5,7,2,35,2,3,140+63+30,=233,233-2,105=23,5,3,3,7,1,21,1,3,7,2,3,5,1,15,1,2,70,问题,1,：,今有物不知其数，三三数之剩二，五五数之,剩二，七七数之剩二，问物几何。,问题,2,：,今有物不知其数，三三数之剩二，五五数之,剩三，问物几何。,x,-2,是,3,、,5,、,7,的公倍数。,71,问题：,今有物不知其数，三三数之剩二，五五数之,剩三，七七数之剩二，问物几何。,孙子算经,72,一、同余式组的解法,中国剩余定理,定理,1,孙子定理,m,1,m,2,m,k,是两两互质的正整数，,记,m,=,m,1,m,2,m,k,，,则,(1),的解为,其中，整数,M,i,（,1,i,k,），满足,M,i,M,i,1(mod,m,i,).,设有同余式组,73,例,1,解同余式组,衍数,乘率,74,例,2,韩信点兵,有兵一队，若列成五行纵队，则,末行,1,人；成六行纵队，则末行,5,人；成七行纵队，,则末行,4,人；成十一行纵队，则末行,10,人。求兵数。,余数,衍数,75,列表如下：,5,1,2310,462,6,5,385,7,4,330,11,10,210,其他略,1,462,3,53851,4,330,1,10,210,1,6731,3,1,1,1,76,定理,2,在定理,1,的条件下，若式,(1),中的,a,1,a,2,a,k,分别通过模,m,1,m,2,m,k,的完全剩余系，则式,(2),中,的,x,通过模,m,1,m,2,m,k,的完全剩余系。,证明：,则,x,通过,m,1,m,2,m,k,个整数，,且容易它们是两两不同余的。,77,