下载文档原格式
一、同餘，剩餘類與剩餘系(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中一個關係”~”。
§2 剩余类及完全剩余系定义 设m 是一个给定的正整数，()0,1,,1r K r m =-表示所有形如()0,1,2,qm r q +=±±的整数组成的集合，则称011,,,m K K K -为模m 的剩余类.定理1 设0110,,,,m m K K K ->是模m 的剩余类，则（ⅰ）每一整数必包含于某一个类里，而且只能包含于一个类里； （ⅱ）两个整数,x y 属于同一类的充分必要条件是()mod .x y m ≡证 （ⅰ）设a 是任意一个整数，则由带余除法，得,0a qm r r m =+≤<，故.r a K ∈故每一整数必包含于某一类里. 又设,r a K ∈且r a K '∈，这里0,0r m r m '≤<≤<，则存在整数,q q '使得,.a mq r a mq r ''=+=+于是，|,|.m r r m r r ''--但是0r r m '≤-<，故0,0,.r r r r r r '''-=-== （ⅱ）设,a b 是两个整数，并且都在r K 内，则存在整数12,q q 分别使得12,.a q m r b q m r =+=+故()mod .a b m ≡反之，若()mod a b m ≡，则由同余的定义知，,a b 被m 除所得的余数相同，设余数都为()0r r m ≤<，则a 和b 都属于同一类r K . 定义 在模m 的剩余类011,,,m K K K -中，各取一数,0,1,,1j j a C j m ∈=-，此m 个数011,,,m a a a -称为模m 的一个完全剩余系.推论 m 个整数作成模m 的一个完全剩余系的充分必要条件是这m 个整数两两对模m不同余.证 充分性 设12,,,m a a a 是m 个两两对模m 不同余的整数. 由定理1知，每个整数i a 必在模m 的m 个剩余类011,,,m K K K -中某一剩余类里，且只能在一个剩余类里. 因12,,,m a a a 是m 个两两对模m 不同余的整数，故有定理1得，12,,,m a a a 分别属于不同的剩余类，故12,,,m a a a 是模m 的一个完全剩余系.必要性 设12,,,m a a a 是模m 的一个完全剩余系，则由完全剩余系的定义得，这m 个数分别属于不同的m 个剩余类011,,,m K K K -. 由定理1得，12,,,m a a a 两两对模m 不同余. 0,1,,1m -是模m 的一个完全剩余系.当m 为奇数时，11,,1,0,1,,22m m ----是模m 的一个完全剩余系. 当m 为偶数时，,1,,1,0,1,,1222m m m --+--与1,,1,0,1,,1,222m m m-+--都是模m 的完全剩余系.定理2 设m 是一个正整数，,a b 都为整数，(),1a m =，若x 通过模m 的一个完全剩余系，则ax b +也通过模m 的一个完全剩余系. 证 设x 通过模m 的完全剩余系12,,,m a a a .下面证明ax b +也通过模m 的一个完全剩余系.根据定理1的推论，只需证明12,,,m aa b aa b aa b +++两两对模m 不同余.因12,,,m a a a 是模m 的一个完全剩余系，故由定理1的推论得，12,,,m a a a 两两对模m 不同余.下面用反证法证明12,,,m aa b aa b aa b +++两两对模m 不同余.假设12,,,m aa b aa b aa b +++不是两两对模m 不同余，则其中有两个数对模m 同余，设()mod ,1i j aa b a b m i j m +≡+≤<≤，则()m o d .i j aa a m ≡因(),1a m =，故()m o d .i j a a m ≡这与12,,,m a a a 两两对模m 不同余矛盾.定理3 设()12120,0,,1m m m m >>=，而12,x x 分别通过模12,m m 的一个完全剩余系，则2112m x m x +通过模12m m 的一个完全剩余系.证 当12,x x 分别通过模12,m m 的一个完全剩余系时，2112m x m x +共取了12m m 个整数值，下面证明这12m m 个整数两两对模12m m 不同余.设()2112211212mod m x m x m x m x m m ''''''+≡+， （1） 其中,i i x x '''是i x 所通过的模i m 的完全剩余系中的数，1,2.i =由（1）得，()211221121mod m x m x m x m x m ''''''+≡+，从而()21211mod m x m x m '''≡.因()12,1m m =，故()111mod .x x m '''≡又因11,x x '''是模1m 的完全剩余系中的数，故11.x x '''=同理，22.x x '''= 故当12,x x 分别通过模12,m m 的一个完全剩余系时，2112m x m x +共取了12m m 个整数值，下面证明这12m m 个整数两两对模12m m 不同余.从而由定理1的推论得，这12m m 个整数作成模12m m 的一个完全剩余系. 定义 0,1,,1m -叫做模m 的最小非负完全剩余系；当m 是奇数时，11,,1,0,1,,22m m ----叫做模m 的绝对最小完全剩余系；当m 是偶数时，,,1,0,1,,122m m ---或1,,1,0,1,,22m m-+-叫做模m 的绝对最小完全剩余系. 作业 P57： 1,2,3,4，习题解答1.证明,0,1,,1,0,1,,1,s t s t t x u p v u p v p t s --=+=-=-≤是模s p 的一个完全剩余系。
完系、简系、剩余系 知识扫描若按对某一模m 的余数进行分类，就可以引入所谓的剩余类和完全剩余类的概念。
定义2：设m N +∈，把全体整数按其对模m 的余数r （0≤r ≤m-1）归为一类，记为r k ，每一类()0,1,2,,1r k r m =-均称为模m 的剩余类（又叫同余类），同一类中任一数称为该类中另一类数的剩余。
根据定义，剩余类具有如下性质：()()()}{()()0012101=20,1,2,,13,,,mod .m i j r r Z k k k k k k i j n Z r m n k a b Z a b k a b m -⋃⋃⋃⋃⋂=∅≠∀∈∈-∈∀∈∈⇔≡，而对于，有唯一的，使得对定义3：设0121,,m k k k k -是模m 的全部剩余类，从每个r k 中任取一个数r a ，这m 个数0121,,,,m a a a a -组成的一个组称为模m 的一个完全剩余系，简称完系。
显然，模m 的完全剩余系有无穷多个，但最常用的是下面两个：()10,1,21;m -最小非负剩余系：，， ()221m m k =+最小绝对值剩余系：它随的奇偶性不同而略有不同。
当时，为-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,,k-1关于完全剩余系，有以下判别法：()()()()121121121,,,,1mod ;2,1,,,,,,,,m m i j m m m m a a a a m i j m a a m b m c a a a a m ba c ba c ba c m --⇔≤<≤≡=+++个整数是模的一个完系当时，设为任意整数，若是模的一个完系，则也是模的一个完系。
特别地，任意m 个连续的整数构成模m 的一个剩余系。
设m 为一正整数，由于在0,1,2，…，m-1中与m 互质的数的个数是由m 唯一确定的一个正整数，因此可以给出以下定义：定义4：m 为一正整数，把0,1,2，…，m-1中与m 互质的数的个数叫做m 的欧拉函数，记为()m 。
完系、简系、剩余类定义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.。
