剩余類與完全剩余系優(yōu)秀課件

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

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

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

4、4是模是模5的一個(gè)完全剩余系，的一個(gè)完全剩余系，集合集合0, 1, 2, 3, 4是模是模5的最小非負(fù)完全剩余系。的最小非負(fù)完全剩余系。,1, 0,1,122mm和和2|1,1, 0,1,22mmm 當(dāng)當(dāng)時(shí)時(shí)，都是模都是模m的絕對最小完全剩余系。的絕對最小完全剩余系。112,1, 0,1,22mmm 當(dāng)當(dāng)時(shí)時(shí)，是模是模m的絕對最小完全剩余系。的絕對最小完全剩余系。 52 2、完全剩余系的構(gòu)造、完全剩余系的構(gòu)造定理定理2 2 整數(shù)集合整數(shù)集合A是模是模m的完全剩余系的充要條件是的完全剩余系的充要條件是 A中含有中含有m個(gè)整數(shù)；個(gè)整數(shù)； A中任何兩個(gè)整數(shù)對模中任何兩個(gè)整數(shù)對模m不同余。不同余。注：

5、由定理注：由定理1 1及定義及定義2 2易得證。易得證。思考思考：1 1、既然完全剩余系是不唯一的，不同的剩余系、既然完全剩余系是不唯一的，不同的剩余系 之間存在什么關(guān)系呢？之間存在什么關(guān)系呢？2 2、一個(gè)完全剩余系的所有元素通過線性變化、一個(gè)完全剩余系的所有元素通過線性變化后，還是完全剩余系嗎？后，還是完全剩余系嗎？6檢驗(yàn)：設(shè)檢驗(yàn)：設(shè)x1, x2, , xm是模是模m的一個(gè)完全剩余系，的一個(gè)完全剩余系，那么，那么，b+x1, b+x2, , b+ xm和和 ax1, ax2, ,a xm是模是模m的一個(gè)完全剩余系嗎？的一個(gè)完全剩余系嗎？6,2mb5,2mb5,2ma6,2ma7定理定理3 設(shè)

6、設(shè)m 1，a，b是整數(shù)，是整數(shù)，(a, m) = 1，x1, x2, , xm是模是模m的一個(gè)完全剩余系，則的一個(gè)完全剩余系，則ax1 b, ax2 b, , axm b也是模也是模m的完全剩余系。的完全剩余系。證明證明 由定理由定理2，只需證明：若，只需證明：若xi xj， 則則 axi b axj b (mod m)。 假設(shè)假設(shè) axi b axj b (mod m)，則則 axi axj (mod m)， 且且(a, m) = 1，xi xj (mod m) 由由3.13.1中的結(jié)論中的結(jié)論,P50,P50第三行知：第三行知： .ijxx1, i jm8注意：注意：(1)(1)在定理在定

7、理3 3中，條件中，條件(a, m) = 1不可缺少，否則不能不可缺少，否則不能 成立；成立；(2) 定理定理3也可以敘述為：設(shè)也可以敘述為：設(shè)m 1，a，b是整數(shù)，是整數(shù)，(a, m) = 1，若若x通過模通過模m的一個(gè)完全剩余系，的一個(gè)完全剩余系，則則ax+b也通過模也通過模m的一個(gè)完全剩余系；的一個(gè)完全剩余系；（3）特別地，若）特別地，若x通過模通過模m的一個(gè)完全剩余系，的一個(gè)完全剩余系， (a, m) = 1，則，則ax和和x+b也分別通過模也分別通過模m的一的一 個(gè)完全剩余系。個(gè)完全剩余系。9例例2 設(shè)設(shè)A = x1, x2, , xm是模是模m的一個(gè)完全剩余系，的一個(gè)完全剩余系，以

8、以x表示表示x的小數(shù)部分，證明：若的小數(shù)部分，證明：若(a, m) = 1，則，則 11(1)2miiaxbmm 證：證： 當(dāng)當(dāng)x通過模通過模m的完全剩余系時(shí)，的完全剩余系時(shí)，ax b也通過也通過模模m的完全剩余系，的完全剩余系， 因此對于任意的因此對于任意的i（1 i m），），axi b一定且只與一定且只與某個(gè)整數(shù)某個(gè)整數(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 . .103 3、剩余系間的聯(lián)系、剩余系間的聯(lián)系定

9、理定理4 設(shè)設(shè)m1, m2 N，A Z，(A, m1) = 1，121212,mmXx xxYyyy 分別是模分別是模m1與模與模m2的完全剩余系，的完全剩余系， 則則 R = Ax m1y：x X，y Y 是模是模m1m2的一個(gè)的一個(gè)完全剩余系。完全剩余系。證明證明 由定理由定理3只需證明：若只需證明：若x , x X，y , y Y，且，且Ax m1y Ax m1y (mod m1m2)， 12, .xxyyRm m 則則中中有有個(gè)個(gè)元元素素11例例1 設(shè)設(shè)p 5是素?cái)?shù)，是素?cái)?shù)，a 2, 3, , p 1，則，則在數(shù)列在數(shù)列a，2a，3a，(p 1)a，pa中有且僅有中有且僅有一個(gè)數(shù)一個(gè)數(shù)

10、b，滿足，滿足 b 1 (mod p)；證證 ： 因?yàn)橐驗(yàn)?，2，3，(p 1)，p是模是模p的的 一個(gè)完全剩余系，一個(gè)完全剩余系，( , )1papa p是是素素?cái)?shù)數(shù)，所以所以a，2a，3a，(p 1)a，pa構(gòu)成模構(gòu)成模p的的 一個(gè)完全剩余系。一個(gè)完全剩余系。因此必有唯一的數(shù)因此必有唯一的數(shù)b滿足式滿足式b 1 (mod p)。12定理定理4 設(shè)設(shè)m1, m2 N，A Z，(A, m1) = 1，121212,mmXx xxYyyy 分別是模分別是模m1與模與模m2的完全剩余系，的完全剩余系， 則則 R = Ax m1y：x X，y Y 是模是模m1m2的一個(gè)的一個(gè)1111m m ym m

11、 y由由，所所以以Ax Ax (mod m1) x x (mod m1) x = x ， m1y m1y (mod m1m2) y y (mod m2) y = y 。 證：證：Ax m1y Ax m1y (mod m1m2)， Ax m1y Ax m1y (mod m1)， 由由x = x ， Ax m1y Ax m1y (mod m1m2)，13推論推論 若若m1, m2 N，(m1, m2) = 1，當(dāng)當(dāng)x1與與x2分別通過分別通過 模模m1與模與模m2的完全剩余系時(shí)，的完全剩余系時(shí)， 則則 m2x1 m1x2通過模通過模m1m2的完全剩余系。的完全剩余系。 24.Am 注注：即即在在定

12、定理理 中中取取14證：證： 由定理由定理3只需證明，若只需證明，若xi , xiXi，1 i n， A1x1 A2x2 Anxn A1x1 A2x2 Anxn (mod m1mn) 則則 可以得到可以得到 xi = xi ，1 i n.事實(shí)上，由條件事實(shí)上，由條件3假設(shè)易得，假設(shè)易得， 對于任意的對于任意的i，1 i n，有，有Aixi Aixi (mod mi)證明方法同定理證明方法同定理4。再利用條件再利用條件2推得推得 xi xi (mod mi)，因此因此xi = xi . 1,0,1,3 13331,01nnnnniHH HxxxxxnH 例 、（）證明中

13、每一個(gè)整數(shù)有而且只有一種方法表示成的形狀，其中或 .(2)說明應(yīng)用 +1個(gè)特制的砝碼，在天平上可以量出1到 中的任何一個(gè)斤數(shù).16111311, 1,0,1,3 1212131213.3 1nnnHH HHHHH （）證:首先包含個(gè)不同的整數(shù)，是模的絕對最小完全剩余系，且由得1111333nnnnnxxxx其次，要證明也是模3=2H+1的絕對最小完全剩余系。（再由模2H+1的絕對最小完全剩余系具有唯一性得到結(jié)論）1711101111033311,0,1(0,1,1)333333nnnniiinnnnnxxxxnxinxxxxx 共有項(xiàng)，當(dāng)時(shí)，每一項(xiàng)各取 個(gè)值，故共通過個(gè)數(shù)；1111101101

14、00111100003333=3333 ()3()3()3nnnnnnnnnnnnnnnxxxxxxxxxxxxxxxxxxxx在這個(gè)數(shù)中，若有則182211,3,3 ,3.nn解：（ ）特制個(gè)砝碼分別重斤將要稱的物體放在天平的左托盤，將若干個(gè)砝碼放在右托盤，為達(dá)到平衡，可以在左托盤放上若干砝碼1111,11333iiinnnnxxxTxxxx這時(shí)左托盤里的砝碼 取右托盤里的砝碼取 ，由（）知，當(dāng) 取適當(dāng)?shù)闹禃r(shí)，可使之值為所要稱的物體的斤數(shù)。19121111111122+13()3()()=03=3nnnnnnnnnxxxxxxxxxxxxxx從而同理， ，即此個(gè)數(shù)中，兩兩互不相同；+1111

15、111031333113331333,21nnnnnnnnnnHHxxxxHHH 此個(gè) 數(shù) 中 ， 最 大 值 為3最 小 值 為 - 3即通 過中 的個(gè) 整 數(shù) ， 結(jié) 論 成 立 。20定理定理5 設(shè)設(shè)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 。則當(dāng)則當(dāng)xi（1 i n）通過模）通過模mi的完全剩余系的完全剩余系Xi時(shí)，時(shí)，y = A1x1 A2x2 Anxn 通過模通過模m1m2mn的的完全剩余系。完全剩余系。21例例3 設(shè)設(shè)m 0是偶數(shù)

16、，是偶數(shù)，a1, a2, , am與與b1, b2, , bm都是模都是模m的完全剩余系，的完全剩余系， 則則a1 b1, a2 b2, , am bm不是模不是模m的完全剩余系。的完全剩余系。 證證 由由1, 2, , m與與a1, a2, , am都是模都是模m的完全剩余系，的完全剩余系， 11(1)(mod )22mmiiim mmaim 所所以以，1(mod)2miimbm 同同理理，如果如果a1 b1, a2 b2, , am bm是模是模m的完全剩余系，的完全剩余系， 1()(mod)2miiimabm 則則1110()(mod)2222mmmiiiiiiimmmm=ababm 從

17、從而而不可能！不可能！22例例4 設(shè)設(shè)mi N（1 i n），則當(dāng)），則當(dāng)xi通過模通過模mi（1 i n） 的完全剩余系時(shí)，的完全剩余系時(shí)，x = x1 m1x2 m1m2x3 m1m2mn 1xn通過模通過模m1m2mn的完全剩余系。的完全剩余系。證明證明 對對n施行歸納法。施行歸納法。當(dāng)當(dāng)n = 2時(shí)，由定理時(shí)，由定理4知定理結(jié)論成立。知定理結(jié)論成立。假設(shè)定理結(jié)論當(dāng)假設(shè)定理結(jié)論當(dāng)n = k時(shí)成立，時(shí)成立， 即當(dāng)即當(dāng)xi（2 i k 1）分別通過模）分別通過模mi的完全剩余系時(shí)，的完全剩余系時(shí)，y = x2 m2x3 m2m3x4 m2mkxk 1通過模通過模m2m3mk 1的完全剩余系。的完全剩余系。 23y = x2 m2x3 m2m3x4 m2mkxk 1通過模通過模m2m3mk 1的完全剩余系。的完全剩余系。 由定理由定理4，當(dāng)，當(dāng)x1通過模通過模m1的完全剩余系，的完全剩余系， xi（2 i k 1）通過模）通過模mi的完全剩余系時(shí)，的完全剩余系時(shí)，x1 m1y = x1 m1(x2 m2x3 m2mkxk 1)= x1 m1x2 m1m2x3 m1m2mkxk 1通過模通過模m1m2mk 1的完全剩余系。的完全剩余系。 即結(jié)論對于即結(jié)論對于n = k 1也成立。也成立。 24三、