1、初等數(shù)論 第二章 同 余第二節(jié) 完全剩余系由帶余數(shù)除法我們知道，對(duì)于給定的正整數(shù)m，可以將所有的整數(shù)按照被m除的余數(shù)分成m類(lèi)。本節(jié)將對(duì)此作進(jìn)一步的研究。一、知識(shí)與方法定義1 給定正整數(shù)m，對(duì)于每個(gè)整數(shù)i，0 £ i £ m - 1，稱(chēng)集合Ri(m) = n|n º i (mod m)，nÎZ 是模m的一個(gè)剩余類(lèi)。顯然，每個(gè)整數(shù)必定屬于且僅屬于某一個(gè)Ri(m)（0 £ i £ m - 1），而且，屬于同一剩余類(lèi)的任何兩個(gè)整數(shù)對(duì)模m是同余的，不同剩余類(lèi)中的任何兩個(gè)整數(shù)對(duì)模m是不同余的。例如，模 5的五個(gè)剩余類(lèi)是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 設(shè)m是正整數(shù)，從模m的每一個(gè)剩余類(lèi)中任取一個(gè)數(shù)xi（0 £ i £ m - 1），稱(chēng)集合x(chóng)0, x1, L,xm - 1是模m的一個(gè)完全剩余系（或簡(jiǎn)稱(chēng)為完全系）。由于xi的選取是任意的，所以模m的完全剩余系有無(wú)窮多個(gè)，通常稱(chēng)() 0,

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

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

5、62;, y ¢¢ÎY，并且Ax ¢ + m1y ¢ º Ax ¢¢ + m1y ¢¢ (mod m1m2)， (2)則 x ¢ = x ¢¢，y ¢ = y ¢¢事實(shí)上，由第一節(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，則當(dāng)x1與x2分別通過(guò)模m1與模m2的完全剩余系時(shí)，m2x1 + m1x2通過(guò)模m1m2的完全剩余系。定理4 設(shè)miÎN（1 £ i £ n），則當(dāng)xi通過(guò)模mi（1 £ i £ n）的完全剩余系時(shí)，x

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

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

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

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

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

12、由定理2，式(4)中的數(shù)構(gòu)成模p的一個(gè)完全剩余系，因此必有數(shù)b滿足式(5)設(shè)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定理) 設(shè)p是素?cái)?shù)，則(p - 1)! º -1 (mod p)。【解答】 不妨設(shè)p5。由例2容易推出對(duì)于2, 3, L, p - 2，中的每個(gè)整數(shù)a，都存在唯一的整數(shù)k，2 £ k £ p - 2，使得 ka º 1 (mod p)。 (6)因此，整數(shù)2, 3, L, p - 2可以兩兩配對(duì)使得式(6)成立。所以2×3×L×(p - 2) º 1 (mod p)，從而 1×2×3×L×(p - 2)(p - 1) º p - 1 º -1 (mod p)。4. 設(shè)m > 0是偶數(shù)，a1, a2, L, am與b1, b2, L, bm都是模m的完全剩余系，證明：a1 + b1, a2 + b2