资源描述：
《第三节 简化剩余系》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、初等数论第二章同余第三节简化剩余系在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。定义1设R是模m的一个剩余类，若有aÎR，使得(a,m)=1，则称R是模m的一个简化剩余类。显然，若R是模的简化剩余类，则R中的每个整数都与m互素。例如，模4的简化剩余类有两个：R1(4)={L,-7,-3,1,5,9,L}，R3(4)={L,-5,-1,3,7,11,L}。定义2对于正整数k，令函数j(k)的值等于模k的所有简化剩余类的个数，称j(k)为Euler函数，或Euler—j函数。例如，容易验证j(2)=1，j(3)=2，j(4)=2，
2、j(7)=6。显然，j(m)就是在m的一个完全剩余系中与m互素的整数的个数。定义3对于正整数m，从模m的每个简化剩余类中各取一个数xi，构成一个集合{x1,x2,L,xj(m)}，称为模m的一个简化剩余系（或简称为简化系）。显然，由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,-5,-3,-1}是模8的简化剩余系，集合{1,3,5,7}也是模8的简化剩余系，通常称最小非负简化剩余系。定理1整数集合A是模m的简化剩余系的充要条件是(ⅰ)A中含有j(m)个整数；(ⅱ)A中的任何两个整数对模m不同余；(ⅲ)A中的每个整数都与m互素。证明留作习题。定理2设a是整数，
3、(a,m)=1，B={x1,x2,L,xj(m)}是模m的简化剩余系，则集合A={ax1,ax2,L,axj(m)}也是模m的简化剩余系。证明显然，集合A中有j(m)个整数。其次，由于(a,m)=1，所以，对于任意的xi（1£i£j(m)），xiÎB，有(axi,m)=(xi,m)=1。因此，A中的每一个数都与m互素。最后，我们指出，A中的任何两个不同的整数对模m不同余。事实上，若有x¢,x¢¢ÎB，使得ax¢ºax¢¢(modm)，初等数论第二章同余第三节简化剩余系在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。定义1设R是模
4、m的一个剩余类，若有aÎR，使得(a,m)=1，则称R是模m的一个简化剩余类。显然，若R是模的简化剩余类，则R中的每个整数都与m互素。例如，模4的简化剩余类有两个：R1(4)={L,-7,-3,1,5,9,L}，R3(4)={L,-5,-1,3,7,11,L}。定义2对于正整数k，令函数j(k)的值等于模k的所有简化剩余类的个数，称j(k)为Euler函数，或Euler—j函数。例如，容易验证j(2)=1，j(3)=2，j(4)=2，j(7)=6。显然，j(m)就是在m的一个完全剩余系中与m互素的整数的个数。定义3对于正整数m，从模m的每个简化剩余类中各取一个数xi，构成一个
5、集合{x1,x2,L,xj(m)}，称为模m的一个简化剩余系（或简称为简化系）。显然，由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,-5,-3,-1}是模8的简化剩余系，集合{1,3,5,7}也是模8的简化剩余系，通常称最小非负简化剩余系。定理1整数集合A是模m的简化剩余系的充要条件是(ⅰ)A中含有j(m)个整数；(ⅱ)A中的任何两个整数对模m不同余；(ⅲ)A中的每个整数都与m互素。证明留作习题。定理2设a是整数，(a,m)=1，B={x1,x2,L,xj(m)}是模m的简化剩余系，则集合A={ax1,ax2,L,axj(m)}也是模m的简化剩余系。证明显
6、然，集合A中有j(m)个整数。其次，由于(a,m)=1，所以，对于任意的xi（1£i£j(m)），xiÎB，有(axi,m)=(xi,m)=1。因此，A中的每一个数都与m互素。最后，我们指出，A中的任何两个不同的整数对模m不同余。事实上，若有x¢,x¢¢ÎB，使得ax¢ºax¢¢(modm)，那么，因为(a,m)=1，所以x¢ºx¢¢(modm)，于是x¢=x¢¢。由以上结论及定理1可知集合A是模m的一个简化系。证毕。注：在定理2的条件下，若b是整数，集合{ax1+b,ax2+b,,L,axj(m)+b}不一定是模m的简化剩余系。例如，取m=4，a=1，b=1，以及模4的简化
7、剩余系{1,3}。定理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是集合A。显然，AÍA’。若m1y+m2xÎR，则(m1y+m2x,m1m2)=1，所以(m1y+m2x,m1)=1，于是
