2 剩余类及完全剩余系

本文格式为Word版，下载可任意编辑——2剩余类及完全剩余系§2剩余类及完全剩余系

定义设m是一个给定的正整数，Kr?r?0,1,m,?1示所有形如?表

qm?r?q?0,?1,?2,?的整数组成的集合，则称K0,K1,,Km?1是模m的剩余类，则

,Km?1为模m的剩余类.

定理1设m?0,K0,K1,（ⅰ）每一整数必包含于某一个类里，而且只能包含于一个类里；（ⅱ）两个整数x,y属于同一类的充分必要条件是x?y?modm?.

证（ⅰ）设a是任意一个整数，则由带余除法，得a?qm?r,0?r?m，故a?Kr.故每一整数必包含于某一类里.又设

a?Kr,且a?Kr?，这里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?.（ⅱ）设a,b是两个整数，并且都在Kr内，则存在整数q1,q2分别使得

a?q1m?r,b?q2m?r.

故a?b?modm?.

反之，若a?b?modm?，则由同余的定义知，a,b被m除所得的余数一致，设余数都为r?0?r?m?，则a和b都属于同一类Kr.定义在模m的剩余类K0,K1,数a0,a1,各取一数aj?Cj,j?0,1,,Km?1中，

此m个,m?1，

,am?1称为模m的一个完全剩余系.

推论m个整数作成模m的一个完全剩余系的充分必要条件是这m个整数两两对模m不同余.

证充分性设a1,a2,,am是m个两两对模m不同余的整数.由定理1知，每个整数

,Km?1中某一剩余类里，且只能在一个剩余类里.因

,am分别属于不同

70

ai必在模m的m个剩余类K0,K1,a1,a2,,am是m个两两对模m不同余的整数，故有定理1得，a1,a2,

的剩余类，故a1,a2,必要性设a1,a2,,am是模m的一个完全剩余系.

,am是模m的一个完全剩余系，则由完全剩余系的定义得，这m个

,Km?1.由定理1得，a1,a2,,am两两对模m不

数分别属于不同的m个剩余类K0,K1,同余.0,1,,m?1是模m的一个完全剩余系.

m?1m?1,,?1,0,1,,是模m的一个完全剩余系.22mmmmmm当m为偶数时，?,??1,,?1,0,1,,?1与??1,,?1,0,1,,?1,222222当m为奇数时，?都是模m的完全剩余系.

定理2设m是一个正整数，a,b都为整数，?a,m??1，若x通过模m的一个完全剩余系，则ax?b也通过模m的一个完全剩余系.证设x通过模m的完全剩余系a1,a2,,am.下面证明ax?b也通过模m的一个完全

,aam?b两两对模m不同余.

剩余系.根据定理1的推论，只需证明aa1?b,aa2?b,因a1,a2,,am是模m的一个完全剩余系，故由定理1的推论得，a1,a2,,am两两对

模m不同余.下面用反证法证明aa1?b,aa2?b,,aam?b两两对模m不同余.假设

aa1?b,aa2?b,,aam?b不是两两对模m不同余，则其中有两个数对模m同余，设

aai?b?aj?b?modm?,1?i?j?m，则aai?aj?momd?因.?a,m??1，故ai?aj?momd?这与.a1,a2,,am两两对模m不同余矛盾.

定理3设m1?0,m2?0,?m1,m2??1，而x1,x2分别通过模m1,m2的一个完全剩余系，则m2x1?m1x2通过模m1m2的一个完全剩余系.

证当x1,x2分别通过模m1,m2的一个完全剩余系时，m2x1?m1x2共取了m1m2个整数值，下面证明这m1m2个整数两两对模m1m2不同余.设

??m1x2??m2x1???m1x2???modm1m2?，（1）m2x1其中xi?,xi??是xi所通过的模mi的完全剩余系中的数，i?1,2.

??m1x2??m2x1???m1x2???modm1?，从而m2x1??m2x1???modm1?.因由（1）得，m2x171

?m1,m2??1，故x1??x1???modm1?.又因x1?,x1??是模m1的完全剩余系中的数，故x1??x1??.

??x2??.同理，x2故当x1,x2分别通过模m1,m2的一个完全剩余系时，m2x1?m1x2共取了m1m2个整数值，下面证明这m1m2个整数两两对模m1m2不同余.从而由定理1的推论得，这m1m2个整数作成模m1m2的一个完全剩余系.定义0,1,,m?1叫做模m的最小非负完全剩余系；当m是奇数时，

m?1m?1,,?1,0,1,,叫做模m的绝对最小完全剩余系；当m是偶数时，22mmmm?,,?1,0,1,,?1或??1,,?1,0,1,,叫做模m的绝对最小完全剩余系.2222?作业P57：1,2,3,4，

习题解答

1.证明

x?u?ps?tv,u?0,1,是模ps的一个完全剩余系。证易知，当u?0,1,,ps?t?1,v?0,1,,pt?1,t?s

,ps?t?1,v?0,1,,pt?1时，x?u?ps?tv通过ps个整数，下

面证明这ps个整数对模ps两两部同余。

设

u??ps?tv??u???ps?tv???modps?,（1）

其中0?u??ps?t?1,0?u???ps?t?1,0?v??pt?1,0?v???pt?1,则

u??ps?tv??u???ps?tv???modps?t?,u??u???modps?t?.

又因0?u??ps?t?1,0?u???ps?t?1，故u??u??.从而由（1）式得

ps?tv??ps?tv???modps?,v??v???modpt?.

又由0?v??p?1,0?v???p?1得v??v??.

故这p个整数对模p两两不同余，从而它们作成模p的完全剩余系。

72

ssstt2.若m1,m2,的完全剩余系，则

,mk是k个两两互质的正整数，x1,x2,,xk分别通过模m1,m2,,mkM1x1?M2x2?通过模m1m2?Mkxk

,k.。

,k,故

mk?m的完全剩余系，其中m?miMi,i?1,2,证因m1,m2,,mk是k个两两互质的正整数，m?miMi,i?1,2,?mi,Mi??1,i?1,2,当x1,x2,k.

,mk的完全剩余系时，

,xk分别通过模m1,m2,?Mkxk

M1x1?M2x2?通过m1m2设

mk个整数。下证这m1m2mk个整数对模m1m2mk两两不同余。

M1x1??M2x2???Mkxk??M1x1???M2x2????Mkxk???modm?,

其中xi?,xi??是xi所通过的模mi的剩余系中的整数，i?1,2,,k,则

M1x1??M2x2???Mkxk??M1x1???M2x2????Mkxk???modmi?,,k.Mixi??Mixi???modmi?,xi??xi???modmi?,xi??xi??,i?1,2,故这m1m2全剩余系。

3.（ⅰ）证明整数?H,种方法表示成

mk个整数对模m1m2mk两两不同余，从而它们作成模m1m2mk的完

,?1,0,1,?3n?1?1?,H?H??中每一个整数都有而且只有一

3?1???3x1?x0（1）

3nxn?3n?1xn?1?的形状，其中xi??1,0,或1；反之，（1）式中的每一数都??H，并且?H.

（ⅱ）说明应用n?1个特制的砝码，在天平上可以量出1到H中任何一个克（注：原

题此处为“斤〞）数。

证（ⅰ）当xi?i?0,1,个整数值，下证这3设

n?1,n?分别取?1,0,1时，3nxn?3n?1xn?1?n?1?3x1?x0共取了3n?1个整数对模3两两不同余。

73

3nxn??3n?1xn?1???3x1??x0??3nxn???3n?1xn?1???,n,则

?3x1???x0???mod3n?1?,（2）

其中?1?xi??1,?1?xi???1,i?0,1,3nxn??3n?1xn?1???3x1??x0??3nxn???3n?1xn?1????3x1???x0???mod3?,x0??x0???mod3?,x0??x0??.由x0??x0??及（2）式得

3nxn??3n?1xn?1??3n?1xn??3n?2xn?1??3n?1?3x1??3nxn???3n?1xn?1????x1??3n?1xn???3n?2xn?1????x1??3n?1?3x1???mod3n?1?,?x1???mod3n?,?x1???mod3?,

xn??3n?2xn?1??xn???3n?2xn?1???x1??x1???mod3?,x1??x1??.同理可得x2??x2??,因此，在?H,,xn??xn??.故这3n?1个整数作成模3n?1的一个完全剩余系。

,?1,0,1,?3n?1?1?,H?H??中任取一个整数x，存在整数

3?1??xi??1?xi?1?,i?0,1,,n使得

?3x1?x0?mod3n?1?.

x?3nxn?3n?1xn?1?由此得

3n?1x??3nxn?3n?1xn?1?因?1?xi?1,i?0,1,?3x1?x0?.(3)

,n，故

?3???1????1???3?1?1?3?1?H.3?1n?13n?1?1n?H???3???1??3n?1???1??3?13nxn?3n?1xn?1?