高中数学竞赛  数论
剩余类与剩余系
1.剩余类的定义与性质
(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)性质(ⅰ)且Ki∩Kj=φ(i≠j).
(ⅱ)每一整数仅在K0,K1,…,Km-1一个里.
(ⅲ)对任意a、b∈Z，则a、b∈Kra≡b(modm).
2.剩余系的定义与性质
(1)定义2 设K0,K1,…,Km-1为模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,…,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),也矛盾!
(ⅲ)设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),矛盾!
3.既约剩余系的定义与性质
    (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的一个既约剩余系由个整数组成(为欧拉函数);
(ⅲ)若(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不同余,则a1,a2,…,aφ(m)是模m的一个既约剩余系.
证明:因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,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是两个互质的正整数,则.
数学数组的定义是什么
证明:因当x,y分别历遍模m1,m2的既约剩余系时,m2x+m1y也历遍模m1m2的既约剩余系,即m2x+m1y取遍个整数,又x取遍个整数,y取遍
个整数,所以, m2x+m1y取遍个整数,故.
推论2 设整数n的标准分解式为(为互异素数,
),则有.
证明:由推论1得,而,
(即从1到这个数中,减去能被整除的数的个数),所以,
.
4.欧拉(Euler)与费尔马(Fermat)定理
欧拉(Euler)定理 设m是大于1的整数,(a,m)=1,则.
证明:设r1,r2,…,r是模m的既约剩余系,则由性质3知ar1,ar2,…,ar也是模m的既约剩余系,所以, ar1ar2…ar≡r1r2…r(modm),即
,因(,m)=1,所以,.
推论(Fermat定理) 设p为素数,则对任意整数a都有.
证明:若(a, p)=1,由及Euler定理得即
;若(a, p)≠1,则p|a,显然有.
例1设m>0,证明必有一个仅由0或1构成的自然数a是m的倍数.
证明:考虑数字全为1的数:因1,11,111,1111,…中必有两个在modm的同一剩余类中,它们的差即为所求的a.
例2证明从任意m个整数a1,a2,…,am中,必可选出若干个数,它们的和
(包括只一个加数)能被m整除.
证明:考虑m个数a1,a1+a2,a1+a2+a3,…,a1+a2+…+am,如果其中有一个数能被m整除,则结论成立,否则,必有两个数属于modm的同一剩余类,这两个数的差即满足要求.
例3设f(x)=5x+2=f1(x), fn+1(x)=f[fn(x)].求证:对任意正整数n,存在正整数m,使得2011|fn(m).
证明:因f2(x)=f[f(x)]=5(5x+2)+2=52x+5×2+2,