====Word行业资料分享--可编辑版本--双击可删====源-于-网-络-收-集高中数学竞赛数论剩余类与剩余系(1)定义1设m为正整数，把全体整数按对模m的余数分成m类，相应m个集合记为：K0,K1,⋯,Km-1,其中Kr={qm+r|q∈Z,0≤余数r≤m-1}称为模m的一个剩余类(也叫同余类)。K0,K1,⋯,Km-1为模m的全部剩余类.(2)性质(ⅰ)imiKZ10且Ki∩Kj=φ(i≠j).(ⅱ)每一整数仅在K0,K1,⋯,Km-1一个里.(ⅲ)对任意a、b∈Z，则a、b∈Kra≡b(modm).(1)定义2设K0,K1,⋯,Km-1为模m的全部剩余类，从每个Kr里任取一个ar，得m个数a0,a1,⋯,am-1组成的数组，叫做模m的一个完全剩余系,简称完系.特别地,0,1,2,⋯,m-1叫做模m的最小非负完全剩余系.下述数组叫做模m的绝对最小完全剩余系:当m为奇数时,21,,1,0,1,,121,21mmm;当m为偶数时,12,,1,0,1,,12,2mmm或2,,1,0,1,,12mm.(2)性质(ⅰ)m个整数构成模m的一完全剩余系两两对模m不同余.(ⅱ)若(a,m)=1，则x与ax+b同时遍历模m的完全剩余系.证明:即证a0,a1,⋯,am-1与aa0+b,aa1+b,⋯,aam-1+b同为模m的完全剩余系,因a0,a1,⋯,am-1为模m的完系时,若aai+b≡aaj+b(modm),则ai≡aj(modm),矛盾!反之,当aa0+b,aa1+b,⋯,aam-1+b为模m的完系时,若ai≡aj(modm),则有====Word行业资料分享--可编辑版本--双击可删====源-于-网-络-收-集aai+b≡aaj+b(modm),也矛盾!(ⅲ)设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y//(modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾!(1)定义3如果剩余类Kr里的每一个数都与m互质，则Kr叫与m互质的剩余类.在与模m互质的全部剩余类中，从每一类中任取一个数所做成的数组，叫做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.(2)性质(ⅰ)Kr与模m互质Kr中有一个数与m互质；证明:设a∈Kr,(m,a)=1,则对任意b∈Kr,因a≡b≡r(modm),所以,(m,a)=(m,r)=(m,b)=1,即Kr与模m互质.(ⅱ)与模m互质的剩余类的个数等于)m(,即模m的一个既约剩余系由)m(个整数组成()m(为欧拉函数);(ⅲ)若(a,m)=1,则x与ax同时遍历模m的既约剩余系.证明:因(a,m)=1,(x,m)=1,所以,(ax,m)=1.若ax1≡ax2(modm),则有x1≡x2(modm),矛盾!(ⅳ)若a1,a2,⋯,aφ(m)是)m(个与m互质的整数,并且两两对模m不同====Word行业资料分享--可编辑版本--双击可删====源-于-网-络-收-集余,则a1,a2,⋯,aφ(m)是模m的一个既约剩余系.证明:因a1,a2,⋯,aφ(m)是)m(个与m互质的整数,并且两两对模m不同余,所以,a1,a2,⋯,aφ(m)属于)m(个剩余类,且每个剩余类都与m互质,故a1,a2,⋯,aφ(m)是模m的一个既约剩余系.(ⅴ)设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m2x+m1y历遍模m1m2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y分别历遍模m1,m2的完系时,m2x+m1y历遍模m1m2的完系.由(m1,x)=(m2,y)=1,(m1,m2)=1得(m2x,m1)=(m1y,m2)=1,所以,(m2x+m1y,m1)=1,(m2x+m1y,m2)=1,故(m2x+m1y,m1m2)=1.反之若(m2x+m1y,m1m2)=1,则(m2x+m1y,m1)=(m2x+m1y,m2)=1,所以,(m2x,m1)=(m1y,m2)=1,因(m1,m2)=1,所以,(m1,x)=(m2,y)=1.证毕.推论1若m1,m2是两个互质的正整数,则)()()(2121mmmm.证明:因当x,y分别历遍模m1,m2的既约剩余系时,m2x+m1y也历遍模m1m2的既约剩余系,即m2x+m1y取遍)(21mm个整数,又x取遍)(1m个整数,y取遍)(2m个整数,所以,m2x+m1y取遍)()(21mm个整数,故)()()(2121mmmm.推论2设整数n的标准分解式为kkpppn2121(kpp,,1为互异素数,*1,,Nk),则有)11()11)(11()(21kpppnn.====Word行业资料分享--可编辑版本--双击可删====源-于-网-络-收-集证明:由推论1得)()()()(2121kkpppn,而1)(ppp,(即从1到p这p个数中,减去能被p整除的数的个数),所以,)())(()(11221112211kkkkppppppn)11()11)(11(21kpppn.4.欧拉(Euler)与费尔马(Fermat)定理欧拉(Euler)定理设m是大于1的整数,(a,m)=1,则)(mod1)(mam.证明:设r1,r2,⋯,r)(m是模m的既约剩余系,则由性...
