(5) 第三章 同余、剩余类、完全剩余系

一、同餘，剩餘類與剩餘系(a ) 同餘的性質：(1) a ≡b (mod m )，c ≡d (mod m )，則 a ±c ≡b ±d (mod m ) 且ac ≡bd (mod m )。

(2) a ≡b (mod m )，c ∈N ，則 ac ≡bc (mod cm )。

(3) a ≡b (mod m )，n ∈N 且 m n ，則 a ≡b (mod n )。

(4) 若a ≡b (mod m )，則 (a ，m )＝(b ，m )。

(5) 整數a ，b ，則 ab ≡1 (mod m ) iff (a ，m )＝1。

(b ) 剩餘類：m 為正整數，將全體整數按照對模m 的餘數進行分類，餘數為r (10-≤≤m r ) 的所有整數歸為一類，記為K r (r =0,1,..,m -1)，每一類K r 均稱為模m 的剩餘類 (同餘類)。

剩餘類K r 是數集K r ={mq +r m 是模，r 是餘數，q ∈Z }＝{a Z a ∈且)(mod m r a ≡}， 它是一個以m 為公差的(雙邊無窮)等差數集。

並具有如下的性質：(1) 1210-⋃⋃⋃⋃=m K K K K Z 且∅=⋂j i K K (j i ≠)。

(2) 對於任意的Z n ∈，有唯一的r 0使0r K n ∈。

(3) 對於任意的a 、b Z ∈，a 、b r K ∈ ⇔ )(mod m b a ≡(c ) 完全剩餘系：設K 0，K 1，…，K m-1是模m 的全部剩餘類，從每個K r 中取任取一個數a r ，這m 個數a 0，a 1，…，a m-1組成的一個數組稱為模m 的一個完全剩餘系。

(d ) 簡化剩餘系：如果一個模m 的剩餘類K r 中任一數都與m 互質，就稱K r 是一個與模m 互質的剩餘類。

在與模m 互質的每個剩餘類中，任取一個數 (共)(m ϕ個) 所組成的數組，稱為模m 的一個簡化剩餘系。

(二) 高觀點：同餘類環(ring)1.等價關係：給集合S中一個關係”~”。

数学奥赛辅导 第三讲同余知识、方法、技能同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本讲介绍同余的基本概念，剩余类和完全剩余系，同余方程，整数模的阶和中国剩余定理.Ⅰ.基本概念定义一：设m 是一个给定的正整数.如果两个整数a 、b 用m 除所得的余数相同，则称a 、b 对模m 同余，记为a ≡b （modm ）；否则，记为a ≡b （modm ）.例如，15≡7（mod4），－23≡12（mod7）.同余有如下两种等价定义法：定义一* 若m|a －b ，则称a 、b 对模m 同余.定义一**若a =b+mt(t ∈Z)，则称a 、b 对模m 同余.同余的基本性质：（1）.|)(mod 0a m m a ⇔≡（2）))((mod 反身性m a a ≡))((mod )(mod )(mod ))((mod )(mod 传递性对称性m c a m c b m b a m a b m b a ≡⇔⎭⎬⎫≡≡≡⇔≡（3）若则),(mod ),(mod m d c m b a ≡≡①);(mod m d b c a ±≡±②).(mod m bd ac ≡（4）若).(mod ,.,,2,1,0),(mod 0101m b x b x b a x a x a n i m b a n n n n i i +++=+++=≡ 则特别地，设)(mod ),()(01m b a Z a a x a x a x f i n n ≡∈+++=若 ，则).)(mod ()(m b f a f ≡（5）若).),((mod ),(mod c m m b a m bc ac ≡≡则特别地，又若（c,m ）=1，则).(mod m b a ≡ 【证明】因),(|b a c m -这等价于).(),(|),(b a c m c c m m -又因若（a ,b ）=),(d b d a d ⇒=1（d ≠0）及b|a c ，且（b,c ）=1,|a b ⇒ 从而有).(|),(b a c m m - 这个性质说明同余式两边的同一非零因数，不能像等式那样“约去”，只有当这非零因数与模互质时，才可“约去”.（6）),(mod m b a ≡而).(mod ),0(|d b a d m d ≡>则（7）设),(mod m b a ≡①若c>0，则);(mod mc bc ac ≡②d 为a 、b 、m 的任一公约数，则).(mod dm d b d a ≡ （8）若).(mod ,1),()(mod ),(mod 212121m m b a m m m b a m b a ≡=≡≡则且（9）若).,(),(),(mod m b m a m b a =≡则Ⅱ.剩余类和完全剩余系若按对某一模m 的余数进行分类，就可以引入所谓的剩余类和完全剩余系的概念.定义二：设m ∈N*，把全体整数按其对模m 的余数r （0≢r ≢m －1）归于一类，记为k r ，每一类k r （r=0,1,…,m －1）均称模m 的剩余类（又叫同余类）.同一类中任一数称为该类中另一数的剩余.剩余类k r 是数集{}{})(mod |,,,|m r a Z a a k Z q r m r qm k r r ≡∈=∈+=且也即是余数是模,它是一个公差为m 的（双边无穷）等差数列.根据定义，剩余类具有如下性质：（1）);(,1210j i k k k k k k Z j i m ≠=⋂⋃⋃⋃=-φ而（2）对任一数n ∈Z ，有惟一的00r k n r ∈使；（3）对任意的a ,b ∈Z ，a ,b ).(mod m b a k r ≡⇔∈定义三：设110,,,-m k k k 是模m 的（全部）剩余类.从每个k r 中任取一个数a r ,这m 个数110,,,-m a a a 组成的一个组称为模m 的一个完全剩余系，简称完系.例如，取m=4，则有{}{} ,9,5,1,3,7,,8,4,0,4,8,10--=--=k k ，k 2={…，－6，－2，2，6，10，…}，k 3={…，－5，－1，3，7，11，…}.数组0，1，2，3；－8，5，2，－1等等都是模的4的一个完全剩余系.显然，模m 的完全剩余系有无穷多个.但最常用的是下面两种：（1）非负数最小完全剩余系：0，1，2，…，m －1；（2）绝对值最小完全剩余系：它随m 的奇偶性不同而略有区别.当.),1(,,1,0,1,),1(,,12k k k k k m -----+= 为时（对称式）当).1(,,1,0,1,),1(,.),1(,1,0,1,),2(),1(,2-----------=k k k k k k k k m 或为时 由定义不难得到如下判别完全剩余系的方法：定理一：m 个整数m a a a ,,,21 是模m 的一个完系i a j i ,时当≠⇔≡)(mod m a j 定理二：设（b,m ）=1，c 为任意整数.若n a a a ,,,21 为一个完系，则c ba c ba c ba m +++,,,21 也是模m 的一个完全剩余系.特别地，任意m 个连续整数构成模m 的一个完全剩余系.【证明】只需证明：当).(mod ,m c ba c ba j i j i +≡+≠时而这可用反证法得证.下略. 设m 为一正整数，由于在0，1，…，m －1中与m 互质的数的个数是由m 惟一确定的一个正整数，因此，可给出如下定义.定义四：m 为一正整数，把0，1，…，m －1与m 互质的数的个数叫做m 的欧拉函数，记为).(m ϕ显然，)(m ϕ的定义域是正整数N*，前n 个值为：,,6)7(,2)6(,4)5(,2)4(,2)3(,1)2(,0)1( =======ϕϕϕϕϕϕϕ当m=p 为质数时，.1)(-=p p ϕ设k 是模的一个剩余类.若a 、b ∈k ，则).(mod m b a ≡于是由性质9知，（a ,m ）=（b,m ）.因此，若（a ,m ）=1，则k 中的任一数均与m 互质.这样，又可给出如下定义.定义五：如果一个模m 的剩余类k r 中任一数与m 互质，则称k r 是与模m 互质的剩余类；在与模m 互质的每个剩余类中任取一个数（共)(m ϕ个）所组成的数组，称为模m 的一个简化剩余系.例如，取m=6，在模6的六个剩余类中，{},,13,7,1,5,11,1 --=k{} ,17,11,5,1,7,5--=k 是与模6互质的剩余类.数组1，5；7，－7；1，－1；等等都是模6的简化剩余类.由此定义，不难得到：定理三:)(21,,,m a a a ϕ 是模m 的简化剩余系)).(,2,1,,)((mod ,1),(m j i j i m a a m a j i i ϕ =≠≡=⇔且 定理四：在模m 的一个完全剩余系中，取出所有与m 互质的数组成的数组，就是一个模m 的简化剩余系.这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法.显然，模m 的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m －1中与m 互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.定理五：设)(21,,,m a a a ϕ 是模m 的简化剩余系.若（k,m ）=1，则)(21,,,m ka ka ka ϕ 也是模m 的简化剩余系.下面介绍两个有关欧拉函数的重要结论.其证明略.定理六：（欧拉定理）若（a ,m ）=1，则)(mod 1)(m a m ≡ϕ特别地，（费马小定理）若m=p 为质数，p a ，则).(mod 11p a p ≡-定理七：（威尔逊定理）设p 素数，则（p －1）！).(mod 1p -≡定理八：（欧拉函数值计算公式）令m 的标准分解式为k k p p p m ααα 2121=，则 ∏=-=k i ip m m 1).11()(ϕ 例如，30=2·3·5，则.8)511)(311)(211(30)30(=---=ϕ读者应认识到：由于任何整数都属于模m 的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m ，然后在模m 的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.Ⅲ.同余方程设x a x a xa x a x f n n n n 为0111)(++++=-- 的整系数多项式.类似于多项式和代数方程式的有关定义，我们有定义六：同余式)(mod 0),(mod 0)(m a m x f n ≡≡叫做一元n 次同余方程.例如， )3(mod 03539257≡-+-x x x 是七次同余方程.定义七：若c 使得)(mod ,)(mod 0)(m c x m c f ≡≡则成立叫做同余方程)(mod 0)(m x f ≡的一个解.显然，同余方程的解是一些剩余类，而不仅是一个或n 个类.例如，),5(mod 1≡x )5(mod 4≡x 都是二次同余方程)5(mod 12≡x 的解.1．一次同余方程)(mod m b ax ≡（其中m a ）称为一次同余方程.关于它的解，有如下共知的结论： 定理九：若（a ,m ）=1，则)(mod m b ax ≡有一个解.定理十：若（a ,m ）=d>1，d b ，则)(mod m b ax ≡无解，其中)(mod 0m a ≡.定理十一：若（a ,m ）=d>1，d|b ，则)(mod m b ax ≡有d 个解.并且，若)(mod 1m x βα=的一个解为),(mod 1m r x ≡则d 个解为：1,,1,0),(mod 1-=+≡d k m km r x ，其中.,,1dm m d b d a ===βα 下面介绍一次同余方程1),(),(mod =≡m a m b ax （*） 的解法.【解法1】因（a ,m ）=1，则存在二数s,t ，使得as +mt=1，即)(mod 1m as =，由此有 )(mod ),(mod m bs x m bs asx ≡≡于是为（*）的解.【解法2】先把（*）变形成ab m a b x )((mod ≡仅只是形式上的记号），然后用与m 互质的数陆续乘右端的分子分母，直至把分母绝对值变成1（通过分子分母各对模m 取余数）而得到解.【解法3】得用欧拉定理.因),(mod )(mod ),(mod 11)()()(m a b x a m b ax m a m m m -⋅≡≡≡ϕϕϕ可得由 从而有解 ).(mod 1)(m a b x m -⋅≡ϕ2．一次同余方程组定义八：若数r 同时满足n 个同余方程：r n k m x f k k 则.,,2,1),(mod 0)( =≡叫做这n 个同余方程组成的同余方程组的解.定理十二：对同余方程组⎩⎨⎧≡≡).(mod ),(mod 2211m c x m c x记.],[,),(2121M m m d m m ==①若d 21c c -，则此同余方程组无解；②若21|c c d -，则此同余方程组有对模M 的一类剩余解.Ⅳ.模m 的阶和中国剩余定理（1）模m 的阶定义九：设m>1是一个固定的整数，a 是与m 互素的整数，则存在整数k ，1≢k ＜m ，使得)(mod 1m a k ≡.我们将具有这一性质的最小正整数（仍记为k ）称为a 模m 的阶.a 模m 的阶具有如下性质：①设m a k m a 模是,1),(=的阶，ν,u 是任意整数，则)(mod m a a v u ≡的充要条件是)(mod k u ν≡.特别地，)(mod 1m a u ≡的充分必要条件是k|u.【简证】充分性显然.必要性.设).(mod 11),()(mod ,,m a m a m a a u l u l u 易知及则由记=≡-=>ννν用带余除法，k r m a m a a k r r kq l r r kq <≤≡≡⋅<≤+=0).(mod 1),(mod 1,0,由即故这里及k 的定义知，必须r=0，所以).(mod k r u ≡②设a m a ,2),(=模m 的阶为k ，则数列,,,,32 a a a 模m 是周期的，且最小正周期是k ，而k 个数k a a a ,,,2 模m 互不同余.③设a m a 则,1),(=模m 的阶整除欧拉函数).(m ϕ特别地，若m 是素数p ，则a 模p 的阶整除p －1.（2）中国剩余定理（即孙子定理）设n m m m n ,,,,221 ≥是两两互质的正整数，记M=∏===n i ii i n i m M M m 1),,2,1(, 则同余方程组 ),,2,1)((mod n i m c x i i =≡有且只有解 ∑=≡ni ii i M c M x 1).(mod α （△） 其中.,,2,1),(mod 1n i m M i i i =≡α （△△）【证明】由)(1),(j i m m j i ≠=知，1),(=j i m M ，因此每一个同余方程)(mod 1i iy m M ≡ （i =1，2，…n ）都有解，于是必存在),(|,).(mod 1,j i M m M m M m M i i i i i i i ≠=≡又因使得αα 所以对模).(mod ),,2,1(111i i i i i n n n i i i i m c c M c M c M c M n i m ≡≡++++=αααα 有故（△△）是（△）的解.若21,x x 是适合（△）的任意两个解，则).(1),(,,,2,1),(mod 21j i m m n i m x x j i i ≠===因 故),(mod ),(mod 212121M x x m m m x x n ≡≡即 因此，（△△）是（△）的惟一解.赛题精讲例1：数1978n 与1978m 的最末三位数相等，试求正整数m 和n ，使得n+m 取最小值，这里.1≥>m n （第20届IMO 试题）【解】由已知而),1000(mod 10781978mn ≡1000=8×125，所以)8(m o d 10781978m n ≡ ① )125(mod 10781978m n ≡ ②因1≥>m n ，且（1978m ，125）=1，则由②式知1978n －m ≡1（mod125）③又直接验证知，1978的各次方幂的个位数字是以8、4、2、6循环出现的，所以只有n －m 为4的倍数时，③式才能成立，因而可令n －m=4k.由于. n+m=（ n －m ）+2m=4k+2m ，因而只需确定出k 和m 的最小值.先确定k 的最小值：因为19784=（79×25+3）4≡34≡1（mod5），19784≡34≡1（mod25）.故可令19784=5t+1，而5 t ，从而0≡1978n －m －1=19784k －1=（5k+1）k －1≡2)5(2)1(t k k ⋅- +)125(mod5t k ⋅，显然，使上式成立的k 的最小值为25. 再确定m 的最小值：因1978≡2（mod8），则由①式知，)8(mod 22mn ≡ ④ 由于,1≥>m n ④式显然对m=1，2不成立，从而m 的最小值为3.故合于题设条件的n+m 的最小值为106.【评述】比例中我们用了这样一个结论：1978的各次方幂的个位数字是以8，4，2，6循环出现，即，当r=1，2，3，4时，).10(mod 6,2,4,8197819784≡=+r q p 这种现象在数学上称为“模同期现象”.一般地，我们有如下定义：整数列{}n x 各项除以m （m ≣2，m ∈N*）后的余数n a 组成数列{}n a .若{}n a 是一个周期数列，则称{}n x 是关于模m 的周期数列，简称模m 周期数列.满足n T n a a =+（或n T n x a ≡+ （modm ））的最小正整数T 称为它的周期.例如，（1）{}n 1978是模10周期数列，周期为4；（2）自然数列{n}是一个模m （m ≣2，m ∈N*）周期数列，周期为m ；（3）任何一个整数等差数列都是一个模m （m ≣2，m ∈N*）周期数列，周期为m.例2：设a 是方程01323=+-x x 的最大正根，求证：17可以整除[a 1788]与[a 1988].其中[x ]表示不超过x 的最大整数. （第29届IMO 预选题）【证明】根据如下符号表可知，若设三根依次为a <<βα， 则,121,211<<-<<-βα.||,,02)12(2)(,223233βαβαααααα<<->-=+-+-=-<于是由于f a另一方面，由韦达定理知，)8(1296292)3(2)(233322222a aa a a a a a a -+=+-+=+-+=+-=-+=+αββαβα .1,8)22(2222<+∴=>βαa为了估计[1788a ]、[1988a ]，先一般考察[a n ]，为此定义：),2,1,0.( =++=n a u n n n n βα直接计算可知：).0(3,9.32,323222210≥-==++==++==++n n u u a u a u u n n 以及βαβ 又因,12223,0,||(10<-<-=+>+<<+<αβαβαβαβα又即n n n n 当2≥n 时，)].(1[1)(),1||22n n n n n n n n n n n u u a βαβαβαβαβα+---=+-=<+<+≤+则),2,1.(1][ =-=∴n u a n n由此知，命题变为证明：1119881788--u u 和能被17整除.现考察{}n u 在模17的意义下的情况：,2,6,5,16,9,9,11,1,7,9,3,311109876543210≡≡≡≡≡≡≡≡≡≡≡≡u u u u u u u u u u u u ,9,3,3,0,6,14,118171615141312≡≡≡≡≡≡≡u u u u u u u可见，在模17意义下，{}n u 是16为周期的模周期数列，即).17(mod 16n n u u ≡+由于 1788),17(mod 1),17(mod 1),16(mod 41988),16(mod 1241988121788≡≡≡≡≡≡u u u u 故故 ).17(mod 01,0119881788≡-≡-u u 命题得证.例3：求八个整数821,,,n n n 满足：对每个整数k （－1985<k<1985），有八个整数a 1，a 2，…，a 8∈{－1，0，1}，使得.882211n a n a n a k +++= （第26届IMO 预选题）【解】令数集{}.1,,2,1},1,0,1{,333|12321+=-∈⋅++⋅+⋅+==+n i a a a a a k k G i n n 显然 3331m a x 12=++++=+n nG H ， .33312H mixG n -=----=且G 中的元素个数有1231+=+H n 个.又因G 中任意两数之差的绝对值不超过2H ，所以G 中的数对模2H+1不同余.因此，G 的元素恰好是模2H+1的一个绝对值最小的完系，于是，凡满足H k H ≤≤-的任意整数都属于G ，且可惟一地表示为：nn a a a a 33312321⋅++⋅+⋅++形式.当n=7时，H=3280>1985，而n=6时，H=1043<1985.故n 1=1，n 2=3，…，n 8=37为所求. 例4：设n 为正整数，整数k 与n 互质，且0<k<n.令M={1，2，…，n －1}，给M 中每个数染上黑、白两种颜色中的一种，染法如下：（i ）对M 中每个i ，i 与n －i 同色；（ii ）对M 中每个i ，i ≠k,i 与|k －i |同色.求证：M 中所有的数必为同色. （第26届IMO 试题）【证明】因,1),(=n k 又0，1，…n －1是模n 的一个完全剩余系，所以0，k ，2k ，…，（n －1）k 也是模n 的一个完全剩余系.若设),1,,2,1,11)((mod -=-≤≤≡n j n r n r jk j j 其中 则M=}.,,,{121-n r r r 下只需证).21(1-≤≤+n j r r j j 与因为，若如此，当r 1的颜色确定后，M 中所有都与r 1同色.由于)(mod ),(mod )1(11n r k r n r k j j j j ++≡+≡+则，因此，（1）若k r r n k r j j j +=<++1,则，于是，由条件（i ）知，j j j j r r n n r n r k =---=-+)(1与同色.又由条件（ii ）知，111||+++=---j j j r k r k r k 与同色，故j j r r 与1+同色.综上所述可知，j j r r 与1+同色.命题得证.例5：设a 和m 都是正整数，a >1.证明：).1(|-m a m ϕ【证明】实上，显然1-m a a 与互素，且1-m a a 模的阶是m ，所以由模阶的性质③导出).1(|-m a m ϕ例6：设p 是奇素数，证明：2p －1的任一素因了具有形式x px ,12+是正整数.【证明】设q 是2p －1的任一素因子，则q ≠2.设2模q 的阶是k ，则由)(mod 12q p ≡知k|p ，故k=1或p （因p 是素数，这是能确定阶k 的主要因素）.显然k ≠1，否则),(mod 121q ≡这不可能，因此k=p.现在由费马小定理)(mod 121q q ≡-推出.1|,1|--q p q k 即因p 、q 都是奇数，故q －1=2p x （x 是个正整数），证毕.例7：设m,a ,b 都是正整数，m>1，则.1)1,1),(-=--b a b a mm m 【证明】记).1,1(--=b a m m d 由于（a ,b ）|a 及（a ,b ）|b ，易知1|1),(--a b a m m及11 1|1),(--b b a m m ，故d m b a |1),(-，另一方面设m 模d 的阶是k ，则由)(mod 1),(mod 1d m d m b a ≡≡推出，k|a 及k|b ，故k|（a ，b ）.因此.1|),(mod 1),(),(-≡b a b a m d d m 即综合两方面可知，.1),(-=b a m d 证毕.例8：设n ，k 是给定的整数，n>0，且k （n －1）是偶数.证明：存在,1),(),(,,==n y n x y x 使得是).(mod n k y x ≡+【证明】我们先证明，当n 为素数幂αp 时结论成立.实际上，我们能证明，存在x ,y ，使 p x y ，且k y x =+.如p=2，则条件表明k 为偶数，可取2,11,1,2;1,1-==-==>-==k y x k y x p k y x 或则如中有一对满足要求.一般情形下，设r r p p n αα 11=是n 的标准分解，上面已证明，对每个i p ，均有整数i x ，i y ，使p i x i y i ，且).,,2,1(r k y x i i =+现在孙子定理表明，同余方程组)(mod ,),(mod 111r a r r p x x p x x ≡≡ α有解x ，同样)(mod ,),(mod 111r a r r p y y p y y ≡≡ α也有解y.现在易证x ,y 符合问题中的要求：因p i x i y i ，故p i x y （i =1，…，r ），于是（x y ，n ）=1.又).(mod ),,,1)((mod 1n k y x r i p k y x y x i i i ≡+==+=+故 α例9：设n 为任意的正整数.证明：一定存在n 个连续的正整数解，使其中任何一个都不是质数的整数幂. （第30届IMO 试题）【证明】取2n 个两两不同的质数.,,,,,,2121n n q q q p p p 和同余方程组),(mod i i q p i x -≡ n i ,,2,1 =.由于n n q p q p q p ,,,2211 两两互质，根据孙子定理必有解，取为正整数N ，则n 个连续正整数N+1，N+2，…，N+n 都至少含有两个不同的质因数，因而它们中的任一个都不是质数的整数幂.证毕.。

完系、简系、剩余类定义1．剩余类：把关于模m同余的数归于一类，每类称为一个模m的剩余类. 即由关于模m同余的数组成的集合，每一个集合叫做关于模m的一个剩余类(又叫同余类)．共有m个剩余类.设K r是余数为r的剩余类, 则K r＝{qm＋r| m是模, r是余数, q∈Z}＝{a |a∈Z且a≡r(mod m)}.剩余类的性质：⑴Z＝K0∪K1∪K2∪…∪K m−1，当i≠j时，K i∩K j＝Ø；⑵对于∨−n∈Z，有唯一的r∈{0, 1, 2, …, m−1}，使得n∈K r；⑶对∨−a, b∈Z，a, b∈K r ⇔a≡b (mod m)定义2.完系：设K0，K1，…，K m−1是模m的m个剩余类，从K r中各取一数a r 作为代表，则这样的m个数a0，a1，…，a m−1称为模m的一个完全剩余系，简称m的完系. 例如：1, 2, 3, …, m.若一组数y1, y2, …, y s满足：对任意整数a有且仅有一个y j，使得a≡y j (mod m)，则y1, y2, …, y s是模m的完全剩余系.模m的完全剩余系有无穷多个，但最常用的是下面两个：①最小非负剩余系：0, 1, 2, 3, …, m−1；②最小绝对值剩余系：(随m的奇偶性略有区别) 当m＝2k+1时，为−k, −k+1, …, −1, 0, 1, 2, …, k−1, k；当m＝2k时，为−k+1, −k+2, …, −1, 0, 1, 2, …, k或−k, −k+1, …, −1, 0, 1, 2, …, k−2, k−1.例如，集合{0, 6, 7, 13, 24}是模5的一个完全剩余系，集合{0, 1, 2, 3, 4}是模5的最小非负完全剩余系.性质：(i) m个整数构成模m的一完全剩余系⇔两两对模m不同余；(ii) 若(a, m)＝1，则x与ax＋b同时跑遍模m的完全剩余系.完全剩余系的判断方法：定理1：a1, a2,…, a m是模m的一个完全剩余系⇔a i≡／a j (mod m), i≠j；定理2：设(a, m)＝1, b∈Z, 若x1, x2, , x m是模m的一个完全剩余系，则ax1＋b, ax2＋b, …, ax m＋b也是模m的一个完全剩余系；特别地，m个连续的整数构成模m的一个完系.设K r是模的一个剩余类, 若a, b∈K r，则a≡b(mod m), 于是(a, m)＝(b, m).因此，若(a, m)＝1，则K r中的任一数均与m互质, 这样，又可给出如下定义：定义3.简系：如果r与m互质，那么K r中每一个数均与m互质，称K r为与模m互质的剩余类．这样的剩余类共有φ(m)个，从中各取一个代表(共取φ(m)个)，它们称为模m的简化剩余系，简称简系．当m为质数p时，简系由p−1个数组成．又如：m＝6，在模6的六个剩余类中：K1＝{…, −11, −5, 1, 7, 13,…} K5＝{…, −7, −1, 5, 11, 17,…}是与模6互质的剩余类，数组1, 5；7, −7；1, −1；等等都是模6的简系.性质：①K r与模m互质⇔K r中有一个数与m互质；②与模m互质的剩余类的个数等于φ(m)；③若(a, m)＝1, 则x与ax同时跑遍模m的简化剩余系.简化剩余系的判断方法：定理3：a1，a2，…，aφ(m)是模m的简化剩余系⇔(a i, m)＝1, 且a i≡／a j(mod m) (i≠j, i, j＝1, 2, …, φ(m)).定理4：在模m的一个完全剩余系中,取出所有与m互质的数组成的数组,就是一个模m的简化剩余系.定理5：设(k, m)＝1, 若a1, a2, …, aφ(m)是模m的简系, 则ka1, ka2, …, kaφ(m)也是模m的简系.这三个定理中，定理3与定理5是简化剩余系的判别方法，定理4是它的构造方法. 显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m －1中与m 互质的那些数组成的数组.说明：由于任何整数都属于模m 的某一剩余类，所以，在研究某些整数性质时，选取适当的(模)m ，然后在模m 的每个剩余类中取一个“代表数”(即组成一个完全剩余系)，当弄清了这些代表数的性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.例1、设n 为偶数，a 1, a 2,…, a n 与b 1, b 2,…, b n 均为模n 的完全剩余系，试证：a 1＋b 1, a 2＋b 2,…, a n ＋b n 不是模的完全剩余系.证明：假设a 1＋b 1, a 2＋b 2,…, a n ＋b n 是模的完全剩余系. ∴1(1)()1+2++(mod )22n i i i n n n a b n n =++≡≡≡∑ ∵a 1, a 2,…, a n 也是模的完全剩余系. ∴11(1)(mod )22n n i i i n n n a i n ==+≡=≡∑∑，同理有：1(mod )2n i i n b n =≡∑ 1()0(mod )n i i i a b n n =∴+≡≡∑，∴n |n2, 矛盾！故假设不成立，从而原命题成立.例2、设m ＞1, (a , m )＝1，b ∈Z , 求和：∑-=+⋅10}{m i mb i a , 其中{x }为x 的小数部分. 解：∵i 取遍模m 的完系，令x i ＝a ·i ＋b ，则也取遍模m 的完系.故11110000111{}{}{}(1)22m m m m i i i k k x a i b k k m m m m m m m m ----====⋅+-====⨯-=∑∑∑∑总结：若a 1, a 2,…, a m 是模m 的一个完系，则①a 1＋a 2＋…＋a m ≡1＋2＋…＋m (mod m )；②a 1·a 2·……·a m ≡1·2·…·m (mod m )； ③(a 1)n ＋(a 2)n ＋…＋(a m )n ≡1n ＋2n ＋…＋m n (mod m ).例3、已知m , n 为正整数, 且m 为奇数, (m , 2n －1)＝1. 证明：m |∑=m k n k1.证明：∵1, 2, …, m 构成模m 的完系, (m , 2)＝1，∴2, 4, …, 2m 也构成模m 的完系.∴)(mod )2(11m k k m k n m k n ∑∑==≡，即)(mod 0)12(1m k m k n n ≡-∑=. ∵(m , 2n －1)＝1，∴∑=m k n k m 1|得证. 例4、求八个整数n 1, n 2,…, n 8满足：对每个整数k (－2014＜k ＜2014)，有八个整数a 1, a 2,…, a n ∈{−1, 0, 1},使得k ＝a 1n 1＋a 2n 2＋…＋a 8n 8解：令G ＝{k | k ＝a 1＋a 2·2＋a 3·32＋…＋a n +1·3n ，a i ∈{−1, 0, 1}，i ＝1，2，…，n ＋1}.显然max G ＝1＋3＋32＋…＋3n ＝3n +1－12(记为H )，min G ＝－1－3－32＋…－3n ＝－H . 且G 中的元素个数有3n +1＝2H ＋1个， 又∵G 中任意两数之差的绝对值不超过2H ，∴G 中的数对模2H ＋1不同余，∴G 的元素恰好是模2H ＋1的一个绝对值最小的完系，于是凡满足－H ≢k ≢H 的任意整数都属于G ，且可唯一地表示为a 1＋a 2·2＋a 3·32＋…＋a n +1·3n 形式，当n ＝7时，H ＝3208＞2014，而n ＝6时，H ＝1043＜2014，故n 1＝1，n 2＝3，…，n 8＝37为所求.例5、已知p 为大于3的质数，且112＋122＋132＋…＋1(p －1)2＝a b，a ，b ∈N *. (a , b )＝1，证明：p a . 证明：对于不超过p −1的自然数k ，由于(k , p )＝1，所以存在唯一的不超过p −1的自然数x ，满足1(mod )kx p ≡而且，当k ＝1或p −1有x ＝1或p −1，当22k p ≤≤-时，有22,x p x k ≤≤-≠，故当k 取遍1，2，……，p −1时，x 也取遍1，2，……，p −1，因为(,(1)!)1,1(mod )p p kx p -=≡由可得到(1)!(1)!(1)!(mod )(1)!(mod ),p p kx p p p x p k--≡--≡或所以 2211222211((1)!)((1)!)(1)(21)((1)!)((1)!)(mod )6p p k x p a p p p p p x p p b k --==----=≡-≡-∑∑ 因为p 是大于3的素数，所以p −1不小于4，所以(p −1)!含有因数6， 从而2(1)(21)((1)!)0(mod )6p p p p p ---≡，即2((1)!)0(mod )p a p b -≡， 因为(,(1)!)1p p -=，所以2(,((1)!))1p p -=，从而0(mod )0(mod )a p a p b≡⇒≡ 例6、(2003克罗地亚奥林匹克) 对于所有奇质数p 和正整数n (n ≣p )，试证：p n C ≡[n p] (mod p)例7、(第26届IMO) 设n 为正整数，整数k 与n 互质，且0＜k ＜n . 令M ＝{1, 2, …, n −1}(n ≣3), 给M 中每个数染上黑白两种染色中的一种，染法如下：⑴对M 中的每个i ，i 与n −i 同色，⑵对M 中每个i ，i ≠k ，i 与|k −i |同色，试证：M 中所有的数必为同色.证明：∵(k , n )＝1且0，1，2，…，n −1是一个模n 的最小非负完系，∴0·k ，1·k ，2·k ，…，(n −1)·k 也是一个模n 的完全剩余系.若设r j ≡j ·k (mod n )(其中1≢r j ≢n －1，j ＝1，2，…，n －1) ，则M ＝{1，2，…，n −1}＝{121,,,-n r r r } 下面只要证明r j 与r j +1(j ＝1，2，…，n −2)同色即可. 因为若如此，当r 1颜色确定后，M 中所有的数都r 1与同色. 由于(j ＋1)k ≡r j +1(mod n )，则r j ＋k ≡r j +1(mod n )，因此若r j ＋k ＜n ，则r j +1＝r j +k ，由条件⑵知r j +1与| r j +1－k |＝r j 同色；若r j ＋k ＞n ，由r j +1＝r j +k －n ，由条件⑴知k －r j +1＝n —r j 与n －(n —r j )＝r j 同色，即k －r j +1与r j 同色， 由条件⑵知k －r j +1与|k －(k －r j +1)|＝r j +1同色，因此r j +1与r j 同色.综上：此r j +1与r j 同色. 故M 中所有的数必为同色.例8、(2001第42届IMO)设n 为奇数且大于1，k 1, k 2,…, k n 为给定的整数，对于1, 2, …, n 的n !个排列中的每一个排列a ＝(a 1, a 2,…, a n )，记S (a )＝∑=n i i ia k 1，试证：有两个排列b 和c ，使得n !| S (b )－S (c ).证明：假设对任意两个不同的b 和c ，均有S (b )≡／S (c )(mod n !)，则当a 取遍所有1，2，…，n 的n !个排列时， S (a )也取遍模n !的一个完全剩余系，且每个剩余系恰好经过一次，所以()aS a ∑≡1+2+3+…+n !(mod n !)≡12(n !+1)n !≡n !2×n !＋n !2≡n !2(mod n !) (n ＞1)其中()a S a ∑表示对取遍个排列求和(下同)，下面用另一种方法计算1()()ni i a a i S a k a ==∑∑∑：对于k 1，i ∈{1，2，…，n }，a i ＝1时，剩n －1个数，有(n －1)!个排列，a i ＝2时，有(n －1)!个排列，…∴k 1的系数为(n －1)!·(1+2+…+n )＝12(n +1)!. ∴()a S a ∑＝(1)!2n +1n i i k =∑ 但()a S a ∑＝(1)!2n +1n i i k =∑≡0(mod n !) (∵n 为奇数)，∴n !2≡0(mod n !), 矛盾. ∴n !| S (b )－S (c ).例9、设m 是给定的整数. 求证：存在整数a ，b 和k . 其中a ，b 均为奇数，k ≣0，使得2m ＝a 19＋b 99＋k ·21999.另解：设x ，y 为奇数，若x ≡／y (mod 21999)，则x 19－y 19＝(x －y )(x 18＋x 17y ＋…＋xy 17＋y 18)，∵x 18＋x 17y ＋…＋xy 17＋y 18为奇数，∴x 18＋x 17y ＋…＋xy 17＋y 18与21999互质，∴x 19≡／y 19(mod 21999)故当a 取遍模21999的简化剩余系时，a 19也取遍模21999的简化剩余系，∴一定存在a ，使得a 19≡2m －1(mod 21999)，并且有无穷多个这样的a ，故2m －1－a 19＝k ·21999令b ＝1，则2m ＝a 19＋b 99＋k ·21999. 当a 足够小时，不难知k ≣0.。

第三章同余§ 1同余的概念及其基本性质定义1设meZ\称之为模。

若用加去除两个整数“与b所得的余数相同，则称"上对模加【可余，记作：a = b (mod /n)；若所得的余数不同，则称w,〃对模加不同余，记作："圭b(mod〃2)。

例如，8 = 1 (mod 7),:所有偶数“三0 (mod 2),所有奇数“ =1 (mod 2)。

同余是整数之间的一种关系，它具有下列性质：R a = a (mod m)；(反身性)2、若"三b (mod加)，贝肪三a (mod m)；(对称性)3、若"三b (mod m), b = c (mod m),贝h 三 c (mod 加);(传递性) 故同余关系是等价关系。

定理1整数对模加同余的充分必要条件是RP a = b + mt,r eZo证明设"=+ b = mq2 + r v 0 < r2 < m,贝l] a = b (mod m) O 打=r2 O a — b = m(q{一⑴)O I (" 一b)°性质1(1)若％三S (mod m)> a2 = b2 (mod m)> 则a x + a2 +b2 (mod /n)；(2)若"+ h = c (mod 〃?)，贝ij a = c-b (mod m)o性质2 若=/?, (mod /??), a2 =b2 (mod m),则"]5 "心(mod m)：特别地，若a = b (mod m),则畑三kb (mod加)。

定理2若比…亞三〃叶・％(mod/),兀三片(mod皿)，j = 1,2,…人则艺比…致坊‘…場三另3时灼)吓…yj (mod/)；特别地,若％三化(mod加),i = OJ2・・・，n，则心* +"心]北1 + - - +u()=b n x n +/>n_|x71'1 + …+ "o (mod 加)。

《信息安全数学基础》课程教学大纲课程性质：学科基础课课程代码：学时：72（讲课学时：72实验学时：0课内实践学时: 0）学分：4.5适用专业：通信工程一、课程教学基本要求《信息安全数学基础》是通信工程专业教学计划中的一门学科基础课，通过对本课程的学习，可以使学生系统地掌握本学科的数学基础，使得学生能够初步掌握和运用数学理论来分析和研究一些问题。

二、课程教学大纲说明信息安全学科是一门新兴的学科．它涉及通信学、计算机科学、信息学和数学等多个学科。

为了使学生系统的掌握信息安全理论基础和实际知识，需要专门开课讲授与信息安全相关的数学知识，特别是关于初等数论知识。

通过本课程的学习，使学生掌握信息安全学科涉及的数学基本概念、基本原理和实际应用，建立数学体系的完整概念，为后续专业课程的学习奠定基础。

本课程的教学内容主要以理论为主，介绍了整数的可除性、同余理论以及有关原根与指标等知识。

学好本课程内容的前提条件：高等数学和线性代数的基础知识。

教学方法与手段：本课程采用课堂理论教学为主要教学方法，习题课和批改作业为检查措施，期末笔试考试为检查手段，以确保本课程的教学质量。

三、各章教学结构及具体要求（一）第一章整数的可除性1.教学目的和要求。

通过对本章的学习，使学生加深对整数的性质、狭义和广义欧几里得除法和算术基本定理的了解，更深入地理解初等数论与现代密码学的关系。

2.教学内容和要点。

共讲授六个方面的内容：（1）整除的概念、欧几里得除法；（2）整数的表示（3）最大公因数与广义欧几里得除法（4）整除的进一步性质及最小公倍数（5）素数、算术基本定理（6）素数定理。

（二）第二章同余1. 教学目的和要求。

通过对本章的学习，使学生了解同余、剩余类和简化剩余类的概念，熟悉欧拉定理、费马小定理。

2.教学内容和要点。

共讲授五个知识点的内容：（1）同余的概念及基本性质（2）剩余类及完全剩余系（3）简化剩余系与欧拉函数（4）欧拉定理费马小定理（5）模重复平方计算法。

剩余类、剩余系、完全剩余系和简化剩余系学习笔记经常在⼀些数论题题解中看到剩余类、剩余系、完全剩余系、简化剩余系这⼏个名词，但总感觉⾃⼰对它们的概念理解得不是很深，⽽且还经常混淆，故写篇博客记录下⾃⼰所理解的剩余系相关知识，如有错误，欢迎路过的⼤佬指正。

剩余类（同余类）定义n n r∈[0,n−1]n C r=n∗x+r,x∈Znn=1145,r=14C14=1145x+141145−1131,14,1159性质剩余系定义n n n x x xnn=1145r={11,4,5,14}114514性质完全剩余系（完系）定义n n n n nnn=5{0,1,2,3,4}5{5,1,8,−3,14}5性质n r a∈Z,b∈Z gcd(n,a)=1a∗r i+b (i∈[0,n−1])n证明：命题 1 ：如果r是⼀个模n的剩余系，那r i+b⼀定也构成⼀个模n的完全剩余系。

反证法，若r i+b不构成⼀个模n的完全剩余系，则存在两个元素同余n，即有r x+b≡r y+b(mod n)，同余式两边同时减去b，有r x≡r y(mod n)，与r是⼀个模n的剩余系这⼀前提⽭盾，命题 1 得证。

命题 2：若r是⼀个模n的完全剩余系，对于任意的整数a，若有gcd(a,n)=1，则a∗r i也构成⼀个模n的完全剩余系。

同样是反证法，若结论不成⽴，则有a∗r x≡a∗r y(mod n)，因为gcd(a,n)=1，所以⼀定存在a mod p的逆元inv(a)，同余式两边同时乘以inv(a)，则有r x≡r y(mod n)，与前提⽭盾，命题 2 得证。

这俩个命题都得证，所以a∗r i构成⼀个模n的完全剩余系，a∗r i+b也构成⼀个模n的完全剩余系，故性质得证。

简化剩余系（既约剩余系、缩系）定义nφ(n)n r nφ(n)φ(n)nn=10{1,3,7,9}10n=5{1,8,7,14}5n n性质n r a∈Z gcd(n,a)=1a∗r i n 参考资料国际惯例。

同余式知识定位数论是初中数学竞赛比较重要的一个知识点，在历年竞赛中占据非常发比例，其中同余理论是初等数论中的重要内容之一，其同余式概念及应用，剩余系概念要熟练掌握。

本文归纳总结了同余的若干性质，将通过例题来说明这些方法的运用。

知识梳理1、同余概念定义1：给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m 同余，记作a≡b(modm)，并读作a同余b，模m。

（1）若a与b对模m同余，由定义1，有a=mq1＋r，b=mq2+r．所以a-b=m(q1-q2)，即m｜a-b。

反之，（2）若m｜a-b，设a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2。

于是，我们得到同余的另一个等价定义：定义2：若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a与b对模m同余．2、同余定理定理1：（1）a≡a(modm)．（2）若a≡b(modm)，则b≡a(modm)．（3）若a≡b(modm)，b≡c(modm)，则a≡c(modm)．定理2：若a≡b(modm)，c≡d(modm)，则a±c≡b±d(modm)，ac≡bd(modm)．证：由假设得m｜a-b，m｜c-d，所以m｜(a±c)-(b±d)，m｜c(a-b)＋b(c-d)，即a±c≡b±d(modm)，ac≡bd(modm)．由此我们还可以得到：若a≡b(modm)，k是整数，n是自然数，则a±k≡b±k(modm)，ak≡bk(modm)，a n≡b n(modm)．定理3：若ac≡bc(modm)，且(c，m)=1，则a≡b(modm)．定理4： 若n ≥2，a ≡b(modm 1)，a ≡b(modm 2)，…………a ≡b(modm n )，且M=[m 1，m 2，…，m n ]表示m 1，m 2，…，m n 的最小公倍数，则a ≡b(modM)3、剩余类和完全剩余系全体整数集合可按模m 来划分：当且仅当()mod a b m ≡时，a 和b 属于同一类。

型剩余类及完全剩余系定义设m是一个给定的正整数，K r r 0,1,”，m 1表示所有形如qm r q 0, 1, 2，川的整数组成的集合，则称K。

，©，川，K m1为模m的剩余类•定理1设m 0, K°K,川,心1是模m的剩余类，则(i)每一整数必包含于某一个类里，而且只能包含于一个类里；(ii)两个整数x, y属于同一类的充分必要条件是x y modm .证(i)设a是任意一个整数，则由带余除法，得 a qm r ,0 r m，故a K r.故每一整数必包含于某一类里.又设a K r,且a K r,这里0 r m,0 r m，则存在整数q, q使得a mq r,a mq r .于是，m| r r , m| r r .但是0 r r m，故r r 0,r r 0,r r .(ii)设a,b是两个整数，并且都在K r内，则存在整数q1,q2分别使得a q1m r ,b q2m r.故a b modm .反之，若a b modm，则由同余的定义知，a,b被m除所得的余数相同，设余数都为r 0 r m，则a和b都属于同一类K r.定义在模m的剩余类K0,K1^|,K m 1中，各取一数a j C j, j 0,1川，m 1，此m个数a0 ,a1，川,a m 1称为模m的一个完全剩余系.推论m个整数作成模m的一个完全剩余系的充分必要条件是这m个整数两两对模m 不同余.证充分性设a1,a2,|#,a m是m个两两对模m不同余的整数.由定理1知，每个整数a i必在模m的m个剩余类K0,K1，川，K m1中某一剩余类里，且只能在一个剩余类里.因a1,a2,|||,a m是m个两两对模m不同余的整数，故有定理1得，a「a2,川，a m分别属于不同的剩余类，故a i ,a 2,川，a m 是模m 的一个完全剩余系必要性 设a i ,a 2,川，a m 是模m 的一个完全剩余系，则由完全剩余系的定义得，这 m 个数分别属于不同的m 个剩余类K 0, K 1^|,K m1-由定理1得，a 1,a 2^| ,a m 两两对模m 不 同余•0,1，川，m 1是模m 的一个完全剩余系号，川，1,0,1,川,号 是模m 的一个完全剩余系定理2设m 是一个正整数，a,b 都为整数， a,m 1，若x 通过模m 的一个完全剩余系，则ax b 也通过模m 的一个完全剩余系.证 设x 通过模m 的完全剩余系a 1, a 2^ |, a m .下面证明ax b 也通过模m 的一个完全 剩余系.根据定理1的推论，只需证明aa 1 b,aa 2 b,川，aa m b 两两对模m 不同余.因厲赴，川，a m 是模m 的一个完全剩余系，故由定理 1的推论得，a 「a 2,川，a m 两两对 模m 不同余.下面用反证法证明 aa 1 b,aa 2 b,川，aa m b 两两对模 m 不同余.假设 aa 1 b,aa 2 b,川,aa m b 不是两两对模 m 不同余，则其中有两个数对模 m 同余，设aa i b a j b modm ,1 i j m ，贝U aa a j modm .因 a, m 1 ， 故 a i a j modm .这与a 「a 2,川，a m 两两对模m 不同余矛盾.定理3设m , 0,m 2 0, m,, m 21，而x 1, x 2分别通过模 , m 2的一个完全剩余系，则m ?X 1 gX 2通过模gm ?的一个完全剩余系.证 当x-i , x 2分别通过模 m“ m 2的一个完全剩余系时, 值，下面证明这 gm 2个整数两两对模 m 1m 2不同余.设m 2为 m]X 2 m 2x 1 gx ? modm ^m ?,其中x,X i 是X i 所通过的模m i 的完全剩余系中的数，i 1,2.当m 为奇数时, 当m 为偶数时， m2 都是模m 的完全剩余系.1与号训‘仙川号m 2m m 1x 2共取了 mim 2个整数(1)由（1）得, m2X! m(x2叫為m1x2modg ，从而叫為m2% mod m .因mi,m21，故％ x i modm -又因x）,x1是模的完全剩余系中的数，故捲洛.同理，X2 X2.故当x1, x2分别通过模m i, m2的一个完全剩余系时，m2m m|x2共取了m^m?个整数值, 下面证明这m i m）2个整数两两对模m i m2不同余.从而由定理1的推论得，这m^m?个整数作成模mim2的一个完全剩余系.定义0,1^|,m 1叫做模m的最小非负完全剩余系；当m是奇数时，m 4 d I L 1 1 a m •d ,|||, 1,0,1,|||, 叫做模m的绝对最小完全剩余系；当m是偶数时，号,川，1,o,1, 忙1或m训，仙川,m叫做模m的绝对最小完全剩余系.作业P57: 1,2,3,4 ，习题解答1.证明X u p st v,u 0,1j||, p s t 1,v 0,1,|||,p t 1,t s是模p s的一个完全剩余系。