简化剩余系与欧拉函数.ppt

《简化剩余系与欧拉函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§3.3简化剩余系与欧拉函数一、基本概念定义1设R是模m的一个剩余类，若有aR，使得(a,m)=1，则称R是模m的一个简化剩余类。即与模m互质的剩余类。注：若R是模的简化剩余类，则R中的数都与m互素。例如，模4的简化剩余类有两个：R1(4)={,7,3,1,5,9,}，R3(4)={,5,1,3,7,11,}。定义2对于正整数k，令函数(k)的值等于模k的所有简化剩余类的个数，称(k)为Euler函数。容易验证：(2)=1，(3)=2，(4)=2，(7)=6。注：(m)就是在m的一个完全剩余系中与m互素的整数的个数，且定义3对于正整数m，从模m的每个简化剩

2、余类中各取一个数xi，构成一个集合{x1,x2,,x(m)}，称为模m的一个简化剩余系（或简称为简化系）。注：由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,5,3,1}是模8的简化剩余系；集合{1,3,5,7}也是模8的简化剩余系.集合{1,3,5,7}称为最小非负简化剩余系。二、主要性质定理1整数集合A是模m的简化剩余系的充要条件是：①A中含有(m)个整数；②A中的任何两个整数对模m不同余；③A中的每个整数都与m互素。说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件2；由定义1易知满足条件3；由定义3易知满足条件1。定理2设a是整数，(

3、a,m)=1，B={x1,x2,,x(m)}是模m的简化剩余系，则集合A={ax1,ax2,,ax(m)}也是模m的简化剩余系。证明显然，集合A中有(m)个整数。由于(a,m)=1，对于任意的xi（1i(m)），xiB，有(axi,m)=(xi,m)=1。故A中的每一个数都与m互素。而且，A中的任何两个不同的整数对模m不同余。因为，若有x,xB，使得axax(modm)，那么，xx(modm)，于是x=x。由以上结论及定理1可知集合A是模m的一个简化系。注：在定理2的条件下，若b是整数，集合{ax1b,ax2b,,,ax(m)b}

4、不一定是模m的简化剩余系。例如，取m=4，a=1，b=1，以及模4的简化剩余系{1,3}。但｛2，4｝不是模4的简化剩余系。定理3设m1,m2N，(m1,m2)=1，又设分别是模m1与m2的简化剩余系，则A={m1ym2x；xX，yY}是模m1m2的简化剩余系。证明由第二节定理3推论可知，若以X与Y分别表示模m1与m2的完全剩余系，使得XX，YY，则A={m1ym2x；xX，yY}是模m1m2的完全剩余系。因此只需证明A中所有与m1m2互素的整数的集合R即模m1m2的简化剩余系是集合A。若m1ym2xR，则(m1ym2x,m1m2)=1，所以(m1

5、ym2x,m1)=1，于是(m2x,m1)=1，(x,m1)=1，xX。同理可得到yY，因此m1ym2xA。这说明RA。另一方面，若m1ym2xA，则xX，yY，即(x,m1)=1，(y,m2)=1。由此及(m1,m2)=1得到(m2xm1y,m1)=(m2x,m1)=1(m2xm1y,m2)=(m1y,m2)=1。因为m1与m2互素，所以(m2xm1y,m1m2)=1，于是m2xm1yR。因此AR。从而A=R。推论设m,nN，(m,n)=1，则(mn)=(m)(n)。证由定理3知，若x,y分别通过m,n的简化剩余系，则mynx通过mn的简化剩余

6、系，即有mynx通过(mn)个整数。另一方面，x〔nx〕通过(m)个整数，y〔my〕通过(n)个整数,从而mynx通过(m)(n)个整数。故有(mn)=(m)(n)。注：可以推广到多个两两互质数的情形。定理4设n是正整数，p1,p2,,pk是它的全部素因数，证设n的标准分解式是由定理3推论得到对任意的素数p，(p)等于数列1,2,,p中与p互素的整数的个数，从而定理得证。注：由定理4可知，(n)=1的充要条件是n=1或2。考虑有重素因子和没有重素因子的情形。三、应用举例注意：有重素因子时，上述不等式中等号不成立！例1设整数n2，证明：即在数列1,2,

7、,n中，与n互素的整数之和是证设在1,2,,n中与n互素的个数是(n)，a1,a2,,a(n)，(ai,n)=1，1ain1，1i(n)，则(nai,n)=1，1nain1，1i(n)，因此，集合{a1,a2,,a(n)}故a1a2a(n)=(na1)(na2)(na(n))，从而，2(a1a2a(n))=n(n)，因此a1a2a(n)与集合{n