2剩余类及完全剩余系

§2剩余类及完全剩余系定义设m是一个给定的正整数，Kr0,1...』1表示所有形如rqmrq0,1,2,...的整数组成的集合，则称火。,%,…,!^］为模m的剩余类.定理1设m0,K0,K「・..，Km］是模m的剩余类，则〔〕每一整数必包含于*一个类里，而且只能包含于一个类里；〔〕两个整数x,y属于同一类的充分必要条件是xyrodm.证〔〕设3是任意一个整数，则由带余除法，得aqmr,0rm，故aK.r故每一整数必包含于*一类里.又设aK，且aK，这里0rm,0rm,则存在整数q,q使得rr于是，m|rr,m||rr|.但是0|rr|m，故|rr|0,rr0,rr.〔〕设a,b是两个整数，并且都在Kr内，则存在整数％,%分别使得故abrodm.反之，假设abrodm，则由同余的定义知，a,b被m除所得的余数一样，设余数都为rqrm,则a和b都属于同一类K.r定义在模m的剩余类K『K，各取一数ajC『j0,L・.,ni1,此m个数TOC\o"1-5"\h\za,a称为模m的一个完全剩余系.01ml推论m个整数作成模m的一个完全剩余系的充分必要条件是这m个整数两两对模m不同余.证充分性设a,a,...，a是m个两两对模m不同余的整数.由定理1知，每个整数a必12mi在模m的m个剩余类火。,%,…,!^〔中*一剩余类里，且只能在一个剩余类里.因a,a,・..,a是m个两两对模m不同余的整数，故有定理1得，a,a,...，a分别属于不同12m12m的剩余类，故a1?a^.,^是模m的一个完全剩余系.必要性设a1?a^.,^是模m的一个完全剩余系，则由完全剩余系的定义得，这m个数分别属于不同的m个剩余类K,K.由定理1得，a,a,...，a两两对模m不01ml12同余.0,l,...,ni1是模m的一个完全剩余系.当m为奇数时，?,・・・，1,0,1.,..,g是模m的一个完全剩余系.,，一,mmm…mm,m当为偶数时，了，5L・・・，LO'hrE1与了L・・・，LO'Lm’eL5都是模m的完全剩余系.定理2设m是一个正整数，a,b都为整数，a,m1,假设x通过模m的一个完全剩余系，则axb也通过模m的一个完全剩余系.证设x通过模m的完全剩余系a1?a2^.,am.下面证明axb也通过模m的一个完全剩余系.根据定理1的推论，只需证明aa1b,aa2b^—aa,b两两对模m不同余.TOC\o"1-5"\h\z因a,a,..・，a是模m的一个完全剩余系，故由定理1的推论得，a,a,...,a两两对12m12m模m不同余.下面用反证法证明aa1b,aa2b,...,&&‘b两两对模m不同余.假设aa1b,aa2如・."&’b不是两两对模m不同余，则其中有两个数对模m同余，设aababmodm,1ijm,ijaaamodm.因a,m1,故ijijaamodm•这与a,a，…，a两两对模,不同余矛盾.ij12m定理3设m0,m0,m,m1,而x,x分别通过模m,m的一个完全剩余系，则12121212mxmx通过模mm的一个完全剩余系.211212证当x,x分别通过模m,m的一个完全剩余系时，mx乂共取了个整数值，1212211212下面证明这mm个整数两两对模mm不同余.设1212〔1〕mxmxmxmxmodmm,〔1〕2112211212其中x,x是x所通过的模m的完全剩余系中的数，i1,2.iiiim,m1,故xxmodm・又因x,x是模m的完全剩余系中的数，故xx.1211111111同理，x2x2.故当x,x分别通过模m,m的一个完全剩余系时，mxmx共取了m个整数值，1212211212下面证明这mm个整数两两对模mm不同余.从而由定理1的推论得，这mm个整数作121212成模mm的一个完全剩余系.12定义0,1叫做模m的最小非负完全剩余系；当m是奇数时，m1m1一、、，…一一一.、，…，1,0,1,•,叫做模m的绝对最小完全剩余系；当m是偶数时，mm…mm一、、，…一,…，1,0,1,・・，51或5L…，1,0,1,・・,了叫做模m的绝对最小完全剩余系.习题解答习题解答作业P57：1,2,3,4,习题解答习题解答upstupstvpstvmodps,〔1〕1.证明是模Ps的一个完全剩余系。证易知，当u0,1,...,pst1,v0,1,...,pt1时，xupstv通过ps个整数，下面证明这ps个整数对模ps两两部同余。其中0upst1,0upst1,0vpt1,0vpt1,则又因0upst1,0upst1,故uu.从而由〔1〕式得又由0vpt1,0vpt1得vv.故这ps个整数对模ps两两不同余，从而它们作成模ps的完全剩余系。TOC\o"1-5"\h\z2.假设m,m,...,m是k个两两互质的正整数，x,x,...，x分别通过模12k12km,m,...,m的完全剩余系，则12k通过模mm...mm的完全剩余系，其中mmM,i1,2,...,k・。12kii证因m,m,・..,m是k个两两互质的正整数，mmM.,i1,2,...，k,故当x,x,...，x分别通过模m,m,...,m的完全剩余系时，通过叩：..气个整数。下证这m.••气个整数对模m.••气两两不同余。设其中x,x是x所通过的模m的剩余系中的整数，i1,2,...,k,则iiii故这m1m2..气个整数对模m1m2••气两两不同余，从而它们作成模mmL*的完全剩余系。3.〔〕证明整数H,...,1,O,1.,..,H3.〔〕证明整数H,...,1,O,1.,..,H3n11 ,中每一个整数都有而且只有一J-L种方法表示成3nx33nx3n1x

n n13x1〔1〕的形状，其中x. 的形状，其中x. 1,0或1；反之，〔1〕式中的每一数都 H，并且H.i〔〕说明应用n1个特制的砝码，在天平上可以量出1到H

题此处为“斤〕数。中任何一个克〔注：原证〔〕当乂ii0,1...,n分别取1,0,1时，3nxn3n1证〔〕当乂ii0,1...,n分别取1,0,1时，3nxn3n1xn3x1x0共取了3n1个整数值，下证这31个整数对模3n1两两不同余。3nx 3n1xn n13xiX3nx3nlX

0 n n13ximod3其中1x1,1i1,i由x0%及〔2〕式得同理可得％.故这3n1个整数作成模同理可得％.故这3n1个整数作成模3n1的一个完全剩余系。3n11r中任取一个整数x存在整数1,iO,1...,n使得由此得3n1x 33n1x 3nx 3nn3xi1,i0,1,…，n,故3n11H3n13nl1...3113nXn3n1Xn1...3xx103n13n11...3113n11H.31又因HxH,故X3nXnX3nX3nn3n1XnIXn1•••1...3xi3xx2H,即10X3n1L〔5〕[0由〔3〕,〔5〕两式得X3片3n1Xn•••13n113xx0.从而10故整数HX3nX3nnHIXn131…3xi中每一个整数X都有表示成X〔6〕.0其中X1,0或1。下证这样的表示方法是唯一的。设还有如下的表示ix3nx3nix...3xx〔7〕nn110其中x1,。成1。则由〔6〕，〔7〕两式得i3nXn3n1x...3xxn1103nX3n1Xnn...3xiiX°.〔8〕由〔8〕式得由xx及〔8〕式得3nX31niix...3x3nxn11n3n1X...n13x.〔9〕i由〔9〕式得同理可得x2XXX.2nn因此，整数H1,0,H3n1131中每一一个整数x都有而且只有一种方法由〔6〕式表示。从〔4〕式还可看出，〔1〕式中的每一数都H,并且H.〔〕用克数分别为1,3,&...，$的n1个特制的硬码，在天平上可以量出1到H中任何一个克数。对于质量在1到H克物体，设其质量为x1xH克，由〔〕，x可以由〔6〕式表示。把物体放在天平的左盘上，对每一个i0in,假设x1就把质量为3i克的那i个砝码放在天平的左盘上，假设X0就不需要质量为3i克的那个砝码，假设x1就把质TOC\o"1-5"\h\zii量为3i克的那个砝码放在天平的右盘上。物体的质量为天平右盘上所有砝码的质量总和减去天平左盘上所有砝码质量总和。4.假设m,m,・..,m是k个正整数，x,x,...，x分别通过模m,m,...,m的完全剩余12k12k12k系，则通过模m1?m^.,^的完全剩余系。证当x,x,...，x分别通过模m,m,...,m的完全剩余系时，12k12k通过m,m,...,m个整数。下证这m,m,...,m个整数对模m,m,...,m两两不同余。12k12k12k设xmxmmx•••mm...mx11212312klk〔1〕xmxmmx•.•mm•.•mxmodmm•.•m,1121231