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

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

2、12,R3(5)=, 7 ,2,3,8,13,R4(5)= , 6 ,1 , 4,9,14,。定義2設(shè)m是正整數(shù)，從模m的每一個(gè)剩余類中任取一個(gè)數(shù)Xi (0 im 1),稱集合xo, xi, ,xm 1是模m的一個(gè)完全剩余系(或簡稱為完全系)。由于Xi的選取是任意的，所以模m的完全剩余系有無窮多個(gè)，通常稱(i )0, 1,2, m 1是模m的最小非負(fù)完全剩余系；(11) ? , “1 爭(當(dāng) 2口)或1,0,1,心(當(dāng)2|m),是模m的絕對最小完全剩余系。2例如，集合0, 6, 7, 13, 24是模5的一個(gè)完全剩余系，集合0, 1,2, 3, 4是模5的最小非 負(fù)完全剩余系。定理1整數(shù)集合A

3、是模m的完全剩余系的充要條件是(i ) A中含有m個(gè)整數(shù)；(1) A中任何兩個(gè)整數(shù)對模 m不同余。I. A是棋僭的完全軻余慕*乩熱成立*反Z.満足(i)當(dāng)ii 【證明】 術(shù) 創(chuàng)數(shù)必莎別來自卜欖w的毎 個(gè)半同的剌余類腳足悅卿的完全幕余鼠定理2設(shè)m 1, a, b是整數(shù)，(a, m) = 1 , X1, X2, , xm是模m的一個(gè)完全剩余系， 則ax1 b, ax2 b, , axm b也是模m的一個(gè)完全剩余系?！咀C明】 由定理1,只需證明：若Xi xj，則axi b axj b (mod m)。(1)事實(shí)上，若 axi b axj b (mod m),貝V axi axj (mod m),由此

4、及第一節(jié)定理 5得到Xi xj (mod m),因此xi = xj。所以式(1)必定成立。證畢。定理 3 設(shè) m1, m2 N , A Z, (A, m” = 1，又設(shè)X Xi，X2，,Xmi , Y %,丫2，, ym2,分別是模mi與模m2的完全剩余系，貝yR = Ax miy; x X, y Y 是模mim2的一個(gè)完全剩余系?！咀C明】由定理1只需證明：若x , x X, y , y Y,并且Ax miy Ax miy (mod mim2)，(2)貝 Ux = x ， y = y事實(shí)上，由第一節(jié)定理5及式(2)，有Ax Ax (mod mi)x x (mod mi)x = x ,再由式(2

5、),又推出miy miy (mod mim2)y y (mod m2)y = y 。證畢。推論 若mi, m2 N, (mi, m2) = i ,則當(dāng)xi與X2分別通過模 mi與模m2的完全剩余系時(shí)， m2xi mi x2通過模mi m2的完全剩余系。定理4 設(shè)mi N (i i n),則當(dāng)Xi通過模mi (i i n)的完全剩余系時(shí)，mim2mnixnk i)分別通過模 mi的完全剩余系時(shí),x = xi mix2 mim2X3通過模mim2 mn的完全剩余系?！咀C明】 對n施行歸納法。當(dāng)n = 2時(shí)，由定理3知定理結(jié)論成立。假設(shè)定理結(jié)論當(dāng)n = k時(shí)成立，即當(dāng)Xi( 2 iy = X2 m2

6、X3 m2m3X4m2 mkXk i通過模m2m3 mk i的完全剩余系。由定理3,當(dāng)xi通過模mi的完全剩余系，x (2 i k i) 通過模mi的完全剩余系時(shí)，xi miy = xi mi(x2 m2X3m2 mkXk i)=xi miX2 mim2X3mim2 mkXk i通過模mim2 mk i的完全剩余系。即定理結(jié)論對于n = k i也成立。定理由歸納法得證。證畢。定理5 設(shè)miN,AiZ (i in),并且滿足下面的條件(i )(mi, mj)=i ,ii, j n,i j ；(i)(Ai, mi)=i ,ii n;(iii)mi Aj ,ii, jn, i j。則當(dāng)Xi( iin

7、)通過模mi的完全剩余系Xi時(shí)，y = AixiA2X2AnXn通過模mi m2mn的完全剩余系?！咀C明】由定理i只需證明：若Xi , XiXi,i i n,則由AixiA2X2AnXnAixiA2X2Anxn (mod mi mn) (3)可以得到Xi =xi , i i n。事實(shí)上，由條件(ii)及式(3)易得，對于任意的i, i i n,有Aixi Aixi (mod mi)。由此并利用條件(ii)和第一節(jié)定理5推得Xi Xi (mod mi),因此 Xi = Xi。證畢。、例題講解i設(shè)A = xi, X2, , xm是模m的一個(gè)完全剩余系，以x表示X的小數(shù)部分m ax b i證明：若(

8、a, m) = 1，貝U i - (m 1)i i m 2【證明】當(dāng)x通過模m的完全剩余系時(shí)，ax b也通過模m的完全剩余系，因此對于任意的i (1 i m), axi b 一定與且只與某個(gè)整數(shù) j (1 j m)同余，即 存在整數(shù)k,使得從而axi b = km j， (1 j m)maxi b1mmkj 1mm j川m 1 j1mm 1丄1m(m 1)m 1j 1 mm222設(shè)p 5是素?cái)?shù)，a 2, 3,p 2 ，則在數(shù)列 a，2a，3a，(p 1)a，pa 中有且僅有一個(gè)數(shù)b，滿足 b 1 (mod p)，p 2。aii 1m i m(m 1)i 12(mod m)。同理如果a1mbi(

9、mod m)。(8)b1, a2b2,am bm是模m的完全剩余系，那么也有m(aib)(mod m)。此外，若 b = ka，則 k a，k 2, 3,【解答】設(shè)b = ka，那么(i ) ka，否則,b =a21 (mod p)，即 p (a1)(a1)，因此p a 1或p a 1，這與2 a p2矛盾；(丘)k1,否則，b =1 a 1 (mod p)，這與 2a p2矛盾；(iii) k1,否則，b=a 1 (mod p)，這與 2a p2矛盾。若又有k，2 k p2，使得 b k a (mod p)，則k aka (mod p)因(a, p)=：1，所以k k(mod p)，從而 p

10、 k k，這是不可能的。這證明了唯一性。因?yàn)?a, p) = 1，所以由定理2，式中的數(shù)構(gòu)成模p的一個(gè)完全剩余系，因此必有數(shù)滿足式(5)3.(Wilson定理)設(shè)p是素?cái)?shù)，則(p 1)!1 (mod p)?！窘獯稹坎环猎O(shè)p 5。由例2容易推出對于2, 3, , p 2，中的每個(gè)整數(shù)a，都存在唯一的整數(shù)k，2 k p 2，使得ka 1 (mod p)。(6)因此，整數(shù)2, 3, p 2可以兩兩配對使得式(6)成立。所以23 (p 2)1 (mod p)，從而 1 2 3 (p 2)(p1) p 11 (mod p)。4.設(shè)m 0是偶數(shù)，a1, a2, , am與 b1, b2, , bm都是模m的完全剩余系，證明：a1 b1, a2 b2, , a