《剩余系和欧拉函数》课件1优质公开课人教B版选修46.ppt

1、2.4 剩余系和欧拉函数剩余系和欧拉函数人教B版数学选修4-6初等数论初步定义定义1 对于正整数对于正整数m，则，则m个整数个整数0,1,m-1中与中与m互素的整数个数记做互素的整数个数记做(m),也就是也就是Euler函数函数 例如，容易验证例如，容易验证(2)=1，(4)=2，(7)=6 定义定义2设设R是模是模m的一个剩余类，若有的一个剩余类，若有a R，使得，使得(a,m)=1，则称，则称R是模是模m的一个简化剩余类。的一个简化剩余类。定义定义3 对于正整数对于正整数m，从模，从模m的每个简化剩余类中的每个简化剩余类中各取一个数各取一个数xi，构成一个集合，构成一个集合x1,x2,x(

2、m)，称为模称为模m的一个简化剩余系的一个简化剩余系模模m的一个简化剩余系的元素个数是的一个简化剩余系的元素个数是(m)例例1设设m是一个正整数是一个正整数,则则0,1,m-1中与中与m互素的整数全体组成模互素的整数全体组成模m的一个简化剩的一个简化剩余系叫做模余系叫做模m的最小非负简化剩余系的最小非负简化剩余系 1,m-1,m中与中与m互素的整数全体组成模互素的整数全体组成模m的一个简化剩的一个简化剩余系叫做模余系叫做模m的最小正简化剩余系的最小正简化剩余系-m+1,-1,0中与中与m互素的整数全体组成模互素的整数全体组成模m的一个简化的一个简化剩余系叫做模剩余系叫做模m的最大非正简化剩余系

3、的最大非正简化剩余系-m,-m+1,1中与中与m互素的整数全体组成模互素的整数全体组成模m的一个简化的一个简化剩余系叫做模剩余系叫做模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的一个简化剩余系的一个简化剩余系上述两个简化剩余系统称为模上述两个简化

4、剩余系统称为模m的一个绝对值最小简化的一个绝对值最小简化剩余系剩余系定理定理1若若a1,a2,a(m)是是(m)个与个与m互素的互素的整数整数,并且两两对模并且两两对模m不同余不同余,则则a1,a2,a(m)是模是模m的一简化剩余系的一简化剩余系定理定理2若若(a,m)=1,rl,r2,r(m)是模是模 m的一的一简化剩余系简化剩余系,则则arl,ar2,ar (m)也是模也是模m的一简化剩余系的一简化剩余系证明证明 由定理由定理1只需证明只需证明arl,ar2,ar (m)是是模模m两两互不同余两两互不同余,且都与且都与m互素即可互素即可.先证两两互不相同先证两两互不相同:假设假设ari a

5、rj(mod m),其中其中1i,j (m).由于由于(a,m)=1,有有ri rj(mod m),这与这与rl,r2,r(m)是模是模 m的一简化剩余系矛盾的一简化剩余系矛盾,故故ariarj(mod m),即即:arl,ar2,ar (m)中模中模m两两互不同两两互不同余余再证再证(a,m)=1,(r,m)=1,(ar,m)=1例例2 已知已知1,7,11,13,17,19,23,29是模是模30的简的简化剩余系化剩余系(7,30)=1 ,构造一个简化剩余构造一个简化剩余系系定理定理 3 设设m是一个正整数是一个正整数,(a,m)=1,则存在则存在a,使使得得a a 1(mod m)证明证

6、明,因为因为,(a,m)=1 故存在唯一的整数故存在唯一的整数s,t 满足满足sa+tm=1 sa 1(mod m),取取s=a 成立成立这里这里 a 也叫做也叫做a模模m的乘法逆元的乘法逆元 定理定理 4 设设m1,m2 N，(m1,m2)=1，又设，又设 分别是模分别是模m1与与m2的简化剩余系，则的简化剩余系，则 A=m1y m2x；x X，y Y 是模是模m1m2的简化剩余系。的简化剩余系。定理定理5设设m,n N，(m,n)=1，则，则 (mn)=(m)(n)证,由定理由定理4直接得到直接得到1 12 21 12 21 12 2(m m)(m m)X X=x x,x x,x x 与与

7、Y Y=y y,y y,y y 定理定理6设设n的标准分解式是的标准分解式是n=是它的全是它的全部素因数，则部素因数，则(n)=证明证明:由定理由定理5 有有(n)=对任意的素数对任意的素数p，(p)等于数列等于数列1,2,p 中中与与p（也就是与（也就是与p）互素的整数的个数，因）互素的整数的个数，因此此(p)=p (1)p|np|n12k12k111111111-1-L 1-=n1-1-1-L 1-=n1-ppppppppn()()()()n()()()()i ik ki ii=1i=1p pi ik ki ii=1i=1(p)(p)-1-1p1p1=p-p=p1-=p-p=p1-pppp

8、()()又又n=,和和(1)式结合起来就得到结论式结合起来就得到结论推论推论 设设pq是不同的素数是不同的素数,则则(pq)=(p)(q)=(p-1)(q-1)下面进一步考察欧拉函数的性质下面进一步考察欧拉函数的性质i ik ki ii=1i=1p p定理定理7 设设n是一个正整数是一个正整数 则则 证明证明:设设C=1,n,按照与按照与n的最大公因素分类的最大公因素分类,对对d|n记记 Cd=m|1m n,(m,n)=d,因为因为,(m,n)=d iff,(m/d,n/d)=1,所以所以Cd中的元素中的元素m的形式的形式Cd=m=dk|1k n/d,(k,n/d)=1,故故Cd的元素个数为的

9、元素个数为(n/d),因因为每个整数属于且仅属于一个类为每个整数属于且仅属于一个类Cd因此因此,#C=,即即 ,又当又当d遍历遍历n的正因素的正因素时时,n/d也遍历也遍历n的所有正因素的所有正因素d|nd|n(d)=n(d)=nd dd d|n n#C Cd|nd|nn n()=n()=nd d例例3 设整数设整数n=50,利用定理利用定理8 对其进行分类对其进行分类解解,因为因为n的因素为的因素为1,2,5,10,15,25,50则则 C1=1,3,7,9,11,13,17,19,23,27,29,31,33,37,39,41,43,47,49C2=2,4,6,8,12,14,16,18,22,24,26,28,32,34,36,3842,44,46,48.The End