2 剩余類及完全剩余系

本文格式為Word版，下載可任意編輯——2剩余類及完全剩余系§2剩余類及完全剩余系

定義設(shè)m是一個(gè)給定的正整數(shù)，Kr?r?0,1,m,?1示所有形如?表

qm?r?q?0,?1,?2,?的整數(shù)組成的集合，則稱K0,K1,,Km?1是模m的剩余類，則

,Km?1為模m的剩余類.

定理1設(shè)m?0,K0,K1,（?。┟恳徽麛?shù)必包含于某一個(gè)類里，而且只能包含于一個(gè)類里；（ⅱ）兩個(gè)整數(shù)x,y屬于同一類的充分必要條件是x?y?modm?.

證（?。┰O(shè)a是任意一個(gè)整數(shù)，則由帶余除法，得a?qm?r,0?r?m，故a?Kr.故每一整數(shù)必包含于某一類里.又設(shè)

a?Kr,且a?Kr?，這里0?r?m,0?r??m，則存在整數(shù)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?.（ⅱ）設(shè)a,b是兩個(gè)整數(shù)，并且都在Kr內(nèi)，則存在整數(shù)q1,q2分別使得

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

故a?b?modm?.

反之，若a?b?modm?，則由同余的定義知，a,b被m除所得的余數(shù)一致，設(shè)余數(shù)都為r?0?r?m?，則a和b都屬于同一類Kr.定義在模m的剩余類K0,K1,數(shù)a0,a1,各取一數(shù)aj?Cj,j?0,1,,Km?1中，

此m個(gè),m?1，

,am?1稱為模m的一個(gè)完全剩余系.

推論m個(gè)整數(shù)作成模m的一個(gè)完全剩余系的充分必要條件是這m個(gè)整數(shù)兩兩對(duì)模m不同余.

證充分性設(shè)a1,a2,,am是m個(gè)兩兩對(duì)模m不同余的整數(shù).由定理1知，每個(gè)整數(shù)

,Km?1中某一剩余類里，且只能在一個(gè)剩余類里.因

,am分別屬于不同

70

ai必在模m的m個(gè)剩余類K0,K1,a1,a2,,am是m個(gè)兩兩對(duì)模m不同余的整數(shù)，故有定理1得，a1,a2,

的剩余類，故a1,a2,必要性設(shè)a1,a2,,am是模m的一個(gè)完全剩余系.

,am是模m的一個(gè)完全剩余系，則由完全剩余系的定義得，這m個(gè)

,Km?1.由定理1得，a1,a2,,am兩兩對(duì)模m不

數(shù)分別屬于不同的m個(gè)剩余類K0,K1,同余.0,1,,m?1是模m的一個(gè)完全剩余系.

m?1m?1,,?1,0,1,,是模m的一個(gè)完全剩余系.22mmmmmm當(dāng)m為偶數(shù)時(shí)，?,??1,,?1,0,1,,?1與??1,,?1,0,1,,?1,222222當(dāng)m為奇數(shù)時(shí)，?都是模m的完全剩余系.

定理2設(shè)m是一個(gè)正整數(shù)，a,b都為整數(shù)，?a,m??1，若x通過模m的一個(gè)完全剩余系，則ax?b也通過模m的一個(gè)完全剩余系.證設(shè)x通過模m的完全剩余系a1,a2,,am.下面證明ax?b也通過模m的一個(gè)完全

,aam?b兩兩對(duì)模m不同余.

剩余系.根據(jù)定理1的推論，只需證明aa1?b,aa2?b,因a1,a2,,am是模m的一個(gè)完全剩余系，故由定理1的推論得，a1,a2,,am兩兩對(duì)

模m不同余.下面用反證法證明aa1?b,aa2?b,,aam?b兩兩對(duì)模m不同余.假設(shè)

aa1?b,aa2?b,,aam?b不是兩兩對(duì)模m不同余，則其中有兩個(gè)數(shù)對(duì)模m同余，設(shè)

aai?b?aj?b?modm?,1?i?j?m，則aai?aj?momd?因.?a,m??1，故ai?aj?momd?這與.a1,a2,,am兩兩對(duì)模m不同余矛盾.

定理3設(shè)m1?0,m2?0,?m1,m2??1，而x1,x2分別通過模m1,m2的一個(gè)完全剩余系，則m2x1?m1x2通過模m1m2的一個(gè)完全剩余系.

證當(dāng)x1,x2分別通過模m1,m2的一個(gè)完全剩余系時(shí)，m2x1?m1x2共取了m1m2個(gè)整數(shù)值，下面證明這m1m2個(gè)整數(shù)兩兩對(duì)模m1m2不同余.設(shè)

??m1x2??m2x1???m1x2???modm1m2?，（1）m2x1其中xi?,xi??是xi所通過的模mi的完全剩余系中的數(shù)，i?1,2.

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

?m1,m2??1，故x1??x1???modm1?.又因x1?,x1??是模m1的完全剩余系中的數(shù)，故x1??x1??.

??x2??.同理，x2故當(dāng)x1,x2分別通過模m1,m2的一個(gè)完全剩余系時(shí)，m2x1?m1x2共取了m1m2個(gè)整數(shù)值，下面證明這m1m2個(gè)整數(shù)兩兩對(duì)模m1m2不同余.從而由定理1的推論得，這m1m2個(gè)整數(shù)作成模m1m2的一個(gè)完全剩余系.定義0,1,,m?1叫做模m的最小非負(fù)完全剩余系；當(dāng)m是奇數(shù)時(shí)，

m?1m?1,,?1,0,1,,叫做模m的絕對(duì)最小完全剩余系；當(dāng)m是偶數(shù)時(shí)，22mmmm?,,?1,0,1,,?1或??1,,?1,0,1,,叫做模m的絕對(duì)最小完全剩余系.2222?作業(yè)P57：1,2,3,4，

習(xí)題解答

1.證明

x?u?ps?tv,u?0,1,是模ps的一個(gè)完全剩余系。證易知，當(dāng)u?0,1,,ps?t?1,v?0,1,,pt?1,t?s

,ps?t?1,v?0,1,,pt?1時(shí)，x?u?ps?tv通過ps個(gè)整數(shù)，下

面證明這ps個(gè)整數(shù)對(duì)模ps兩兩部同余。

設(shè)

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個(gè)整數(shù)對(duì)模p兩兩不同余，從而它們作成模p的完全剩余系。

72

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

,mk是k個(gè)兩兩互質(zhì)的正整數(shù)，x1,x2,,xk分別通過模m1,m2,,mkM1x1?M2x2?通過模m1m2?Mkxk

,k.。

,k,故

mk?m的完全剩余系，其中m?miMi,i?1,2,證因m1,m2,,mk是k個(gè)兩兩互質(zhì)的正整數(shù)，m?miMi,i?1,2,?mi,Mi??1,i?1,2,當(dāng)x1,x2,k.

,mk的完全剩余系時(shí)，

,xk分別通過模m1,m2,?Mkxk

M1x1?M2x2?通過m1m2設(shè)

mk個(gè)整數(shù)。下證這m1m2mk個(gè)整數(shù)對(duì)模m1m2mk兩兩不同余。

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

其中xi?,xi??是xi所通過的模mi的剩余系中的整數(shù)，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.（?。┳C明整數(shù)?H,種方法表示成

mk個(gè)整數(shù)對(duì)模m1m2mk兩兩不同余，從而它們作成模m1m2mk的完

,?1,0,1,?3n?1?1?,H?H??中每一個(gè)整數(shù)都有而且只有一

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

3nxn?3n?1xn?1?的形狀，其中xi??1,0,或1；反之，（1）式中的每一數(shù)都??H，并且?H.

（ⅱ）說明應(yīng)用n?1個(gè)特制的砝碼，在天平上可以量出1到H中任何一個(gè)克（注：原

題此處為“斤〞）數(shù)。

證（?。┊?dāng)xi?i?0,1,個(gè)整數(shù)值，下證這3設(shè)

n?1,n?分別取?1,0,1時(shí)，3nxn?3n?1xn?1?n?1?3x1?x0共取了3n?1個(gè)整數(shù)對(duì)模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個(gè)整數(shù)作成模3n?1的一個(gè)完全剩余系。

,?1,0,1,?3n?1?1?,H?H??中任取一個(gè)整數(shù)x，存在整數(shù)

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?