(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）模重复平方计算法。