剩余類與完全剩余系【竹菊書苑】

《剩余類與完全剩余系【竹菊書苑】》由會員分享，可在線閱讀，更多相關《剩余類與完全剩余系【竹菊書苑】（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、3.2 3.2 剩余類與完全剩余系剩余類與完全剩余系 一、剩余類一、剩余類 按余數(shù)的不同對整數(shù)分類按余數(shù)的不同對整數(shù)分類 1,01,mZrZrm 定定義義 給給定定對對每每個個稱稱集集合合 ():(mod)rKmn nrm是模是模m的一個剩余類，的一個剩余類，即即 余數(shù)相同的整數(shù)構成余數(shù)相同的整數(shù)構成m的的一個剩余類。一個剩余類。一個剩余類中任意一個數(shù)稱為它同類一個剩余類中任意一個數(shù)稱為它同類的數(shù)的剩余。的數(shù)的剩余。一個整數(shù)被正整數(shù)一個整數(shù)被正整數(shù)n除后，余數(shù)有除后，余數(shù)有n種情形：種情形：0 0，1 1，2 2，3 3，n-1-1，它們彼此對模，它們彼此對模n不同余。這表明，每個不同余。這表

2、明，每個整數(shù)恰與這整數(shù)恰與這n個整數(shù)中某一個對模個整數(shù)中某一個對模n同余。這樣一來，同余。這樣一來，按模按模n是否同余對整數(shù)集進行分類，可以將整數(shù)集分是否同余對整數(shù)集進行分類，可以將整數(shù)集分成成n個兩兩不相交的子集。個兩兩不相交的子集。1向上教學定理定理1 1().rmZmmK m 設設，則則全全部部整整數(shù)數(shù)分分別別在在模模 的的 個個剩剩余余類類里里 ():(mod)rKmn nrm其其中中，01,rm并并且且(1)()rnKm任任一一整整數(shù)數(shù) 必必包包含含且且僅僅包包含含在在某某個個里里；(2),()(mod).ra bZa bKmabm設設，則則2向上教學二、完全剩余系二、完全剩余系1.

3、1.定義定義2 2 mZm 設設，從從模模 的的每每一一個個剩剩余余類類里里各各取取一一個個 011,01,imximxxxm 數(shù)數(shù)稱稱集集合合是是模模 的的一一個個完完全全剩剩余余系系，簡簡稱稱完完全全系系.注：注：完全剩余系不唯一；完全剩余系不唯一；0,1,2,m 1是模是模m的最小非負完全剩余系；的最小非負完全剩余系；若把剩余系作為一個集合，則可以把對模若把剩余系作為一個集合，則可以把對模m的余的余數(shù)相同的整數(shù)數(shù)相同的整數(shù)即同一剩余類里的整數(shù)，看作同即同一剩余類里的整數(shù)，看作同一元素。一元素。3向上教學完全剩余系舉例：完全剩余系舉例：集合集合0,6,7,13,24是模是模5的一個完全剩余

4、系，的一個完全剩余系，集合集合0,1,2,3,4是模是模5的最小非負完全剩余系。的最小非負完全剩余系。,1,0,1,122mm和和2|1,1,0,1,22mmm當當時時，都是模都是模m的絕對最小完全剩余系。的絕對最小完全剩余系。112,1,0,1,22mmm當當時時，是模是模m的絕對最小完全剩余系。的絕對最小完全剩余系。4向上教學2 2、完全剩余系的構造、完全剩余系的構造定理定理2 2 整數(shù)集合整數(shù)集合A是模是模m的完全剩余系的充要條件是的完全剩余系的充要條件是 A中含有中含有m個整數(shù)；個整數(shù)；A中任何兩個整數(shù)對模中任何兩個整數(shù)對模m不同余。不同余。注：由定理注：由定理1 1及定義及定義2 2

5、易得證。易得證。思考思考：1 1、既然完全剩余系是不唯一的，不同的剩余系、既然完全剩余系是不唯一的，不同的剩余系 之間存在什么關系呢？之間存在什么關系呢？2 2、一個完全剩余系的所有元素通過線性變化、一個完全剩余系的所有元素通過線性變化后，還是完全剩余系嗎？后，還是完全剩余系嗎？5向上教學檢驗：設檢驗：設x1,x2,xm是模是模m的一個完全剩余系，的一個完全剩余系，那么，那么，b+x1,b+x2,b+xm和和 ax1,ax2,a xm是模是模m的一個完全剩余系嗎？的一個完全剩余系嗎？6,2mb5,2mb5,2ma6,2ma6向上教學定理定理3 設設m 1，a，b是整數(shù)，是整數(shù)，(a,m)=1，

6、x1,x2,xm是模是模m的一個完全剩余系，則的一個完全剩余系，則ax1 b,ax2 b,axm b也是模也是模m的完全剩余系。的完全剩余系。證明證明 由定理由定理2，只需證明：若，只需證明：若xi xj，則則 axi b axj b(mod m)。假設假設 axi b axj b(mod m)，則則 axi axj(mod m)，且且(a,m)=1，xi xj(mod m)由由3.13.1中的結論中的結論,P50,P50第三行知：第三行知：.ijxx1,i jm7向上教學注意：注意：(1)(1)在定理在定理3 3中，條件中，條件(a,m)=1不可缺少，否則不能不可缺少，否則不能 成立；成立；

7、(2)定理定理3也可以敘述為：設也可以敘述為：設m 1，a，b是整數(shù)，是整數(shù)，(a,m)=1，若若x通過模通過模m的一個完全剩余系，的一個完全剩余系，則則ax+b也通過模也通過模m的一個完全剩余系；的一個完全剩余系；（3）特別地，若）特別地，若x通過模通過模m的一個完全剩余系，的一個完全剩余系，(a,m)=1，則，則ax和和x+b也分別通過模也分別通過模m的一的一 個完全剩余系。個完全剩余系。8向上教學例例2 設設A=x1,x2,xm是模是模m的一個完全剩余系，的一個完全剩余系，以以x表示表示x的小數(shù)部分，證明：若的小數(shù)部分，證明：若(a,m)=1，則，則 11(1)2miiaxbmm 證：證

8、：當當x通過模通過模m的完全剩余系時，的完全剩余系時，ax b也通過也通過模模m的完全剩余系，的完全剩余系，因此對于任意的因此對于任意的i（1 i m），），axi b一定且只與一定且只與某個整數(shù)某個整數(shù)j（1 j m）同余，）同余，即存在整數(shù)即存在整數(shù)k，使得，使得 axi b=km j，（，（1 j m）11mmiijaxbjkmm 從從而而1 mjjm 11 mjjm 11mjjm 1(1)2m mm 12m .9向上教學3 3、剩余系間的聯(lián)系、剩余系間的聯(lián)系定理定理4 設設m1,m2 N，A Z，(A,m1)=1，121212,mmXx xxYyyy分別是模分別是模m1與模與模m2的完

9、全剩余系，的完全剩余系，則則 R=Ax m1y：x X，y Y 是模是模m1m2的一個的一個完全剩余系。完全剩余系。證明證明 由定理由定理3只需證明：若只需證明：若x ,x X，y ,y Y，且，且Ax m1y Ax m1y (mod m1m2)，12,.xxyyRm m則則中中有有個個元元素素10向上教學例例1 設設p 5是素數(shù)，是素數(shù)，a 2,3,p 1，則，則在數(shù)列在數(shù)列a，2a，3a，(p 1)a，pa中有且僅有中有且僅有一個數(shù)一個數(shù)b，滿足，滿足 b 1(mod p)；證證 ：因為因為1，2，3，(p 1)，p是模是模p的的 一個完全剩余系，一個完全剩余系，(,)1papa p是是素

10、素數(shù)數(shù)，所以所以a，2a，3a，(p 1)a，pa構成模構成模p的的 一個完全剩余系。一個完全剩余系。因此必有唯一的數(shù)因此必有唯一的數(shù)b滿足式滿足式b 1(mod p)。11向上教學定理定理4 設設m1,m2 N，A Z，(A,m1)=1，121212,mmXx xxYyyy分別是模分別是模m1與模與模m2的完全剩余系，的完全剩余系，則則 R=Ax m1y：x X，y Y 是模是模m1m2的一個的一個1111m m ym m y由由，所所以以Ax Ax (mod m1)x x (mod m1)x =x ，m1y m1y (mod m1m2)y y (mod m2)y =y 。證：證：Ax m1

11、y Ax m1y (mod m1m2)，Ax m1y Ax m1y (mod m1)，由由x =x ，Ax m1y Ax m1y (mod m1m2)，12向上教學推論推論 若若m1,m2 N，(m1,m2)=1，當當x1與與x2分別通過分別通過 模模m1與模與模m2的完全剩余系時，的完全剩余系時，則則 m2x1 m1x2通過模通過模m1m2的完全剩余系。的完全剩余系。24.Am 注注：即即在在定定理理 中中取取13向上教學證：證：由定理由定理3只需證明，若只需證明，若xi,xiXi，1 i n，A1x1 A2x2 Anxn A1x1 A2x2 Anxn (mod m1mn)則則 可以得到可以

12、得到 xi =xi，1 i n.事實上，由條件事實上，由條件3假設易得，假設易得，對于任意的對于任意的i，1 i n，有，有Aixi Aixi (mod mi)證明方法同定理證明方法同定理4。再利用條件再利用條件2推得推得 xi xi (mod mi)，因此因此xi =xi.14向上教學111103121,1,0,1,3 13331,01nnnnniHH HxxxxxnH 例、（）證明中每一個整數(shù)有而且只有一種方法表示成的形狀，其中或.(2)說明應用+1個特制的砝碼，在天平上可以量出1到 中的任何一個斤數(shù).15向上教學111311,1,0,1,3 1212131213.3 1nnnHH HHH

13、HH（）證:首先包含個不同的整數(shù)，是模的絕對最小完全剩余系，且由得1111333nnnnnxxxx其次，要證明也是模3=2H+1的絕對最小完全剩余系。（再由模2H+1的絕對最小完全剩余系具有唯一性得到結論）16向上教學11101111033311,0,1(0,1,1)333333nnnniiinnnnnxxxxnxinxxxxx 共有項，當時，每一項各取 個值，故共通過個數(shù)；111110110100111100003333=3333()3()3()3nnnnnnnnnnnnnnnxxxxxxxxxxxxxxxxxxxx在這個數(shù)中，若有則17向上教學2211,3,3,3.nn解：（）特制個砝碼分

14、別重斤將要稱的物體放在天平的左托盤，將若干個砝碼放在右托盤，為達到平衡，可以在左托盤放上若干砝碼1111,11333iiinnnnxxxTxxxx這時左托盤里的砝碼 取右托盤里的砝碼取，由（）知，當 取適當?shù)闹禃r，可使之值為所要稱的物體的斤數(shù)。18向上教學121111111122+13()3()()=03=3nnnnnnnnnxxxxxxxxxxxxxx從而同理，即此個數(shù)中，兩兩互不相同；+1111111031333113331333,21nnnnnnnnnnHHxxxxHHH 此個 數(shù) 中，最 大 值 為3最 小 值 為-3即通 過中 的個 整 數(shù)，結 論 成 立。19向上教學定理定理5 設

15、設mi N，Ai Z（1 i n），并且滿足：），并且滿足：(mi,mj)=1，1 i,j n，i j；(Ai,mi)=1，1 i n；mi Aj，1 i,j n，i j。則當則當xi（1 i n）通過模）通過模mi的完全剩余系的完全剩余系Xi時，時，y=A1x1 A2x2 Anxn 通過模通過模m1m2mn的的完全剩余系。完全剩余系。20向上教學例例3 設設m 0是偶數(shù)，是偶數(shù)，a1,a2,am與與b1,b2,bm都是模都是模m的完全剩余系，的完全剩余系，則則a1 b1,a2 b2,am bm不是模不是模m的完全剩余系。的完全剩余系。證證 由由1,2,m與與a1,a2,am都是模都是模m的完

16、全剩余系，的完全剩余系，11(1)(mod)22mmiiim mmaim 所所以以，1(mod)2miimbm 同同理理，如果如果a1 b1,a2 b2,am bm是模是模m的完全剩余系，的完全剩余系，1()(mod)2miiimabm 則則1110()(mod)2222mmmiiiiiiimmmm=ababm 從從而而不可能！不可能！21向上教學例例4 設設mi N（1 i n），則當），則當xi通過模通過模mi（1 i n）的完全剩余系時，的完全剩余系時，x=x1 m1x2 m1m2x3 m1m2mn 1xn通過模通過模m1m2mn的完全剩余系。的完全剩余系。證明證明 對對n施行歸納法。施

17、行歸納法。當當n=2時，由定理時，由定理4知定理結論成立。知定理結論成立。假設定理結論當假設定理結論當n=k時成立，時成立，即當即當xi（2 i k 1）分別通過模）分別通過模mi的完全剩余系時，的完全剩余系時，y=x2 m2x3 m2m3x4 m2mkxk 1通過模通過模m2m3mk 1的完全剩余系。的完全剩余系。22向上教學y=x2 m2x3 m2m3x4 m2mkxk 1通過模通過模m2m3mk 1的完全剩余系。的完全剩余系。由定理由定理4，當，當x1通過模通過模m1的完全剩余系，的完全剩余系，xi（2 i k 1）通過模）通過模mi的完全剩余系時，的完全剩余系時，x1 m1y=x1 m

18、1(x2 m2x3 m2mkxk 1)=x1 m1x2 m1m2x3 m1m2mkxk 1通過模通過模m1m2mk 1的完全剩余系。的完全剩余系。即結論對于即結論對于n=k 1也成立。也成立。23向上教學三、與抽象代數(shù)的關系三、與抽象代數(shù)的關系若將模若將模m的剩余類作為元素，則的剩余類作為元素，則 同余同余剩余類的相等，剩余類的相等，同余的運算同余的運算元素剩余類的運算，元素剩余類的運算，剩余類的集合即是環(huán)。剩余類的集合即是環(huán)。特別地，當特別地，當m為合數(shù)時，就有：為合數(shù)時，就有：非零的剩余類的乘積可能為零的剩余類，非零的剩余類的乘積可能為零的剩余類，即存在零因子的環(huán)。即存在零因子的環(huán)。上述環(huán)中所有與模上述環(huán)中所有與模m互質(zhì)的剩余類對乘法構成群；互質(zhì)的剩余類對乘法構成群；當當m為質(zhì)數(shù)時，上述的環(huán)又可以構成一個有限域。為質(zhì)數(shù)時，上述的環(huán)又可以構成一個有限域。24向上教學