资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.4,剩余系和欧拉函数,人教,B,版数学选修,4-6,初等数论初步,2.4 剩余系和欧拉函数人教B版数学选修4-6初等数论初,定义,1,对于正整数,m,，则,m,个整数,0,1,m-1,中与,m,互素的整数个数记做,(,m,),也就是,Eule,r,函数,例如，容易验证,(2)=1,，,(4)=2,，,(7)=6,定义,2,设,R,是模,m,的一个剩余类，若有,a,R,，使得,(,a,m,)=1,，则称,R,是模,m,的一个简化剩余类。,定义,3,对于正整数,m,，从模,m,的每个简化剩余类中各取一个数,x,i,，构成一个集合,x,1,x,2,x,(,m,),，称为模,m,的一个简化剩余系,模,m,的一个简化剩余系的元素个数是,(,m,),定义1 对于正整数m，则m个整数0,1,m-1中与m互素,例,1,设,m,是一个正整数,则,0,1,m-1,中与,m,互素的整数全体组成模,m,的一个简化剩余系叫做模,m,的最小非负简化剩余系,1,m-1,m,中与,m,互素的整数全体组成模,m,的一个简化剩余系叫做模,m,的最小正简化剩余系,-m+1,-1,0,中与,m,互素的整数全体组成模,m,的一个简化剩余系叫做模,m,的最大非正简化剩余系,-m,-m+1,1,中与,m,互素的整数全体组成模,m,的一个简化剩余系叫做模,m,的最大负简化剩余系,例1设m是一个正整数,则,当,m,分别为偶数时,-m/2,-(m-2)/2,-1,0,1,(m-2)/2,或,-(m-2)/2,-1,0,1,(m-2)/2,m/2,中与,m,互素的整数全体组成模,m,的一个简化剩余系,当,m,是奇数时,-(m-1)/2,-1,0,1,(m-1)/2,中与是,m,互素的整数全体组成模,m,的一个简化剩余系,上述两个简化剩余系统称为模,m,的一个绝对值最小简化剩余系,当m分别为偶数时,定理,1,若,a,1,a,2,a,(m),是,(m),个与,m,互素的整数,并且两两对模,m,不同余,则,a,1,a,2,a,(m),是模,m,的一简化剩余系,定理,2,若,(a,m)=1,r,l,r,2,r,(m),是模,m,的一简化剩余系,则,ar,l,ar,2,ar,(m),也是模,m,的一简化剩余系,定理1若a1,a2,a(m)是(m)个与m互素的整数,证明,由定理,1,只需证明,ar,l,ar,2,ar,(m),是模,m,两两互不同余,且都与,m,互素即可,.,先证两两互不相同,:,假设,ar,i,ar,j,(mod m),其中,1i,j,(m).,由于,(a,m)=1,有,r,i,r,j,(mod m),这与,r,l,r,2,r,(m),是模,m,的一简化剩余系矛盾,故,ar,i,ar,j,(mod m),即,:ar,l,ar,2,ar,(m),中模,m,两两互不同余,证明 由定理1只需证明arl,ar2,ar(m)是,再证,(a,m)=1,(r,m)=1,(ar,m)=1,例,2,已知,1,7,11,13,17,19,23,29,是模,30,的简化剩余系,(7,30)=1 ,构造一个简化剩余系,再证(a,m)=1,(r,m)=1,(ar,m)=1,定理,3,设,m,是一个正整数,(a,m)=1,则存在,a,使,得,a a,1(mod m),证明,因为,(a,m)=1,故存在唯一的整数,s,t,满足,sa+tm=1,sa,1(mod m),取,s=a,成立,这里,a,也叫做,a,模,m,的乘法逆元,定理 3 设m是一个正整数,(a,m)=1,则存在a,定理,4,设,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,的简化剩余系。,定理,5,设,m,n,N,，,(,m,n,)=1,，则,(,mn,)=,(,m,),(,n,),证,由定理,4,直接得到,定理 4 设m1,m2N，(m1,m2)=1，又设,定理,6,设,n,的标准分解式是,n,=,是它的全部素因数，则,(,n,)=,证明,:,由定理,5,有,(,n,)=,对任意的素数,p,，,(,p,),等于数列,1,2,p,中与,p,（也就是与,p,）互素的整数的个数，因此,(,p,)=,p,(1),定理6设n的标准分解式是n=是它的全部素因,又,n,=,和,(1),式结合起来就得到结论,推论,设,pq,是不同的素数,则,(,pq,),=,(,p,),(,q,)=(p-1)(q-1),下面进一步考察欧拉函数的性质,又n=,和(1)式结合起来就得到结论,定理,7,设,n,是一个正整数 则,证明,:,设,C=1,n,按照与,n,的最大公因素分类,对,d|n,记,C,d,=m|1m n,(m,n)=d,因为,(m,n)=d iff,(m/d,n/d)=1,所以,C,d,中的元素,m,的形式,C,d,=m=dk|1k n/d,(k,n/d)=1,故,C,d,的元素个数为,(,n/d,),因为每个整数属于且仅属于一个类,C,d,因此,#C=,即,又当,d,遍历,n,的正因素,时,n/d,也遍历,n,的所有正因素,定理7 设n是一个正整数 则,例,3,设整数,n=50,利用定理,8,对其进行分类,解,因为,n,的因素为,1,2,5,10,15,25,50,则,C,1,=1,3,7,9,11,13,17,19,23,27,29,31,33,37,39,41,43,47,49,C,2,=2,4,6,8,12,14,16,18,22,24,26,28,32,34,36,3842,44,46,48,.,例3 设整数n=50,利用定理8 对其进行分类,The End,The End,
展开阅读全文