高中数学竞赛 数论
剩余类与剩余系
1.剩余类的定义与性质
(1)定义1 设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r ≤m-1}称为模m 的一个剩余类(也叫同余类)。K 0,K 1,…,K m-1为模m 的全部剩余类.
(2)性质(ⅰ)i m i K Z 1
0-≤≤=Y 且K i ∩K j =φ(i ≠j). (ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.
(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a ≡b(modm).
2.剩余系的定义与性质
(1)定义2 设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系,简称完系. 特别地,0,1,2,…,m -1叫做模m 的最小非负完全剩余系.下述数组叫做模m 的绝对最小完全剩余系:当m 为奇数时,21,,1,0,1,,121,21--+----
m m m ΛΛ;当m 为偶数时,12
,,1,0,1,,12,2--+--m m m ΛΛ或2,,1,0,1,,12m m ΛΛ-+-. (2)性质(ⅰ)m 个整数构成模m 的一完全剩余系⇔两两对模m 不同余. (ⅱ)若(a,m)=1，则x 与ax+b 同时遍历模m 的完全剩余系.
证明:即证a 0,a 1,…,a m-1与aa 0+b, aa 1+b,…,aa m-1+b 同为模m 的完全剩余系, 因a 0,a 1,…,a m-1为模m 的完系时,若aa i +b ≡aa j +b(modm),则a i ≡a j (modm), 矛盾!反之,当aa 0+b, aa 1+b,…,aa m-1+b 为模m 的完系时,若a i ≡a j (modm),则有 aa i +b ≡aa j +b(modm),也矛盾!
(ⅲ)设m1,m2是两个互质的正整数,而x,y分别遍历模m1,m2的完系,则m2x+m1y历遍模m1m2的完系.
证明:因x,y分别历遍m1,m2个整数,所以,m2x+m1y历遍m1m2个整数.
假定m2x/+m1y/≡m2x1m2(m1,m2)=1,所以,m2x/≡m2x约剩余系的定义与性质
(1)定义3如果剩余类K r里的每一个数都与m互质，则K r叫与m互质的剩余类.在与模m互质的全部剩余类中，从每一类中任取一个数所做成的数组，叫做模m的一个既约(简化)剩余系.如:模5的简系1,2,3,4;模12的简系1,5,7,11.
(2)性质(ⅰ)K r与模m互质⇔K r中有一个数与m互质；
证明:设a∈K r,(m,a)=1,则对任意b∈K r,因a≡b≡r(modm),所以,(m,a)=(m,r)= (m,b)=1,即K r与模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不同余,则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 分别历遍模m 1,m 2的完系时,m 2x+m 1y 历遍模m 1m 2的完系.由(m 1,x )=(m 2,y )=1, (m 1,m 2)=1得(m 2x,m 1)=(m 1y,m 2)=1,所以,(m 2x+m 1y,m 1)=1,(m 2x+m 1y,m 2)=1,故 (m 2x+m 1y, m 1m 2)=1.反之若(m 2x+m 1y, m 1m 2)=1,则(m 2x+m 1y,m 1)=(m 2x+m 1y,m 2) =1,所以,(m 2x,m 1)=(m 1y,m 2)=1,因(m 1,m 2)=1,所以,(m 1,x )=(m 2,y )=1.证毕.
推论1若m 1,m 2是两个互质的正整数,则)()()(2121m m m m ϕϕϕ=.
证明:因当x,y 分别历遍模m 1,m 2的既约剩余系时,m 2x+m 1y 也历遍模m 1m 2的既约剩余系,即m 2x+m 1y 取遍)(21m m ϕ个整数,又x 取遍)(1m ϕ个整数,y 取遍 )(2m ϕ个整数,所以, m 2x+m 1y 取遍)()(21m m ϕϕ个整数,故)()()(2121m m m m ϕϕϕ=.
推论2 设整数n 的标准分解式为k k
p p p n αααΛ2121=(k p p ,,1Λ为互异素数, *1,,N k ∈ααΛ),则有)11()11)(11()(21k
p p p n n ---=Λϕ. 证明:由推论1得)()()()(2121k k p p p n αααϕϕϕϕΛ=,而1)(--=αααϕp p p ,
(即从1到αp 这αp 个数中,减去能被p 整除的数的个数),所以,
)())(()(11221112211------=k
k k k p p p p p p n ααααααϕΛ )11()11)(11(21k
p p p n ---=Λ. 4.欧拉(Euler)与费尔马(Fermat)定理
欧拉(Euler)定理 设m 是大于1的整数,(a ,m)=1,则)(m od 1)(m a m ≡ϕ. 证明:设r 1,r 2,…,r )(m ϕ是模m 的既约剩余系,则由性质3知a r 1,a r 2,…,a r )(m ϕ也是模m 的既约剩余系,所以, a r 1a r 2…a r )(m ϕ≡r 1r 2…r )(m ϕ(modm),即≡)(21)(m m r r r a ϕϕΛ )(21m r r r ϕΛ,因()(21m r r r ϕΛ,m)=1,所以,)(m od 1)(m a m ≡ϕ.
推论(Fermat 定理) 设p 为素数,则对任意整数a 都有)(m od p a a p ≡.
