第三章同余1同余的概念及其基本性質(zhì)1mZb所得的余數(shù)相同，

m去除兩個(gè)整數(shù)a與則稱 a,b對(duì)得的余數(shù)不同，

m同余，記作：則稱

ab(mod若a,b對(duì)模 m不同余，記作：ab(modm)。81(mod7)

a0(mod2)，所有奇數(shù) a1(mod2)。同余是整數(shù)之間的一種1aa(modm)；(反身性)

關(guān)系，它具有下列性質(zhì)：2、若ab(modm)，則ba(modm)；(對(duì)稱性)3、若(modm)；(傳遞性)故同余關(guān)系是等價(jià)關(guān)系。

ab(modm)，bc(modm)，則a c定理1整數(shù)a,b對(duì)模m同余的充分必要條件是abmt，

m|(ab)，即tZ。證明設(shè)1 則a b(modm) r r a1 1b11(1)a1b1

amq r，b1 m(q1q21 (mod m)，

mq r0r ,rm|(ab)。2 2 1 ab2 1(modm)2 2 1 ab2 1abb2 1 2abb

(modm)；12(2)若abc(modm)，則ac b(modm)。121性質(zhì)2若a1

b (modm)，1m)；1

a2

(mod m)，則 aa

b1b2

(mod特別地，若 ab(modm)，則kakb(modm)。2 2 1k

B1k

(modm)，x

y(modm)，i1,2,

,k，iiA則1kx11xkiiA則

B1k 11

y (modm)；特別地，若ab(modm)，k i k i xby0nxn11k 1kxby0nxn1i0,1,2, ,n，則 n

ax x a b n

n1b0b

(modm)。n11 1 1 n性質(zhì)3若aad，bbd，(d,m)1，ab(modm)，則a b (modm)性質(zhì)4(1)若ab(modm)，k0，則akbk(modmk)n11 1 1 n(2)ab(modm)da,bm的任一公因數(shù)，則ab(modm)。dddi 1 2 性質(zhì)5若ab(modm)，i1,2,,k，則ab(mod[m ,m ,,m ])i 1 2 6ab(modm)d|md0ab(modd)。性質(zhì)7若ab(modm)，則(a,m)(b,m)，因而若d能整除a,b及m兩數(shù)之一，則 d必能整除a,b中的另一數(shù)。1求3406寫成十進(jìn)位數(shù)時(shí)的個(gè)位數(shù)碼。a9的數(shù) a。因?yàn)?29 1(mod10)，所以3406(32)203(1)203即個(gè)位數(shù)碼是9。

3406a(mod10)，019(mod10)，2證明：當(dāng)數(shù)時(shí)， 3|2n1。

n為奇數(shù)時(shí)， 3|2n1，當(dāng)n 為偶證明因?yàn)?當(dāng)n為奇數(shù)時(shí)，1，

1(mod3)，所以2n1(1)n1(mod3)，2n1(1)n1 110(mod3)3|2n當(dāng)n為偶數(shù)時(shí)，故 3|同余性質(zhì)在算術(shù)中的一些應(yīng)用。一、檢查因數(shù)的方法

2n1(1)n1112(mod3)，1。1、一整數(shù)能被和能被

39)整除的充分必要條件是它的十進(jìn)位數(shù)碼之3(或9)整除。aZa可以寫成十進(jìn)位的形式：aa10na

10n1

a，0

10，于是，由101(mod3)可知n n1 0 i0 n n1 aanan1 a (mod3)，從而3|a3|0 n n1 n 10i對(duì)于n 10in2、設(shè)正整數(shù)a n

1000n

a 1000n1

， 0 a00

7(或11或 13)

|a的充分必要條件是7(或11或13)| (aa)213(a a )。a)213證明因?yàn)?×11×13=1001。例3a=5874192能被3和9整除。例4a=435693能被3整除，但不能被9整除。例5a=637693能被7整除； a=能被13整除二、棄九法(驗(yàn)算整數(shù)計(jì)算結(jié)果的方法)例6設(shè)a=28997，b=39495，P=ab=15，檢查計(jì)算是否正確。a

10n

10n1

a，0a10n n1 0 im mbb10mb 10mm m0 0k0 0k

b，0b10ll1Pc10 c ll1

c，0c10i則 ( a)(ii0 j0

b)c(mod9)j j

(*)若(*)不成立，則P≠ab，故在本題中，計(jì)算不正確。注(1)若(*)不成立，則計(jì)算不正確；但否命題不成立。(2)利用同樣的方法可以用來驗(yàn)證整數(shù)的加、減運(yùn)算的正確性。2剩余類及完全剩余系定理1設(shè)m0，則全體整數(shù)可分成0 1 mK,K,,0 1 mr中K{qmr|qZ}，r0,1,,m1，這些集合具有下列性r

m個(gè)集合，記作：質(zhì)：每個(gè)整數(shù)必包含在而且 僅在上述的一個(gè)集合中；兩個(gè)整數(shù)同在一個(gè)集合m同余。

的充分必要條件是對(duì)模a 證(1)設(shè)a是任一整數(shù)，則必有amqr，0r ma 于是由r的存在性可知只能在 K中。a ra

aKrarar 1 2r(2)設(shè)整數(shù)a,bK，則amq r，bmq r，故ab(modr 1 2r反之，若

ab(modm)，則a,b必處于同一K 中。0定義1定理 1中的 0類，一個(gè)剩余類 中的任一

,K1

,,Km1

稱為模 m 的剩余數(shù)稱為它同類數(shù)的剩余。若m個(gè)整數(shù)不在同 一剩余類，則稱為模m的一個(gè)完全剩余系。推論m個(gè)整數(shù)作成模的一個(gè)完全剩余系的充分必要條件是它們對(duì)模

a0,aa0,a

1,1,,am1

中任何兩個(gè)數(shù)都mm例如，下列序列都是模m的完全剩余系：(1)0,1,2,,m1；(最小非負(fù)完全剩余系)(2)0,m1,(3)0,m1,

,ama,,(1)ama,

,(m1)m(m1)；,(1)m1m(m1)；1當(dāng)m為偶數(shù)時(shí)，1m

1,,22

1,0,1, 1；mm1,,1,0,1,2

1,；22m為奇數(shù)時(shí)， m12

1,0,1,,m1。(絕對(duì)最小完全剩余系)22mZ(a,m)1bZ剩余系，則

x通過模m

的一個(gè)完全axb也通過模

m的一個(gè)完全剩余系，即若a

,a,,a0 1 m1m是模 m的完全剩余系則aab,aab,,0 1 m1m

m的完全剩余系。

0 1 m10證只需證明aa0法。

b,aab,

,aa

b兩兩不同余即可，采用反證i j i 設(shè)aa b aab(modm)(ij)，則aaaa(modm)i j i i 又(a,m)1，于是i 0 1 m故aa b,aab,,aa b0 1 m

j)，與已知矛盾，m的完全剩余系。1 2 1 2 1 2 1 定理3設(shè)m,m Z，(m,m)1，而x ,x 分別通過模m,m1 2 1 2 1 2 1 mx余系，則mx2 1

也通過模mm1 2mm

的完全剩余系。x,x分別通過m

個(gè)整數(shù)，所以

mxmx通過1 2 1 2mm個(gè)整數(shù)，

2 1 1 21 2下證這m1m2個(gè)整數(shù)對(duì)模m1m2兩兩不同余。設(shè)mx

'mx'm

x''

x''(modmm

)，其中

',x

'',x

',x

''分別是x

,x所2 1 1 2 2 1 1 2 1 2 1 1 2 2 1 2通過的完全剩余系中的 數(shù)，則

x'm

x''(modm

)，mx

'mx

''(mod2 1 2 1m)，m)2

1 1 2 1 2又 (m

,m) 1，故

x ' x

''(modm

)， x

'x''1 2 1 1 1 2 2(mod m)，這說明mx mx2 2 1 1 2所通過的數(shù)兩兩不同余的完全剩余系。

，因此，

m2x1

也通過模mm1 2mm1 m 1 例1設(shè)m0(mod2)，a,,a及b,,b 都是模m1 m 1 ab1 ab1

不是模mbmmb

m的完全剩余系。a1證：因?yàn)?,a1

及 ,mb,m 1mb,

都是模m的完全剩余系，ma所以mai

m i m(m1) (modm)m

m2(modbii1 i1bi2mm從而(a b) a2mm

i1mm0(mod

m)，i i ii1 i1

i)，22a mb若 ,a a mb1 1 m

m mm b) (modab,的完全剩余系，則ab,1 1

i(aii1例2證明：對(duì)任何正整n，存在著僅有數(shù)字 1,0組成的數(shù)n1

1個(gè)

它們對(duì)模

a，使得 n|a。設(shè)bc，b11 1，c111， c(modn)，則n|(bc)111000 a。k s個(gè)1 ks個(gè)1s個(gè)0個(gè)1例3設(shè)mZ，(a,m)1，b Z，x通過

m的一個(gè)完全剩余系，axb1則xm2x

(m1)。證因?yàn)閤通過模余系，所 以axb通過模axb01m1

m的一個(gè)完全剩m的一個(gè)完全axb 01m

m1 1。m 1)(m。2§3簡(jiǎn)化剩余系與歐拉函數(shù)定義1歐拉函數(shù)(a)是定義在正整數(shù)集上它的值等于序列 0,1,2,,a1中與a互質(zhì)的數(shù)的個(gè)數(shù)。

函數(shù)，注若a是質(zhì)數(shù)，則2如果一個(gè)模稱它為一個(gè)與 模m互的剩余類。在與模一數(shù)所作成的數(shù)的集合稱為模m的一個(gè)簡(jiǎn)化剩余系。

a1；若 a是合數(shù)，則(a)a1。m的剩余類中的數(shù)與m互質(zhì)m互質(zhì)的全部剩余類中，從每一類各取定理1模m的剩余類與模是 此類中有一數(shù)與

m互質(zhì)的充分必要條件m互質(zhì)。因此，與模 m互質(zhì)的剩余類的個(gè)數(shù)m的每一簡(jiǎn)化剩余系是由 與m互質(zhì)r的(m)個(gè)對(duì)模m不同余的整數(shù)組成的。r

(m)rr0 1 mrr0 1 m

是模 m的全部剩余類，若 K與模 m互質(zhì)(r,m)1；k反之，若有kr

K， (k

,m)

1，則對(duì)于

中任一數(shù)Kkr Kk

' qmrrk，有(krrrKm互質(zhì)。r

',m) 1，2若

,a,,a

是 (m)個(gè)與

m互質(zhì)的整數(shù)，1 2 (m)并且兩兩 對(duì)模m不同余，1 2 則a,a,,a 是模m1 2 定理3 若(a,m)1，x通過模m的簡(jiǎn)化剩余系，的簡(jiǎn)化剩余系。

ax也通過模m證ax通過 (m)個(gè)整數(shù)，而且由 (a,m)1，(x,m)1可知 (ax,m)1，ii

ax(modm)(i j，則

(modm)(i

j)，與已知矛盾，jixj故ax通過模m的簡(jiǎn)化剩余系。jixj1 2 1 2 1 2 1 定理4 設(shè)m,mZ，(m,m)1，而x,x分別通過模m,m1 2 1 2 1 2 1 余系，則

m2x1m1

x也通過模

1m2

的簡(jiǎn)化剩余系。2證由上一節(jié)定理完全剩余系，則2

3可知，若

,x2

分別通過模m1m

,m2的

也通過模m1m

的完全剩余系。下證當(dāng)1xm2 1xm

,x2

分別通過m12模 ,m的簡(jiǎn)m12化剩余系時(shí)，

mxmx

通過模

mm 的一個(gè)完全2 1 1 2 1 2

mm互質(zhì)的1 2整數(shù)。一方面，由

(x1

,

) (x2,m2)

,m2) 1 可 知(m2x1

,m1

1，(m

x2,m2

) 1，211于是(mx211

m1,m1)1，

(m1

,

) 1，從而

(m2x1 m1

,m1m )2另一方面，由2

(mx

mx,m

) 1可知(mx

mx,m )2 1 1 2 1 2 2 1 1 2 1xmx12212(m ,m) 1，xmx122122于是(m2

x1,m1

)

1x2

,m2

)1，從而

,

)(x2

,

)1。11 2 1 2 1 1 推論設(shè)m ,m Z，(m ,m)1，則(mm) (m)(m11 2 1 2 1 1 證由定理 4可知，

x1,x2

分別通過模

m1,m2的簡(jiǎn)mx化剩余系，則mx2 1x通過模個(gè)整數(shù)。x

m1x2

m1m2

的簡(jiǎn)化剩余系，即mx2 1mx

通過(m

m2)另一方面，由于個(gè)整數(shù)，因此，

通過 m2x1m1x2

)個(gè)整數(shù)，

通過( m)1221 2 1 2 1 11通過(m)(m個(gè)整數(shù)。故 (mm) (m)(m)1221 2 1 2 1 1111 11定理5 設(shè)ap1

1

，則 (a)a1 1 1 。pkpppkpkppp1 2 k(p)pp1。在模質(zhì)

p的完全剩余系1,2,,p中，與p不互p,2p,,p1p，共有p1(p)pp1。因此，

(a)

(p ) (p)1 1 11

(p) (p p 1)(pk 1 1 2k 1 1k 1 1 2

p 1) (p p1)2 k 2 k p pa1 1 1p p1 2 k4歐拉定理·費(fèi)馬定理1(Euler)mZm1(a,m)1，則a(m)1(modm)。12r12

,

是模 的 簡(jiǎn) m(m)m

剩 余 系 ， 則1ar,ar1

,,ar

也是模)rrr(m))rrr

m的簡(jiǎn)21化剩余系，于是(ar21

)(ar)

(ar

(m) 2

(m)

(modm)，112即a(m)112

(m) 1

r (modm)(r

(r,m)(r ,m)1，r ) r(m) 12 1r ) r(m) 12 12

r(m),

m)1，從而a(m)1(mod

m