第二節(jié) 完全剩余系

1、初等數(shù)論 第二章 同 余第二節(jié) 完全剩余系由帶余數(shù)除法我們知道，對于給定的正整數(shù)m，可以將所有的整數(shù)按照被m除的余數(shù)分成m類。本節(jié)將對此作進一步的研究。一、知識與方法定義1 給定正整數(shù)m，對于每個整數(shù)i，0 £ i £ m - 1，稱集合Ri(m) = n|n º i (mod m)，nÎZ 是模m的一個剩余類。顯然，每個整數(shù)必定屬于且僅屬于某一個Ri(m)（0 £ i £ m - 1），而且，屬于同一剩余類的任何兩個整數(shù)對模m是同余的，不同剩余類中的任何兩個整數(shù)對模m是不同余的。例如，模 5的五個剩余類是R0(5) = L , -1

2、0, -5, 0 , 5, 10, L ，R1(5) = L , -9 , -4 , 1 , 6 , 11, L ，R2(5) = L , -8 , -3 , 2 , 7 , 12, L ，R3(5) = L , -7 , -2 , 3 , 8 , 13, L ，R4(5) = L , -6 , -1 , 4 , 9 , 14, L 。定義2 設m是正整數(shù)，從模m的每一個剩余類中任取一個數(shù)xi（0 £ i £ m - 1），稱集合x0, x1, L,xm - 1是模m的一個完全剩余系（或簡稱為完全系）。由于xi的選取是任意的，所以模m的完全剩余系有無窮多個，通常稱() 0,

3、 1, 2, L, m - 1是模m的最小非負完全剩余系；() 或,是模m的絕對最小完全剩余系。例如，集合0, 6, 7, 13, 24是模5的一個完全剩余系，集合0, 1, 2, 3, 4是模5的最小非負完全剩余系。定理1 整數(shù)集合A是模m的完全剩余系的充要條件是() A中含有m個整數(shù)；() A中任何兩個整數(shù)對模m不同余。【證明】定理2 設m ³ 1，a，b是整數(shù)，(a, m) = 1，x1, x2, L, xm是模m的一個完全剩余系，則ax1 + b, ax2 + b, L, axm + b也是模m的一個完全剩余系。【證明】 由定理1，只需證明：若xi ¹ xj，則ax

4、i + baxj + b (mod m)。 (1)事實上，若axi + b º axj + b (mod m)，則axi º axj (mod m)，由此及第一節(jié)定理5得到xi º xj (mod m)，因此xi = xj。所以式(1)必定成立。證畢。定理3 設m1, m2ÎN，AÎZ，(A, m1) = 1，又設，分別是模m1與模m2的完全剩余系，則R = Ax + m1y；xÎX，yÎY 是模m1m2的一個完全剩余系?！咀C明】 由定理1只需證明：若x ¢, x ¢¢ÎX，y

5、62;, y ¢¢ÎY，并且Ax ¢ + m1y ¢ º Ax ¢¢ + m1y ¢¢ (mod m1m2)， (2)則 x ¢ = x ¢¢，y ¢ = y ¢¢事實上，由第一節(jié)定理5及式(2)，有Ax ¢ º Ax ¢¢ (mod m1) Þ x ¢ º x ¢¢ (mod m1) Þ x ¢ = x ¢¢

6、;，再由式(2)，又推出m1y ¢ º m1y ¢¢ (mod m1m2) Þ y ¢ º y ¢¢ (mod m2) Þ y ¢ = y ¢¢ 。證畢。推論 若m1, m2ÎN，(m1, m2) = 1，則當x1與x2分別通過模m1與模m2的完全剩余系時，m2x1 + m1x2通過模m1m2的完全剩余系。定理4 設miÎN（1 £ i £ n），則當xi通過模mi（1 £ i £ n）的完全剩余系時，x

7、= x1 + m1x2 + m1m2x3 + L + m1m2Lmn - 1xn通過模m1m2Lmn的完全剩余系?！咀C明】 對n施行歸納法。當n = 2時，由定理3知定理結(jié)論成立。假設定理結(jié)論當n = k時成立，即當xi（2 £ i £ k + 1）分別通過模mi的完全剩余系時，y = x2 + m2x3 + m2m3x4 + L + m2Lmkxk + 1通過模m2m3Lmk + 1的完全剩余系。由定理3，當x1通過模m1的完全剩余系，xi（2 £ i £ k + 1）通過模mi的完全剩余系時，x1 + m1y = x1 + m1(x2 + m2x3

8、+ L + m2Lmkxk + 1)= x1 + m1x2 + m1m2x3 + L + m1m2Lmkxk + 1通過模m1m2Lmk + 1的完全剩余系。即定理結(jié)論對于n = k + 1也成立。定理由歸納法得證。證畢。定理5 設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 ¹

9、j 。則當xi（1 £ i £ n）通過模mi的完全剩余系Xi時，y = A1x1 + A2x2 + L + Anxn通過模m1m2Lmn的完全剩余系?！咀C明】由定理1只需證明：若xi¢, xi¢¢ÎXi，1 £ i £ n，則由A1x1¢ + A2x2¢ + L + Anxn¢ º A1x1¢¢ + A2x2¢¢ + L + Anxn¢¢ (mod m1Lmn) (3)可以得到xi¢ = xi¢

10、¢，1 £ i £ n。事實上，由條件()及式(3)易得，對于任意的i，1 £ i £ n，有Aixi¢ º Aixi¢¢ (mod mi)。由此并利用條件()和第一節(jié)定理5推得xi¢ º xi¢¢ (mod mi)，因此xi¢ = xi¢¢。證畢。二、例題講解1.設A = x1, x2, L, xm是模m的一個完全剩余系，以x表示x的小數(shù)部分 證明：若(a, m) = 1，則【證明】 當x通過模m的完全剩余系時，ax + b也通過模m

11、的完全剩余系，因此對于任意的i（1 £ i £ m），axi + b一定與且只與某個整數(shù)j（1 £ j £ m）同余，即存在整數(shù)k，使得axi + b = km + j，（1 £ j £ m）從而2.設p ³ 5是素數(shù)，aÎ 2, 3, L, p - 2 ，則在數(shù)列a，2a，3a，L，(p - 1)a，pa (4) 中有且僅有一個數(shù)b，滿足b º 1 (mod p) (5) 此外，若b = ka，則k ¹ a，kÎ2, 3, L, p - 2。 【解答】 因為(a, p) = 1，所以

12、由定理2，式(4)中的數(shù)構(gòu)成模p的一個完全剩余系，因此必有數(shù)b滿足式(5)設b = ka，那么() k ¹ a，否則，b = a2 º 1 (mod p)，即p½(a + 1)(a - 1)，因此p½a - 1或p½a + 1，這與2 £ a £ p - 2矛盾；() k ¹ 1，否則，b = 1×a º 1 (mod p)，這與2 £ a £ p - 2矛盾；() k ¹ -1，否則，b = -a º 1 (mod p)，這與2 £ a

13、63; p - 2矛盾。若又有k ¢，2 £ k ¢ £ p - 2，使得b º k ¢a (mod p)，則k ¢a º ka (mod p) 因(a, p) = 1，所以k º k ¢ (mod p)，從而p½k - k ¢，這是不可能的。這證明了唯一性。3.(Wilson定理) 設p是素數(shù)，則(p - 1)! º -1 (mod p)?！窘獯稹?不妨設p5。由例2容易推出對于2, 3, L, p - 2，中的每個整數(shù)a，都存在唯一的整數(shù)k，2 £ k £ p - 2，使得 ka º 1 (mod p)。 (6)因此，整數(shù)2, 3, L, p - 2可以兩兩配對使得式(6)成立。所以2×3×L×(p - 2) º 1 (mod p)，從而 1×2×3×L×(p - 2)(p - 1) º p - 1 º -1 (mod p)。4. 設m > 0是偶數(shù)，a1, a2, L, am與b1, b2, L, bm都是模m的完全剩余系，證明：a1 + b1, a2 + b2