高中数学竞赛数论

高中数学竞赛 数论

剩余类与剩余系

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 为奇数时,2

1

,,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/≡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如果剩余类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不同余,

所以,a 1,a 2,…,a φ(m)属于)m (ϕ个剩余类,且每个剩余类都与m 互质,故a 1,a 2,…,a φ

(m)

是模m 的一个既约剩余系.

(ⅴ)设m 1,m 2是两个互质的正整数,而x,y 分别历遍模m 1,m 2的既约剩余

系,则m 2x+m 1y 历遍模m 1m 2的既约剩余系.

证明:显然,既约剩余系是完系中所有与模互质的整数做成的.因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 整除的数的个数),所以,

)())(()(11221112

2

1

1

------=k

k

k k p p p p p p n ααααααϕΛ

)1

1()11)(11(21k

p p p n ---

=Λ.