文档介绍：第三节简化剩余系在模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,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是整数,(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),那么,因为(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的简化剩余系{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,于是(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。综合以上