资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,剩余系,和欧拉函数,剩余系和欧拉函数,一、基本概念,定义,1,设,R,是模,m,的一个剩余类，若有,a,R,，使得,(,a,m,),=1，则称,R,是模,m,的一个简化剩余类,。,即与模,m,互质的剩余类。,注：若,R,是模的简化剩余类，则,R,中的数都与,m,互素。,例如，模,4的简化剩余类有两个：,R,1,(4)=,7,3,1,5,9,，,R,3,(4)=,5,1,3,7,11,。,一、基本概念定义1 设R是模m的一个剩余类，若有aR，使,定义,2,对于正整数,k,，令函数,(,k,)的值等于模,k,的所有,简化剩余类的个数，称,(,k,)为,Euler,函数。,容易验证：,(2)=1,，,(3)=2,，,(4)=2,，,(7)=6,。,注：,(,m,)就是在,m,的一个完全剩余系中与,m,互素的,整数的个数，且,定义,3,对于正整数,m,，从模,m,的每个简化剩余类中,各取一个数,x,i,，构成一个集合,x,1,x,2,x,(,m,),，,称为模,m,的一个简化剩余系（或简称为简化系）。,定义2 对于正整数k，令函数(k)的值等于模k的所有简化,注：由于选取方式的任意性，模,m,的简化剩余系,有无穷多个。,例如，集合,9,5,3,1,是模,8的简化剩余系；,集合,1,3,5,7也是模8的简化剩余系.,集合,1,3,5,7称为最小非负简化剩余系。,注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，,二、主要性质,定理,1,整数集合,A,是模,m,的简化剩余系的充要条件是：,A,中含有,(,m,)个整数；,A,中的任何两个整数对模,m,不同余；,A,中的每个整数都与,m,互素。,说明：简化剩余系是某个完全剩余系中的部分元素,构成的集合，故满足条件,2；,由定义,1易知满足条件3；,由定义,3易知满足条件1。,二、主要性质 定理1 整数集合A是模m的简化剩余系的充要条,定理,2,设,a,是整数，,(,a,m,)=1，,B,=,x,1,x,2,x,(,m,),是模,m,的简化剩余系，则集合,A,=,ax,1,ax,2,ax,(,m,),也是模,m,的简化剩余系。,证明,显然，集合,A,中有,(,m,)个整数。,由于,(,a,m,)=1，,对于任意的,x,i,（,1,i,(,m,)）,，,x,i,B,，,有,(,ax,i,m,)=(,x,i,m,)=1。,故,A,中的每一个数都与,m,互素。,而且，,A,中的任何两个不同的整数对模,m,不同余。,因为，若有,x,x,B,，使得,a x,ax,(mod,m,)，,那么，,x,x,(mod,m,)，,于是,x,=,x,。,由以上结论及定理,1可知集合,A,是模,m,的一个简化系。,定理2 设a是整数，(a,m)=1，B=x,注：在定理,2的条件下，若,b,是整数，集合,ax,1,b,ax,2,b,ax,(,m,),b,不一定是模,m,的简化剩余系。,例如，取,m,=4，,a,=1，,b,=1，,以及模,4的简化剩余系1,3。,但,2，4不是模4的简化剩余系。,注：在定理2的条件下，若b是整数，集合ax1 b,a,定理,3,设,m,1,m,2,N,，,(,m,1,m,2,)=1，又设,分别是模,m,1,与,m,2,的简化剩余系，,则,A,=,m,1,y,m,2,x,；,x,X,，,y,Y,是模,m,1,m,2,的简化剩余系。,证明 由第二节定理,3推论可知，,若以,X,与,Y,分别表示,模,m,1,与,m,2,的完全剩余系，使得,X,X,，,Y,Y,，,则,A,=,m,1,y,m,2,x,；,x,X,，,y,Y,是模,m,1,m,2,的完全,剩余系。,因此只需证明,A,中所有与,m,1,m,2,互素的整数的集合,R,即模,m,1,m,2,的简化剩余系是集合,A,。,定理3 设m1,m2N，(m1,m2)=1，,若,m,1,y,m,2,x,R,，则,(,m,1,y,m,2,x,m,1,m,2,)=1，,所以,(,m,1,y,m,2,x,m,1,)=1，,于是,(,m,2,x,m,1,)=1，(,x,m,1,)=1，,x,X,。,同理可得到,y,Y,，因此,m,1,y,m,2,x,A,。,这说明,R,A,。,另一方面，若,m,1,y,m,2,x,A,，则,x,X,，,y,Y,，,即,(,x,m,1,)=1，(,y,m,2,)=1。,由此及,(,m,1,m,2,)=1得到,(,m,2,x,m,1,y,m,1,)=(,m,2,x,m,1,)=1,(,m,2,x,m,1,y,m,2,)=(,m,1,y,m,2,)=1。,因为,m,1,与,m,2,互素，所以,(,m,2,x,m,1,y,m,1,m,2,)=1，,于是,m,2,x,m,1,y,R,。因此,A,R,。,从而,A,=,R,。,若m1y m2xR，则(m1y m2x,m1m2,推论,设,m,n,N,，,(,m,n,)=1，则,(,mn,)=,(,m,),(,n,),。,证 由定理,3知，若,x,y,分别通过,m,n,的简化剩余系，,则,my,nx,通过,mn,的简化剩余系，,即有,my,nx,通过,(,mn,)个整数。,另一方面，,x,nx,通过,(,m,)个整数，,y,my,通过,(,n,)个整数,从而,my,nx,通过,(,m,),(,n,)个整数。,故有,(,mn,)=,(,m,),(,n,),。,注：可以推广到多个两两互质数的情形。,推论 设m,nN，(m,n)=1，则(mn),定理,4 设,n,是正整数，,p,1,p,2,p,k,是它的全部素因数，,证 设,n,的标准分解式是,由定理,3推论得到,对任意的素数,p,，,(,p,),等于数列,1,2,p,中与,p,互素的整数的个数，,从而定理得证。,定理4 设n是正整数，p1,p2,pk是它的全部,注：由定理,4可知，,(,n,)=1的充要条件是,n,=1或2。,考虑有重素因子和没有重素因子的情形。,三、应用举例,注意：有重素因子时，上述不等式中等号不成立！,注：由定理4可知，(n)=1的充要条件是n=1或2,例,1 设整数,n,2,，证明：,即在数列,1,2,n,中，与,n,互素的整数之和是,证 设在,1,2,n,中与,n,互素的,个数是,(,n,)，,a,1,a,2,a,(,n,),，,(,a,i,n,)=1,，,1,a,i,n,1,，,1,i,(,n,)，,则,(,n,a,i,n,)=1，1,n,a,i,n,1,，,1,i,(,n,)，,因此，集合,a,1,a,2,a,(,n,),故,a,1,a,2,a,(,n,),=,(,n,a,1,),(,n,a,2,),(,n,a,(,n,),),，,从而，,2(,a,1,a,2,a,(,n,),),=n,(,n,)，,因此,a,1,a,2,a,(,n,),与集合,n,a,1,n,a,2,n,a,(,n,),是相同的，,例1 设整数n 2，证明：即在数列1,2,例,2 设,n,N,，证明：,1)若,n,是奇数，则,(4,n,)=2,(,n,)；,的充要条件是,n,=2,k,，,k,N,；,的充要条件是,n,=2,k,3,l,，,k,l,N,；,4)若6,n,，则,(,n,),5)若,n,1,与,n,1,都是素数，,n,4，则,(,n,),例2 设nN，证明：1)若n是奇数，则(4n)=,1)若,n,是奇数，则,(4,n,)=2,(,n,)；,(4,n,)=,(2,2,n,),=,(2,2,),(,n,),=,2,(,n,)TH4,1)若n是奇数，则(4n)=2(n)；(4n),的充要条件是,n,=2,k,，,k,N,；,若,n,=2,k,，,若,(,n,)=,设,n,=2,k,n,1,，,由,(,n,)=,(2,k,n,1,),=,(2,k,),(,n,1,),=2,k,1,(,n,1,),所以,n,1,=1，即,n,=2,k,；,的充要条件是n=2k，kN；若n=2k，若(n,的充要条件是,n,=2,k,3,l,，,k,l,N,；,设,n,=2,k,3,l,n,1,，,所以,n,1,=1，即,n,=2,k,3,l,；,若,n,=2,k,3,l,，,则,(,n,)=,(2,k,),(,3,l,),的充要条件是n=2k3l，k,lN；设 n=2k,4)若6,n,，则,(,n,),设,n,=2,k,3,l,n,1,，,则,(,n,)=,(2,k,),(,3,l,),(,n,1,),4)若6n，则(n)设 n=2k3ln1，,5)若,n,1,与,n,1,都是素数，,n,4，则,(,n,),因为,n,4，且,n,1,与,n,1,都是奇素数，,所以,n,是偶数，且,n,1 3.,所以,n,1,与,n,1,都不等于,3，,所以,3,n,，,由结论,4，,也不能被,3整除，,因此,6,n,。,即可得到结论,5。,若,6,n,，则,(,n,),5)若n 1与n 1都是素数，n 4，则(n,例,3 证明：若,m,n,N,，则,(,mn,)=(,m,n,),(,m,n,)；,证：显然,mn,与,m,n,有相同的素因数，,设它们是,p,i,（,1,i,k,），则,由此两式及,mn,=(,m,n,),m,n,即可得证。,例3 证明：若m,nN，则(mn)=(m,n),
展开阅读全文