资源描述:
《高中数学竞赛——数论》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、高中数学竞赛数论剩余类与剩余系1.剩余类的定义与性质(1)定义1设m为正整数,把全体整数按对模m的余数分成m类,相应m个集合记为:K0,K1,…,Km-1,其中Kr={qm+r
2、q∈Z,0≤余数r≤m-1}称为模m的一个剩余类(也叫同余类)。K0,K1,…,Km-1为模m的全部剩余类.(2)性质(ⅰ)且Ki∩Kj=φ(i≠j).(ⅱ)每一整数仅在K0,K1,…,Km-1一个里.(ⅲ)对任意a、b∈Z,则a、b∈Kra≡b(modm).2.剩余系的定义与性质(1)定义2设K0,K1,…,Km-1为
3、模m的全部剩余类,从每个Kr里任取一个ar,得m个数a0,a1,…,am-1组成的数组,叫做模m的一个完全剩余系,简称完系.特别地,0,1,2,…,m-1叫做模m的最小非负完全剩余系.下述数组叫做模m的绝对最小完全剩余系:当m为奇数时,;当m为偶数时,或.(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,…
4、,am-1为模m的完系时,若aai+b≡aaj+b(modm),则ai≡aj(modm),矛盾!反之,当aa0+b,aa1+b,…,aam-1+b为模m的完系时,若ai≡aj(modm),则有aai+b≡aaj+b(modm),也矛盾!14(ⅲ)设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.假定m2x/+m1y/≡m2x//+m1y//(modm1m2),其
5、中x/,x//是x经历的完系中的数,而y/,y//是y经历的完系中的数.因(m1,m2)=1,所以,m2x/≡m2x//(modm1),m1y/≡m1y//(modm2),从而x/≡x//(modm1),y/≡y//(modm2),矛盾!3.既约剩余系的定义与性质(1)定义3如果剩余类Kr里的每一个数都与m互质,则Kr叫与m互质的剩余类.在与模m互质的全部剩余类中,从每一类中任取一个数所做成的数组,叫做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.(2
6、)性质(ⅰ)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的一个既约剩余系由个整数组成(为欧拉函数);(ⅲ)若(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)
7、是个与m互质的整数,并且两两对模m不同余,则a1,a2,…,aφ(m)是模m的一个既约剩余系.14证明:因a1,a2,…,aφ(m)是个与m互质的整数,并且两两对模m不同余,所以,a1,a2,…,aφ(m)属于个剩余类,且每个剩余类都与m互质,故a1,a2,…,aφ(m)是模m的一个既约剩余系.(ⅴ)设m1,m2是两个互质的正整数,而x,y分别历遍模m1,m2的既约剩余系,则m2x+m1y历遍模m1m2的既约剩余系.证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因x,y分别历遍模m1,
8、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是两个互质的正整数,则.证
9、明:因当x,y分别历遍模m1,m2的既约剩余系时,m2x+m1y也历遍模m1m2的既约剩余系,即m2x+m1y取遍个整数,又x取遍个整数,y取遍个整数,所以,m2x+m1y取遍个整数,故.推论2设整数n的标准分解式为(为互异素数,),则有.证明:由推论1得,而,(即从1到这个数中,减去能被整除的数的个数),所以,.144.欧拉(Euler)与费尔马(Fermat)定理欧拉(Euler)定理设m是大于1的整数,(a,m)=1,则.证明:设r1,r2,…,r是模m的既约剩余系,则由性质3知ar1,a