同余的-概念與性質(zhì)

第三章

同余與同余式

第一部分同余概念與性質(zhì)§3.1

同余的概念§3.2

同余的性質(zhì)§3.3同余的應(yīng)用第三章同余與同余式

在日常生活中,有時(shí)我們注意的常常不是某些整數(shù),而是這些整數(shù)用某一個(gè)固定的整數(shù)去除所得到的余數(shù).例如本月2日是星期3,那么9日,16日,…都是星期3,這是因?yàn)樗鼈冇?除后得到的余數(shù)都是2.在我國古代的干支紀(jì)年也是這樣的,它是以60作為除數(shù)的紀(jì)年法.這樣,在數(shù)學(xué)中就產(chǎn)生了同余的概念.同余概念是Gauss在1800年前后創(chuàng)立的.§3.1同余的概念定義假定兩個(gè)整數(shù)a,b對于正整數(shù)m，有a＝mq1+r1,(0≤r1<m)，b＝mq2+r2，(0≤r2<m)，并且r1＝r2,那么我們就稱a與b對(關(guān))于模m同余,用符號表示為

a

≡b(modm)或a

≡b(m).假定上面的r1≠r2,我們就說兩個(gè)整數(shù)a與b關(guān)于模m不同余,用符號a

≡b(modm)或a

≡b(m)表示.

例如,31≡9(mod11),31≡9(mod10).由上例可知，同樣的兩個(gè)數(shù)關(guān)于不同的模同余關(guān)系可能不相同．例3.2

求證：(1)如果a除以m的余數(shù)為r(0≤r<m),那么a≡r(modm);

(2)如果a≡r(modm)，0≤r<m，那么a除以m的余數(shù)為r。

證明(1)由題意得可設(shè)，a＝mq+r

(0≤r<m)．由于0≤r<m，所以r除以m的不完全商為0，余數(shù)為r，即r＝m·０+r

(0≤r<m)．根據(jù)同余概念，可得a≡r(modm);(2)因?yàn)閍≡

r(modm)，所以由同余概念可得·

a＝mq1+R

,

r＝mq2+R，(0≤R<m)，又因?yàn)椋啊躵<m，所以q2＝0，即R＝r.因此得

a＝mq1+r(0≤r<m)．即a被m除，所得的余數(shù)為r．a(chǎn)的對于模m的最小非負(fù)剩余注意：例3．2(1)的結(jié)果說明每一整數(shù)a恰與0，1，…，m－1中的一個(gè)數(shù)對于模m同余．通常稱余數(shù)r(0≤r<m)為a的對于模m的最小非負(fù)剩余．而0，1，…，m－1則稱為模m的最小非負(fù)剩余系．例3．2(2)的結(jié)果是我們以后利用同余知識解決求余數(shù)問題的依據(jù)．

例3．3

求證；如果a

≡b(modm)，那么a+km≡b(modm)，這里k為整數(shù)．證明：由a

≡b(modm)，得a＝mq1+r

，

b＝mq2+r，(0≤r<m)，∴a+km

＝mq1+r+km＝m(q1+k)+r

，∴a+km≡b

(modm)。兩個(gè)整數(shù)同余的充分必要條件定理3.1

兩個(gè)整數(shù)a,b對于模m同余的必要且充分條件是這兩個(gè)數(shù)的差a－b

能夠被正整數(shù)m整除,即a

≡b(modm)

m|(a－b)。證明：∵

a

≡b(modm)∴

a＝mq1+r

，

b＝mq2+r，(0≤r<m)，∴a－b＝mq1+r

－（mq2+r）＝m(q1－q2)，從而由整除的定義得m|(a－b)。

設(shè)a＝mq1+r1,(0≤r1<m),b＝mq2+r2

,(0≤r2<m)，則a－b＝m(q1－q2)+(r1－r2)，

因?yàn)閙|(a－b).所以m|(r1－

r2)，而0≤r1<m，0≤r2<m故|r1－r2|<m,又因?yàn)閨r1－r2|≥0，所以只有r1－r2

＝0，即r1＝r2所以a

≡b(modm)

推論

推論1如果m|(a－b)，那么a

≡b(modm)

推論2

a

≡b(modm)的必要且充分條件是存在整數(shù)k，使得a

＝

b+km(modm)．(這里是等號不是同余號)定理3.1及推論2都是同余的必要且充分條件，因此也可以把它們作為同余的定義:

如果a－b

能被m整除，我們就說a與b對于模m同余．同余的這個(gè)定義與前一個(gè)定義是等價(jià)的，也就是說，既能從前面一個(gè)定義推出這個(gè)定義，也能從這個(gè)定義推出前一個(gè)定義(讀者可自行證明)．今后討論與同余定義有關(guān)的問題時(shí)，靈活選用其中一個(gè)，可以使討論簡便．例3.4用同余式表示下面的說法：

(1)45，94被7除，余數(shù)都是3;(2)數(shù)a與15之差能被17整除;例3.5求證：若a≡b(modm)，則a≡b+km

(modm)，這里k為任意整數(shù)．證明:因?yàn)閍≡b(modm)，所以m|(a－b)，因此m|[(a－b)－km]，即m|[a－

(b＋km)]，所以a≡b

+km(modm)．

(3)171＝15+13X12;(4)數(shù)b被15除余4．例3．3與例3．5的啟示在同余式的左右兩邊中，把一個(gè)數(shù)換成與這個(gè)數(shù)同余的數(shù)(a換成a+km,b換成b+km),同余式仍成立.例3．3與例3．5的比較:

⑴a+km≡b

(modm)并非理所當(dāng)然地就有b≡a

+km(modm),僅當(dāng)關(guān)系滿足自反律時(shí)才能成立.⑵前者根據(jù)同余的定義證明的,而后者是應(yīng)用定理3.1證明的.也就是說,在同余式的左邊或右邊,可以加上模的任意整數(shù)倍km,就象加零一樣,即它與等式性質(zhì)”在等式的左邊或右邊加上零,等式不變”是類似的.§3.2

同余的性質(zhì)

1.同余的基本性質(zhì):在數(shù)學(xué)中,具有自反律,

對稱律,

傳遞律的關(guān)系稱之為等價(jià)關(guān)系.同余關(guān)系就是一種等價(jià)關(guān)系.也就是說,由同余的定義可以得到證明先證自反律,∵m|(a－a),∴a

≡a(modm).我們再證明傳遞律.由題可知m|(a－b),m|(b－c),所以由同余的定義,得到m|[(a－b)＋(b－c)],因此m|(a－c),即a

≡c(modm)

.定理3.2

a

≡a(modm)(自反律).

定理3.3

若a

≡b(modm),則b

≡a(modm)(對稱律).定理3.4如果a

≡b(modm),b

≡c(modm),那么a

≡c(modm)

(傳遞律).例3.6

求證若a≡b(modm)，則(a,m)=(b,m)．

證明因?yàn)閍

≡b(modm)，所以m|(a－b)。即存在整數(shù)q，使得a＝mq+b

，設(shè)d1是a，m的公約數(shù)，則d1|a，d1|m，又因?yàn)閎=a－mq，所以d1|b；再設(shè)d2是b，m的公約數(shù)，則d2|b，d2|m,因?yàn)閍=mq+b，所以d2|a．因此，a，m的公約數(shù)集和b，m的公約數(shù)集相同，所以(a,m)=(b,m)．從例3．6的證明，還可以得出如下的結(jié)論：如果a

≡b(modm)，又d能整除m以及整除a，b兩個(gè)數(shù)中的一個(gè)，則d必能整除a，b中的另一個(gè)．

例3.7

求證：如果a

≡b(modm),b=

c,c

≡d(modm),那么a

≡d(modm).證明因?yàn)閍

≡b(modm)，所以m|(a－b)，又b＝c，因此m|(a－c)，所以a

≡c(modm)，又因?yàn)閏≡d(modm)，由傳遞性，所以a≡

d(modm)．例3.7告訴我們，在討論同余的時(shí)候，可以把等號混在同余中同時(shí)使用，即例3.7的結(jié)論可以寫成a

≡b=

c

≡d(modm)P134習(xí)題3.1第1,4,5題作業(yè)

2.同余的運(yùn)算性質(zhì):二個(gè)同模的同余式能夠象等式一樣進(jìn)行加、減和乘等運(yùn)算.定理3.5

設(shè)a

≡b(modm),c

≡d(modm),則

a＋c

≡b＋d

(modm),a－

c

≡b－

d(modm).證明:由題意,有m|(a－

b),

m|(

c－

d

),所以m|[(a－

b)±(

c－

d

)],即m|[(a±c)－

(

b±d

)],故a＋c

≡b＋d

(modm),a－

c

≡b－

d(modm)

.推論推論1

在同余式的兩邊同加上(或同減去)一個(gè)整數(shù)，同余式仍成立。即：若a＋b

≡c

(modm),則a＋b－

c

≡0

(modm),或a≡c－b(modm).推論3

定理3.5可以推廣到有限個(gè)同余式的情況。推論2

在一個(gè)同余式中，一個(gè)項(xiàng)可以改變符號后移到同余式的另一邊去，定理3.6

設(shè)a

≡b(modm),c

≡d(modm)，則ac

≡bd

(modm).推論推論1設(shè)a

≡b(modm),c是任意整數(shù).

則ac

≡bc

(modm).推論3設(shè)a

≡b(modm),則ak

≡bk(modm),k是任意正整數(shù).推論2設(shè)ai≡bi(modm)(i=1,2,…,n,n>2),則a1a2…an

≡b1b2…bn

(modm).例例1

試證明一個(gè)整數(shù)能被3整除的充分必要條件是它的10進(jìn)位數(shù)碼的和能被3整除.用與例1同樣的證明方法,我們可以得到:一個(gè)整數(shù)能被9整除的必要充分條件是它的10進(jìn)位數(shù)碼的和能被9整除.因?yàn)?0≡1(mod3),所以我們得到因此,我們知道當(dāng)且僅當(dāng)證明設(shè)a是一正整數(shù),并將a寫成10進(jìn)位數(shù)的形式:例3.8

已知x+y≡7(mod5),x≡3(mod5)，求對于模5與y同余的整數(shù)．解因?yàn)閤+y≡7(mod5)，x≡3(mod5)，由定理3.5得x+y－x≡7－3=4(mod5)，即y≡4(mod5)．因此對于模數(shù)5，與y同余的整數(shù)是4+5t(t為任意整數(shù)).

例3.9巳知x≡2(mod5)，

求證：2x2－x+3≡4(mod5)

證明因?yàn)閤≡2(mod5)，所以x2≡22

≡4(mod5)，2x2≡8≡3

(

mod5)，而－x≡－2(mod5)，從例3．9可以看出，應(yīng)用定理3.5的推論1與定理3.6的推論1與推論3，對同余式可以像等式那樣進(jìn)行代換.因此,2x2－x+3≡2×22－2＋3≡9≡4(mod5).§3.3同余概念、性質(zhì)的應(yīng)用利用同余定義與性質(zhì)，可以解決小學(xué)數(shù)學(xué)中的某些較難的問題，例如確定余數(shù)的大小，乘積或乘冪的末位數(shù)字問題以及整除的證明問題等等.例3.10

求下列各數(shù)被7除后的余數(shù)；(1)71427X19，(2)476．解(1)因?yàn)?≡14≡0(mod7)，

71427≡6(mod7)，19≡5(mod7)，(2)∵47≡5(mod7),472≡52≡4(mod7),所以476=(472)3≡43=64≡1(mod7),即476被7除的余數(shù)為1．所以71427X19≡6X5=30≡2(mod7)，即71427X19≡7除的余數(shù)為2；

例3.11

求1350分別被5，11除所得的余數(shù)．解因?yàn)?3≡3(mod5)，34≡1(mod5)，所以350=348X32≡(34)12X9≡4(mod5)．1350≡250=(25)10≡1010=(102)5≡1(mod11);因此所求的余數(shù)分別為4與1.又因?yàn)?3≡2(mod11)，25≡10(mod11)，102≡1(mod11)，所以例3.12把由1開始的自然數(shù)依次寫下來，直寫到第201位為止，就是

12345678910111213…

試問這個(gè)數(shù)除以3的余數(shù)等于幾?解因?yàn)?～9寫在一起構(gòu)成九位數(shù)，10～99寫在一起為90X2＝180位數(shù)，所以由1開始的自然數(shù)依次寫到99，合計(jì)為189位數(shù)，由于201－189=12，因此只需在1寫到99后再寫上100，101，102，103四個(gè)數(shù)．即從１開始的自然數(shù)依次寫到103就構(gòu)成一個(gè)201位數(shù)(由103個(gè)連續(xù)的自然數(shù)組成）．因?yàn)槊咳齻€(gè)連續(xù)自然數(shù)的各位數(shù)字之和能被3除，103≡1(mod3)，所以這個(gè)數(shù)除以3的余數(shù)為1．201位大數(shù)的余數(shù)問題從上面幾個(gè)例題可以看到，在給定模數(shù)的條件下，對于很大的數(shù)，尤其是對于以方冪形式給出的數(shù),利用同余的性質(zhì)，可在同余的意義下使它變小，如果能在運(yùn)算過程中，出現(xiàn)ak≡1(modm)，那么對于求an被m除的余數(shù)就很方便了．乘冪Ak

的末位數(shù)字問題對于乘冪Ak

的末位數(shù)字問題，即所謂尾數(shù)問題，根據(jù)整除定義，本質(zhì)上是求Ak與那個(gè)數(shù)字對于模10同余問題．實(shí)際上，若設(shè)Ak=10b+c，這里c是乘冪Ak的個(gè)位數(shù)字，則Ak≡c(mod10)．由于乘冪Ak的個(gè)位數(shù)字c只能與底數(shù)A的個(gè)位數(shù)字a有關(guān)，所以我們根據(jù)0~9這十個(gè)數(shù)字自乘的規(guī)律來解決乘冪Ak的個(gè)位數(shù)字問題就顯得比較簡單．?dāng)?shù)字a(1≤a≤9)自乘后所得冪ak的末位數(shù)字變化規(guī)律，(見下頁)．

從表可以看出，當(dāng)a為0，1，5，6時(shí),a的任何次冪的個(gè)位數(shù)字都是它們本身．即a=0，1，5或6時(shí)．a(chǎn)k的個(gè)位數(shù)字呈現(xiàn)周期為1的規(guī)律性;當(dāng)a=2，3，7或8時(shí)，ak的個(gè)位數(shù)字出現(xiàn)的規(guī)律也有周期性，其周期為4。當(dāng)a=4或9時(shí)，a3，a5，a7，a9，a11，a1