1、第二節(jié) 剩余類與完全剩余系第三節(jié) 縮系教學(xué)目的：1、掌握剩余類與完全剩余系的定義與基本性質(zhì)；2、掌握縮系的定義與基本性質(zhì)；3、證明及應(yīng)用Wilson定理；4、證明及應(yīng)用Fermat小定理、Euler定理的證明及應(yīng)用；5、掌握Euler函數(shù)計(jì)算方法及其基本性質(zhì).教學(xué)重點(diǎn)：1、剩余類與完全剩余系的基本性質(zhì)；2、證明及應(yīng)用Wilson定理；3、證明及應(yīng)用Fermat小定理；4、掌握Euler函數(shù)計(jì)算方法及其基本性質(zhì).教學(xué)課時(shí)：8課時(shí)教學(xué)過程一、剩余類與完全剩余系由上一節(jié)我們知道，同余關(guān)系滿足自反性、對稱性、傳遞性，即對于整數(shù)集來說，同余是一個(gè)等價(jià)關(guān)系. 這樣，可以按同余關(guān)系將所有的整數(shù)分類.1、定義

2、1 給定正整數(shù)m，對于每個(gè)整數(shù)i，0 i m - 1，稱集合 Ki(m) = n；n i (mod m)，nZ 是模m的一個(gè)剩余類.顯然，每個(gè)整數(shù)必定屬于且僅屬于某一個(gè)Ki(m)（0 i m - 1），而且，屬于同一剩余類的任何兩個(gè)整數(shù)對模m是同余的，不同剩余類中的任何兩個(gè)整數(shù)對模m是不同余的.例如，模 5的五個(gè)剩余類是K0(5) = L , -10, -5, 0 , 5, 10, L ，K1(5) = L , -9 , -4 , 1 , 6 , 11, L ，K2(5) = L , -8 , -3 , 2 , 7 , 12, L ，K3(5) = L , -7 , -2 , 3 , 8 ,

3、13, L ，K4(5) = L , -6 , -1 , 4 , 9 , 14, L .2、定義2 設(shè)m是正整數(shù)，從模m的每一個(gè)剩余類中任取一個(gè)數(shù)xi（0 i m - 1），稱集合x0, x1, L,xm - 1是模m的一個(gè)完全剩余系（或簡稱為完全系）.由于xi的選取是任意的，所以模m的完全剩余系有無窮多個(gè)，通常稱() 0, 1, 2, L, m - 1是模m的最小非負(fù)完全剩余系；() 或是模m的絕對最小完全剩余系.例如，集合0, 6, 7, 13, 24是模5的一個(gè)完全剩余系，集合0, 1, 2, 3, 4是模5的最小非負(fù)完全剩余系.3、定理1 整數(shù)集合A是模m的完全剩余系的充要條件是()

4、A中含有m個(gè)整數(shù)；() A中任何兩個(gè)整數(shù)對模m不同余.4、定理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，則axi + baxj + b (mod m). (1)事實(shí)上，若axi + b axj + b (mod m)，則axi axj (mod m)，由此得到 xi xj (mod m)，因此xi = xj. 所以式(1)必定成立. 證畢 5、定理3 設(shè)m1, m2N，AZ，(A, m1) = 1，又設(shè)，分別是模m

5、1與模m2的完全剩余系，則R = Ax + m1y；xX，yY 是模m1m2的一個(gè)完全剩余系.證明：由定理1只需證明：若x , x X，y , 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 ，再由式(2)，又推出m1y m1y (mod m2) y y (mod m2) y = y .推論 若m1, m2N，(m1, m2) = 1，則當(dāng)x1與x2分別通過模m1與模m2的完全剩余系時(shí)，m2x1 + m1x2通過模m1m2的完全剩

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

7、x1 + m1(x2 + m2x3 + L + m2Lmkxk + 1)= x1 + m1x2 + m1m2x3 + L + m1m2Lmkxk + 1通過模m1m2Lmk + 1的完全剩余系. 即定理結(jié)論對于n = k + 1也成立.7、定理5 設(shè)miN，AiZ（1 i n），并且滿足下面的條件：() (mi, mj) = 1，1 i, j n，i j；() (Ai, mi) = 1，1 i n；() miAj ，1 i, j n，i j .則當(dāng)xi（1 i n）通過模mi的完全剩余系Xi時(shí)，y = A1x1 + A2x2 + L + Anxn通過模m1m2Lmn的完全剩余系.證明：由定理1

8、只需證明：若xi, xiXi，1 i n，則由A1x1 + A2x2 + L + Anxn A1x1 + A2x2 + L + Anxn (mod m1Lmn) (3)可以得到xi = xi，1 i n.事實(shí)上，由條件()及式(3)易得，對于任意的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通過模m的完全剩余系時(shí)，ax + b也通過模m的完全剩余系，因此對于任意的i（1

9、 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，k2, 3, L, p - 2.解：因?yàn)?a, p) = 1，所以由定理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

10、a - 1或pa + 1，這與2 a p - 2矛盾；() k 1，否則，b = 1a 1 (mod p)，這與2 a p - 2矛盾；() k -1，否則，b = -a 1 (mod p)，這與2 a p - 2矛盾.若又有k ，2 k p - 2，使得b k a (mod p)，則k a ka (mod p).因(a, p) = 1，所以k k (mod p)，從而pk - k ，這是不可能的. 這證明了唯一性.8、定理6 (Wilson定理) 設(shè)p是素?cái)?shù)，則(p - 1)! -1 (mod p).證：不妨設(shè)p5. 由例2容易推出對于2, 3, L, p - 2，中的每個(gè)整數(shù)a，都存在唯一

11、的整數(shù)k，2 k p - 2，使得ka 1 (mod p). (6)因此，整數(shù)2, 3, L, p - 2可以兩兩配對使得式(6)成立. 所以23L(p - 2) 1 (mod p)，從而123L(p - 2)(p - 1) p - 1 -1 (mod p).例3 設(shè)m 0是偶數(shù)，a1, a2, L, am與b1, b2, L, bm都是模m的完全剩余系，證明：a1 + b1, a2 + b2, L, am + bm不是模m的完全剩余系.解：因?yàn)?, 2, L, m與a1, a2, L, am都是模m的完全剩余系，所以(mod m). (7)同理(mod m). (8)如果a1 + b1, a

12、2 + b2, L, am + bm是模m的完全剩余系，那么也有(mod m).聯(lián)合上式與式(7)和式(8)，得到0(mod m)，這是不可能的，所以a1 + b1, a2 + b2, L, am + bm不能是模m的完全剩余系.二、縮系在模m的完全剩余系中，與m互素的整數(shù)所成的集合有一些特殊的性質(zhì)，我們下面對它們做些研究.1、定義1 設(shè)R是模m的一個(gè)剩余類，若有aR，使得(a, m) = 1，則稱R是模m的一個(gè)簡化剩余類.顯然，若R是模的簡化剩余類，則R中的每個(gè)整數(shù)都與m互素.例如，模4的簡化剩余類有兩個(gè)：R1(4) = L, -7 , -3, 1 , 5 , 9 , L ，R3(4) =

13、L, -5 , -1 , 3 , 7 , 11 , L .2、定義2 對于正整數(shù)k，令函數(shù)j(k)的值等于模k的所有簡化剩余類的個(gè)數(shù)，稱j(k)為Euler函數(shù)，或Eulerj函數(shù).例如，容易驗(yàn)證j(2) = 1，j(3) = 2，j(4) = 2，j(7) = 6.顯然，j(m)就是在m的一個(gè)完全剩余系中與m互素的整數(shù)的個(gè)數(shù).3、定義3 對于正整數(shù)m，從模m的每個(gè)簡化剩余類中各取一個(gè)數(shù)xi，構(gòu)成一個(gè)集合x1, x2, L,xj(m)，稱為模m的一個(gè)簡化剩余系（或簡稱為簡化系或縮系）.顯然，由于選取方式的任意性，模m的簡化剩余系有無窮多個(gè).例如，集合9, -5, -3, -1是模8的簡化剩余系

14、，集合1, 3, 5, 7也是模8的簡化剩余系，通常稱最小非負(fù)簡化剩余系.4、定理1 整數(shù)集合A是模m的簡化剩余系的充要條件是() A中含有j(m)個(gè)整數(shù)；() A中的任何兩個(gè)整數(shù)對模m不同余；() A中的每個(gè)整數(shù)都與m互素.5、定理2 設(shè)a是整數(shù)，(a, m) = 1，B = x1, x2, L, xj(m)是模m的簡化剩余系，則集合A = ax1, ax2, L, axj(m)也是模m的一個(gè)縮系.證明 ：顯然，集合A中有j(m)個(gè)整數(shù). 其次，由于(a, m) = 1，所以，對于任意的xi（1 i j(m)），xiB，有(axi, m) = (xi, m) = 1. 因此，A中的每一個(gè)數(shù)都

15、與m互素. 最后，我們指出，A中的任何兩個(gè)不同的整數(shù)對模m不同余. 事實(shí)上，若有x , x B，使得a x ax (mod m)，那么，因?yàn)?a, m) = 1，所以x x (mod m)，于是x = x . 由以上結(jié)論及定理1可知集合A是模m的一個(gè)縮系.注：在定理2的條件下，若b是整數(shù)，集合ax1 + b, ax2 + b, L, axj(m) + b不一定是模m的簡化剩余系.例如，取m = 4，a = 1，b = 1，以及模4的簡化剩余系1, 3.6、定理3 設(shè)m1, m2N，(m1, m2) = 1，又設(shè)分別是模m1與m2的縮系，則A = m1y + m2x；xX，yY 是模m1m2的縮

16、系.證明：若以X 與Y 分別表示模m1與m2的完全剩余系，使得X X ，Y Y ，則A = m1y + m2x；xX ，yY 是模m1m2的完全剩余系. 因此只需證明A 中所有與m1m2互素的整數(shù)的集合R是集合A. 顯然，A A.若m1y + m2xR，則(m1y + m2x, m1m2) = 1，所以(m1y + m2x, m1) = 1，于是 (m2x, m1) = 1，(x, m1) = 1，xX.同理可得到y(tǒng)Y，因此m1y + m2xA. 這說明R A.另一方面，若m1y + m2xA，則xX，yY，即(x, m1) = 1，(y, m2) = 1.由此及(m1, m2) = 1得到(

17、m2x + m1y, m1) = (m2x, m1) = 1以及(m2x + m1y, m2) = (m1y, m2) = 1.因?yàn)閙1與m2互素，所以(m2x + m1y, m1m2) = 1，于是m2x + m1yR. 因此A R. 綜合以上，得到A = R.7、定理4 設(shè)m, nN，(m, n) = 1，則j(mn) = j(m)j(n).證明：這是定理3的直接推論.8、定理5 設(shè)n是正整數(shù)，p1, p2, L, pk是它的全部素因數(shù)，則j(n) =.證明：設(shè)n的標(biāo)準(zhǔn)分解式是n =，由定理4得到j(luò)(n) =. (1)對任意的素?cái)?shù)p，j(pa)等于數(shù)列1, 2, L, pa中與pa（也就是

18、與p）互素的整數(shù)的個(gè)數(shù)，因此j(pa) = pa -，將上式與式(1)聯(lián)合，證明了定理.由定理5可知，j(n) = 1的充要條件是n = 1或2.例1 設(shè)整數(shù)n 2，證明：nj(n)，即在數(shù)列1, 2, L, n中，與n互素的整數(shù)之和是nj(n).解：設(shè)在1, 2, L, n中與n互素的j(n)個(gè)數(shù)是a1, a2, L, aj(n)，(ai, n) = 1，1 ai n - 1，1 i j(n)，則 (n - ai, n) = 1，1 n - ai n - 1，1 i j(n)，因此，集合a1, a2, L, aj(n)與集合n - a1, n - a2, L, n - aj(n)是相同的，于

19、是 a1 + a2 + L + aj(n) = (n - a1) + (n - a2) + L + (n - aj(n)，2(a1 + a2 + L + aj(n) = nj(n)，因此 a1 + a2 + L + aj(n) =nj(n).例2 設(shè)n是正整數(shù)，則= n，此處是對n的所有正約數(shù)求和.解：將正整數(shù)1, 2, L, n按它們與整數(shù)n的最大的公約數(shù)分類，則n =.例3 設(shè)nN，證明：() 若n是奇數(shù)，則j(4n) = 2j(n)；() j(n) =的充要條件是n = 2k，kN；() j(n) =的充要條件是n = 2k3l，k, lN；() 若6n，則j(n) ；() 若n - 1

20、與n + 1都是素?cái)?shù)，n 4，則j(n) .解： () 我們有j(4n) = j(22n) = j(22)j(n) = 2j(n)；() 若n = 2k，則j(2k) =，若j(n) =，設(shè)n = 2kn1，2n1，則由= j(n) = j(2kn1) = j(2k)j(n1) =2k - 1j(n1) =推出j(n1) = n1，所以n1 = 1，即n = 2k；() 若n = 2k3l，則j(n) = j(2k)j(3l) =.若j(n) =，設(shè)n = 2k3ln1，6n1，則由推出j(n1) = n1，所以n1 = 1，即n = 2k3l；() 設(shè)n = 2k3ln1，6n1，則j(n)

21、 = j(2k)j(3l)j(n1) =；() 因?yàn)閚 4，所以n - 1與n + 1都是奇素?cái)?shù)，所以n是偶數(shù).因?yàn)閚 - 1 3，所以n - 1與n + 1都不等于3，當(dāng)然不被3整除，所以3n，因此6n.再由上面已經(jīng)證明的結(jié)論()，即可得到結(jié)論().例4 證明：若m, nN，則j(mn) = (m, n)j(m, n)；解：顯然mn與m, n有相同的素因數(shù)，設(shè)它們是pi（1 i k），則由此兩式及mn = (m, n)m, n即可得證.三、Euler定理與Fermat小定理1、定理1(Euler) 設(shè)m是正整數(shù)，(a, m) = 1，則aj(m) 1 (mod m).證明：由第三節(jié)定理2，設(shè)

22、x1, x2, L, xj(m)是模m的一個(gè)簡化剩余系，則ax1, ax2, L, axj(m)也是模m的簡化剩余系，因此ax1ax2Laxj(m) x1x2, Lxj(m) (mod m)，aj(m)x1x2Lxj(m) x1x2, Lxj(m) (mod m). (1)由于(x1x2Lxj(m), m) = 1，所以由式(1)得出aj(m) 1 (mod m).2、定理2(Fermat) 設(shè)p是素?cái)?shù)，則對于任意的整數(shù)a，有a p a (mod p).證明：若(a, p) = 1，則由定理1得到a p - 1 1 (mod p) a p a (mod p).若(a, p) 1，則pa，所以a

23、 p 0 a (mod p).例1 設(shè)n是正整數(shù)，則51n + 2n + 3n + 4n的充要條件是4n.解 因?yàn)閖(5) = 4，所以，由定理2k4 1 (mod 5)，1 k 4.因此，若n = 4q + r，0 r 3，則1n + 2n + 3n + 4n 1r + 2r + 3r + 4r 1r + 2r + (-2)r + (-1)r (mod 5)，(2)用r = 0，1，2，3，4分別代入式(2)即可得出所需結(jié)論.例2 設(shè)x1, x2, L, xj(m)是模m的簡化剩余系，則(x1x2Lxj(m)2 1 (mod m).解 記P = x1x2Lxj(m)，則(P, m) = 1.

24、又記yi =，1 i j(m)，則y1, y2, L, yj(m)也是模m的簡化剩余系，因此(mod m)，再由Euler定理，推出P2 Pj(m) 1 (mod m).例3 設(shè)(a, m) = 1，d0是使a d 1 (mod m)成立的最小正整數(shù)，則() d0j(m)；() 對于任意的i，j，0 i, j d0 - 1，i j，有a ia j (mod m). (3)解： () 由Euler定理，d0 j(m)，因此，由帶余數(shù)除法，有j(m) = qd0 + r，qZ，q 0，0 r d0.因此，由上式及d0的定義，利用定理1，我們得到1 (mod m)，即整數(shù)r滿足a r 1 (mod

25、m)，0 r j.因?yàn)?a, m) = 1，所以ai - j 0 (mod m)，0 i - j 1，(b, m) = 1，并且b a 1 (mod m)，b c 1 (mod m)， (4)記d = (a, c)，則bd 1 (mod m).解：利用輾轉(zhuǎn)相除法可以求出整數(shù)x，y，使得ax + cy = d，顯然xy 0，y 0，由式(4)知1 b ax = b db -cy = b d(b c) -y b d (mod m).若x 0，由式(4)知1 b cy = b db -ax = b d(ba) -x b d (mod m).例5 設(shè)p是素?cái)?shù)，pbn - 1，nN，則下面的兩個(gè)結(jié)論中至少有一個(gè)成立：() pbd - 1對于n的某個(gè)因數(shù)d 2，則()中的mod n可以改為mod 2n.解：記d = (n, p - 1)，由b n 1，b p - 1 1 (mod p)，及例題4，有b d 1 (mod p).若d 2，則p 1 (mod 2).由此及結(jié)論()，并利用同余的基本性質(zhì)，得到p 1 (mod 2n).注：例5提供了一個(gè)求