1、教學目的和要求（1）熟練掌握同余的基本概念及性質(zhì)。（2）熟練掌握剩余類、完全剩余系、簡化剩余系和歐拉函數(shù)的概念及其性質(zhì)。（3）熟練掌握歐拉定理、費馬定理和解某些同余問題。本章是初等數(shù)論的核心內(nèi)容，是學生必須掌握的基礎(chǔ)知識。,第三章同余,1,第三章同余,同余是數(shù)論中的重要概念，同余理論是研究整數(shù)問題的重要工具之一.本章介紹同余的基本概念，剩余類和完全剩余系.,生活中我們經(jīng)常遇到與余數(shù)有關(guān)的問題，比如：某年級有將近400名學生。有一次演出節(jié)目排隊時出現(xiàn)：如果每8人站成一列則多余1人；如果改為每9人站成一列則仍多余1人；如果每10人結(jié)成一列，結(jié)果還是多余1人；聰明的你知道該年級共有學生多少名？,2,

2、中學數(shù)學競賽,1、今天是星期一，再過100天是星期幾？,3、13511，13903，14589被自然數(shù)m除所得余數(shù)相同，問m最大值是多少？,3,一、同余,3.1同余的概念及其基本性質(zhì),1.定義1給定正整數(shù)m，如果用m去除任意的兩個整數(shù)a與b所得的余數(shù)相同，則稱a與b對于模m同余。記為,如果余數(shù)不同，則稱a與b對于模m不同余。記為,注：mod是英語modulo(對模)的縮寫,4,2、判斷a,b對模m同余,定義,3.1同余的概念及其基本性質(zhì),定理1整數(shù)a,b對m同余的充要條件是,注：下面的三個表示是等價的：,5,二、同余的性質(zhì),3、同余關(guān)系是等價關(guān)系,6,二、同余的性質(zhì),7,推廣：,8,5.,9,

3、6.ab(modm)，k0，kN，則1）akbk(modmk)；,7.若ab(modmi)，1ik，則ab(modm1,m2,mk)；,10,8.若ab(modm)，dm，d0，則ab(modd)；,9.若ab(modm)，則(a,m)=(b,m)；,11,12,解：依次計算對模641的同余數(shù),224（mod641）,2416（mod641）,28256（mod641）,13,14,15,例5判斷75312289能否被7（9，11，13）整除。,所以，75312289不能被7（11）整除，能被13整除,16,17,18,例8設(shè)n的十進制表示是,且792n，,求x，y，z.,解因為792=891

4、1，故,8n，9n及11n。,9n9（13xy45z）=19xy,9xy1，(1),11n11（z54yx31）=3yx,11（3yx）。(2),即有xy1=9或18，,3yx=0或11,解方程組，得到x=8，y=0，z=6。,19,五、棄九法驗算計算結(jié)果,應(yīng)用這種方法可以驗算較大整數(shù)的乘法。,例9.驗算28997394951145236415是否正確。,注：若結(jié)論成立，其結(jié)果不一定正確；,所以結(jié)果不正確。,也可以檢查和、差的運算。,20,21,3.2剩余類與完全剩余系,引言,一個整數(shù)被正整數(shù)n除后，余數(shù)有n種情形：0，1，2，3，n-1，它們彼此對模n不同余。這表明，每個整數(shù)恰與這n個整數(shù)中

5、某一個對模n同余。這樣一來，按模n是否同余對整數(shù)集進行分類，可以將整數(shù)集分成n個兩兩不相交的子集。,22,3.2剩余類與完全剩余系,一、剩余類,按余數(shù)的不同對整數(shù)分類,是模m的一個剩余類，,即余數(shù)相同的整數(shù)構(gòu)成m的一個剩余類。,注：一個剩余類中任意一個數(shù)稱為它同類的數(shù)的剩余。,1.剩余類,23,K0(5)=nn0(mod5)，nZK1(5)=nn1(mod5)，nZK2(5)=nn2(mod5)，nZK3(5)=nn3(mod5)，nZK4(5)=nn4(mod5)，nZ,模5的五個剩余類是,24,2.定理1,25,二、完全剩余系,1.定義2,完全剩余系不唯一；,若把剩余系作為一個集合，則同一

6、剩余類里的整數(shù)，看作同一元素。,注：模m的一個完全剩余系有且僅有m個整數(shù)；,26,2.定義3：,集合0,6,7,13,24是模5的一個完全剩余系，,如，集合0,1,2,3,4是模5的最小非負完全剩余系。,叫做模m的絕對最小完全剩余系。,叫做模m的絕對最小完全剩余系。,0,1,2,m1這m個整數(shù)叫做模m的最小非負完全剩余系；,27,例1寫出模7（或8）的最小非負完全剩余系和絕對最小完全剩余系,模7的絕對最小完全剩余系為-3,-2,-1,0,1,2,3,解：模7的最小非負完全剩余系為0,1,2,3,4,5,6,28,3、完全剩余系的構(gòu)造,推論m個整數(shù)作成模m的完全剩余系的充要條件是,兩兩對模m不同

7、余。,注：由定理1及定義2易得證。,思考：1、既然完全剩余系是不唯一的，不同的剩余系之間存在什么關(guān)系呢？,2、一個完全剩余系的所有元素通過線性變換后，還是完全剩余系嗎？,29,檢驗：設(shè)x1,x2,xm是模m的一個完全剩余系，,那么，b+x1,b+x2,b+xm和ax1,ax2,axm,是模m的一個完全剩余系嗎？,30,定理2設(shè)m1，a，b是整數(shù)，(a,m)=1，x1,x2,xm,是模m的一個完全剩余系，則,ax1b,ax2b,axmb也是模m的完全剩余系。,證明由定理1，只需證明：若xixj，,則axibaxjb(modm)。,假設(shè)axibaxjb(modm)，,則axiaxj(modm)，且

8、(a,m)=1，,xixj(modm),由3.1中的結(jié)論,P50第三行知：,31,注意：,(2)在定理2中，條件(a,m)=1不可缺少，否則不能成立；,(3)定理2也可以敘述為：設(shè)m1，a，b是整數(shù)，,(a,m)=1，若x通過模m的一個完全剩余系，,則ax+b也通過模m的一個完全剩余系；,（4）特別地，若x通過模m的一個完全剩余系，(a,m)=1,則ax和x+b也分別通過模m的一個完全剩余系。,(1)任意m個連續(xù)整數(shù)都能構(gòu)成模m的一個完全剩余系；,32,例1設(shè)p5是素數(shù)，a2,3,p1，則在數(shù)列a，2a，3a，(p1)a，pa中有且僅有一個數(shù)b，滿足b1(modp).,證：因為1，2，3，(p

9、1)，p是模p的一個完全剩余系，,所以a，2a，3a，(p1)a，pa構(gòu)成模p的一個完全剩余系。,因此必有唯一的數(shù)b滿足式b1(modp)。,33,例2設(shè)A=x1,x2,xm是模m的一個完全剩余系，以x表示x的小數(shù)部分，證明：若(a,m)=1，則,證：當x通過模m的完全剩余系時，axb也通過模m的完全剩余系，,因此對于任意的i（1im），axib一定與且只與某個整數(shù)j（1jm）同余，,即存在整數(shù)k，使得axib=kmj，（1jm）,34,定理3若m1,m2N，(m1,m2)=1，當x1與x2分別通過,模m1與模m2的完全剩余系時，,則m2x1m1x2通過模m1m2的完全剩余系。,4、剩余系間的

10、聯(lián)系,35,例3設(shè)m0是偶數(shù)，a1,a2,am與b1,b2,bm,都是模m的完全剩余系，,則a1b1,a2b2,ambm不是模m的完全剩余系。,證由1,2,m與a1,a2,am都是模m的完全剩余系，,如果a1b1,a2b2,ambm是模m的完全剩余系，,不可能！,36,例4設(shè)miN（1in），則當xi通過模mi（1in）,的完全剩余系時，,x=x1m1x2m1m2x3m1m2mn1xn,通過模m1m2mn的完全剩余系。,證明對n施行歸納法。,當n=2時，結(jié)論成立。,假設(shè)定理結(jié)論當n=k時成立，,即當xi（2ik1）分別通過模mi的完全剩余系時，,y=x2m2x3m2m3x4m2mkxk1,通過

11、模m2m3mk1的完全剩余系。,37,y=x2m2x3m2m3x4m2mkxk1,通過模m2m3mk1的完全剩余系。,由定理3，當x1通過模m1的完全剩余系，,xi（2ik1）通過模mi的完全剩余系時，,x1m1y=x1m1(x2m2x3m2mkxk1),=x1m1x2m1m2x3m1m2mkxk1,通過模m1m2mk1的完全剩余系。,即結(jié)論對于n=k1也成立。,38,39,3.3簡化剩余系與歐拉函數(shù),一、基本概念,定義1設(shè)R是模m的一個剩余類，若有aR，使得(a,m),=1，則稱R是模m的一個簡化剩余類。,即與模m互質(zhì)的剩余類。,注：若R是模m的簡化剩余類，則R中的數(shù)都與m互素。,例如，模4

12、的簡化剩余類有兩個：,R1(4)=,7,3,1,5,9,，,R3(4)=,5,1,3,7,11,。,40,定義2對于正整數(shù)k，令函數(shù)(k)的值等于模k的所有,簡化剩余類的個數(shù)，稱(k)為Euler函數(shù)。,容易驗證：(2)=1，(3)=2，(4)=2，(7)=6。,注:(1)(m)就是在m的一個完全剩余系中與m互素的,整數(shù)的個數(shù)，,41,定義3對于正整數(shù)m，從模m的每個簡化剩余類中,各取一個數(shù)xi，構(gòu)成一個集合x1,x2,x(m)，,稱為模m的一個簡化剩余系（或簡稱為簡化系）。,注：由于選取方式的任意性，模m的簡化剩余系,有無窮多個。,例如，集合9,5,3,1是模8的簡化剩余系；,集合1,3,5

13、,7也是模8的簡化剩余系.,集合1,3,5,7稱為模8的最小非負簡化剩余系。,注：模m的任意一組簡化剩余系中有(m)個整數(shù),42,二、主要性質(zhì),1.定理1整數(shù)集合A是模m的簡化剩余系的充要條件是：,A中含有(m)個整數(shù)；,A中的任何兩個整數(shù)對模m不同余；,A中的每個整數(shù)都與m互素。,說明：簡化剩余系是某個完全剩余系中的部分元素,構(gòu)成的集合，故滿足條件2；,由定義1易知滿足條件3；,由定義3易知滿足條件1。,43,2.定理2若a1,a2,a(m)是(m)個與m互質(zhì)的整數(shù)，且兩兩對模m不同余，則a1,a2,a(m)是模m的一個簡化系。(留做練習),44,3.定理3設(shè)a是整數(shù)，(a,m)=1，B=x

14、1,x2,x(m),是模m的簡化剩余系，則集合,A=ax1,ax2,ax(m),也是模m的簡化剩余系。,證明:1)顯然，集合A中有(m)個整數(shù)。,2)由于(a,m)=1，,對于任意的xi（1i(m)），xiB，,有(axi,m)=(xi,m)=1。,故A中的每一個數(shù)都與m互素。,3)A中的任何兩個不同的整數(shù)對模m不同余。,因為，若有x,xB，使得axax(modm)，,那么，xx(modm)，,于是x=x。,由以上結(jié)論及定理1可知集合A是模m的一個簡化系。注:條件(a,m)=1不可少。,45,注：在定理3的條件下，若b是整數(shù)，集合,ax1b,ax2b,ax(m)b,不一定是模m的簡化剩余系。,

15、例如，取m=4，a=1，b=1，,以及模4的簡化剩余系1,3。,但2，4不是模4的簡化剩余系。,46,4.定理4設(shè)m1,m2N，(m1,m2)=1，又設(shè),分別是模m1與m2的簡化剩余系，,則A=m1ym2xxX，yY,是模m1m2的簡化剩余系。,證明由第二節(jié)定理3可知，,若以X與Y分別表示,模m1與m2的完全剩余系，使得XX，YY，,則A=m1ym2xxX，yY是模m1m2的完全剩余系。,因此只需證明A中所有與m1m2互素的整數(shù)的集合R,即模m1m2的簡化剩余系是集合A。,47,若m1ym2xR，則(m1ym2x,m1m2)=1，,所以(m1ym2x,m1)=1，,于是(m2x,m1)=1，(

16、x,m1)=1，xX。,同理可得到y(tǒng)Y，因此m1ym2xA。,這說明RA。,另一方面，若m1ym2xA，則xX，yY，,即(x,m1)=1，(y,m2)=1。,由此及(m1,m2)=1得到,(m2xm1y,m1)=(m2x,m1)=1,(m2xm1y,m2)=(m1y,m2)=1。,因為m1與m2互素，所以(m2xm1y,m1m2)=1，,于是m2xm1yR。因此AR。,從而A=R。,48,推論設(shè)m1,m2N,(m1,m2)=1,則(m1m2)=(m1)(m2),證由定理4知，若x1,x2分別通過m1,m2的簡化剩余系，,則m1x2m2x1通過m1m2的簡化剩余系，,即有m1x2m2x1通過(

17、m1m2)個整數(shù)。,另一方面，x1m2x1通過(m1)個整數(shù)，,x2m1x2通過(m2)個整數(shù),從而m1x2m2x1通過(m1)(m2)個整數(shù)。,故有(m1m2)=(m1)(m2)。,注：可以推廣到多個兩兩互質(zhì)數(shù)的情形。,49,注：由上式立即得到若n=2m，（2，m）=1，則(n)=(m)；若m是奇數(shù)，則(4m)=2(m)。,50,5.定理5設(shè)n是正整數(shù)，p1,p2,pk是它的全部素因數(shù)，,證設(shè)n的標準分解式是,由定理4推論得到,對任意的素數(shù)p，,(p)等于數(shù)列1,2,p中與p互素的整數(shù)的個數(shù)，,從而定理得證。,51,證：顯然mn與m,n有相同的素因數(shù)，,設(shè)它們是pi（1ik），則,由此兩式及

18、mn=(m,n)m,n即可得證。,例2.證明：若m,nN，則(mn)=(m,n)(m,n),三、應(yīng)用舉例,52,例3設(shè)nN，證明：,1)若n是奇數(shù)，則(4n)=2(n)；,的充要條件是n=2k，kN；,的充要條件是n=2k3l，k,lN；,4)若6n，則(n),53,1)若n是奇數(shù)，則(4n)=2(n)；,(4n)=(22n),=(22)(n),=2(n),54,的充要條件是n=2k，kN；,若n=2k，,若(n)=,設(shè)n=2kn1，,由(n)=(2kn1)=(2k)(n1),=2k1(n1),所以n1=1，即n=2k；,55,的充要條件是n=2k3l，k,lN；,設(shè)n=2k3ln1，,所以n

19、1=1，即n=2k3l；,若n=2k3l，,則(n)=(2k)(3l),56,4)若6n，則(n),設(shè)n=2k3ln1，,則(n)=(2k)(3l)(n1),57,58,3.4歐拉定理費馬定理及其對循環(huán)小數(shù)的應(yīng)用,本節(jié)主要通過應(yīng)用簡化剩余系的性質(zhì)證明數(shù)論中的兩個重要定理，歐拉定理和費馬定理,并說明其在理論和解決實際問題中的應(yīng)用。,59,一、兩個基本定理,定理1Euler設(shè)m是正整數(shù)，(a,m)=1，,則am)1(modm).,證明：設(shè)x1,x2,x(m)是模m的一個簡化剩余系，,則ax1,ax2,ax(m)也是模m的簡化剩余系，,所以ax1ax2ax(m)x1x2x(m)(modm)，,即a(

20、m)x1x2x(m)x1x2x(m)(modm).,得(x1x2x(m),m)=1，,所以a(m)1(modm).,60,定理2(Fermat)設(shè)p是素數(shù)，,apa(modp)。,注：Fermat定理即是歐拉定理的推論。,證：由于p是素數(shù)，,若(a,p)1，,則由定理1得到,ap11(modp),apa(modp),若(a,p)1，則pa，,所以ap0a(modp),am)1(modm),61,注:根據(jù)歐拉定理，當(a,m)=1時，總能找到x=(m)，使得ax1(modm)。但(m)并不是使ax1(modm)成立的自然數(shù)x中的最小數(shù)。,62,二、定理的應(yīng)用舉例,例1求131956被60除的余數(shù)

21、。,am)1(modm),即131956被60除的余數(shù)為1。,解：,63,練習求313159被7除的余數(shù)。,所以由歐拉定理得,am)1(modm),從而5159=(56)2653,53(mod7),53=255456(mod7)。,即313159被7除的余數(shù)為6。,解：313159,64,am)1(modm),即所求余數(shù)為5,65,例3如果今天是星期一，再過101010天是星期幾？,即得：再過101010天是星期五。,解：,66,三、在分數(shù)與小數(shù)互化中的應(yīng)用,有理數(shù)，即有限小數(shù)和無限循環(huán)小數(shù)，可以用分數(shù)來表示。利用歐拉定理可以解決分數(shù)、小數(shù)的轉(zhuǎn)化問題。,1.定義如果對于一個無限小數(shù),則稱之為循

22、環(huán)小數(shù)，并簡記為,注：若找到的t是最小的，則稱,為循環(huán)節(jié)；t稱為循環(huán)節(jié)的長度；若最小的s0，,則稱該小數(shù)為純循環(huán)小數(shù)，否則為混循環(huán)小數(shù)。,67,2.定理3有理數(shù),能表示為純循環(huán)小數(shù),即：分母不含質(zhì)因數(shù)2或5。,68,(b,10)=1,由Euler定理可知，有正整數(shù)k，使得,10k1(modb)，0k(b)，,因此存在整數(shù)q使得,而且ak,a1不能都等于0，也不能都等于9。,=0.akak1a1akak1a1。,69,3.定理4設(shè)a與b是正整數(shù)，0ab，(a,b)=1，,并且b=25b1，(b1,10)=1，b11，,此處與是不全為零的正整數(shù)，,其中不循環(huán)的位數(shù)碼個數(shù)是=max.,則可以表示成混循環(huán)小數(shù)，,證明：不妨假設(shè)=，,其中0a1b1，0M10，,且(a1,b1)=(2aMb1,b1)=(2a,b1)=(a,b1)=1。,因此，由定理3，可以表示成純循環(huán)小數(shù)：,70,M=m1101m2102m（0mi9，1i），,下面說明，上式中的是最小的不循環(huán)位數(shù)碼的個數(shù)