第三章同余§1同余的概念及其基本性質定義1設meZ+,稱之為模。若用m去除兩個整數(shù)a與b所得的余數(shù)相同，則稱a,b對模m同余，記作：a三b(modm)；若所得的余數(shù)不同，則稱a,b對模m不同余，記作：a豐b(modm)。例如，8三l(mod7),；所有偶數(shù)a三0(mod2)，所有奇數(shù)a三l(mod2)。同余是整數(shù)之間的一種關系，它具有下列性質：1、a三a(modm)；(反身性)2、若a三b(modm)，貝Vb三a(modm)；(對稱性)3、若a三b(modm)，b三c(modm)，貝Va三c(modm)；(傳遞性)故同余關系是等價關系。定理1整數(shù)a,b對模m同余的充分必要條件是mI(a-b)，即a=b+mt,teZ。證明設a=mq+r，b=mq+r，0<r,r<m，112212貝9a三b(modm)or=「oa-b=m(q-q?)omI(a-b)。性質1(1)若a三b(modm)，a三b(modm),則a+a三b+b(modm)；11221212(2)若a+b三c(modm)，貝Va三c一b(modm)。性質2若a三b(modm)，a三b(modm),則aa三bb(modm)；11221212特另ll地，若a三b(modm)，貝Vka三kb(modm)。定理2則工A定理2則工Aa…aa】一a若A三B(modm)，x三y(modm)，i=1,2,???,k,a—aii1k1kx円…xak三乙By?1…yak(modm)；特別地，若a三b(modm),1ka?a1kii1ka】一ai=0,12…,n則axn+axn-1++a三bxn+bxn-1+—+b(modm)。nn-10nn-10性質3若a=ad,b=bd,(d,m)=1,a三b(modm),貝Ua三b(modm)。1111性質4(1)若a三b(modm),k>0,貝Vak三bk(modmk)；TOC\o"1-5"\h\zabm(2)若a三b(modm),d是a,b及m的任一公因數(shù)，貝V—三一(mod)。ddd性質5若a三b(modm),i=1,2,…，k,則a三b(mod[m,m,…,m])。i12k反之亦然。性質6若a三b(modm),dIm,d>0,貝Va三b(modd)。性質7若a三b(modm),貝V(a,m)=(b,m),因而若d能整除a,b及m兩數(shù)之一，則d必能整除a,b中的另一數(shù)。例1求3406寫成十進位數(shù)時的個位數(shù)碼。解事實上，只需求滿足3406三a(mod10),0<a<9的數(shù)a。因為32三9=-1(mod10),所以3406三(32)203三(-1)203三一1三9(mod10),即個位數(shù)碼是9。例2證明：當n為奇數(shù)時，3I2n+1,當n為偶數(shù)時，3J2n+1。證明因為2三-1(mod3),所以2n+1三(-1)n+1(mod3),當n為奇數(shù)時，2n+1三(-1)n+1三-1+1三0(mod3)，故3I2n+1,當n為偶數(shù)時，2n+1三(-1)n+1三1+1三2(mod3),故3J2n+1。同余性質在算術中的一些應用。一、檢查因數(shù)的方法1、一整數(shù)能被3(或9)整除的充分必要條件是它的十進位數(shù)碼之和能被3(或9)整除。證明只需討論正整數(shù)即可。任取aeZ+,則a可以寫成十進位的形式:a=a10n+a10n—1++a,0<a<10,于是，由10三l(mod3)可矢口TOC\o"1-5"\h\znn-10ia三a+a++a(mod3),從而31ao31a+a++a。nn-10nn-10對于9同理可證。2、設正整數(shù)a=a1000n+a1000n-1+…+a,0<a<1000，貝I」7(或nn-10i11或13)|a的充分必要條件是7(或11或13)|(a+a+…)-(a+a+…)。0213證明因為7X11X13=1001。例3a=5874192能被3和9整除。例4a=435693能被3整除，但不能被9整除。例5a=637693能被7整除；a二能被13整除。二、棄九法(驗算整數(shù)計算結果的方法)例6設a=28997,b=39495,P=ab=15，檢查計算是否正確。解令a=a10n+a10n-1++a,0<a<10TOC\o"1-5"\h\znn-10ib=b10m+b10m-1+…+b,0<b<10

mm-10jP=c101+c101-1++c,0<c<10ll-10k則(工a)(2b)三工c(mod9)(*)ijki=0j=0k=0若(*)不成立，則P^ab，故在本題中，計算不正確。注(1)若(*)不成立，則計算不正確；但否命題不成立。(2)利用同樣的方法可以用來驗證整數(shù)的加、減運算的正確性。§2剩余類及完全剩余系定理1設m>0,則全體整數(shù)可分成m個集合，記作：K,K，…,K，其01m-1中K={qm+rIqgZ},r=0,1，…,m-1,這些集合具有下列性質：r每個整數(shù)必包含在而且僅在上述的一個集合中；兩個整數(shù)同在一個集合的充分必要條件是對模m同余。證(1)設a是任一整數(shù)，貝9必有a=mq+r，0<r<m，aa于是由r的存在性可知agK，由r的唯一性可知a只能在K中。TOC\o"1-5"\h\zararaa(2)設整數(shù)a,bgK，貝9a=mq+r，b=mq+r,故a三b(modm)。r12反之，若a三b(modm)，則a,b必處于同一K中。r定義1定理1中的K,K，…,K稱為模m的剩余類，一個剩余類中的任一01m-1數(shù)稱為它同類數(shù)的剩余。若m個整數(shù)a,a，…,a中任何兩個數(shù)都不在同一剩余類，貝臨,a，…,a01m-101m-1稱為模m的一個完全剩余系。推論m個整數(shù)作成模m的一個完全剩余系的充分必要條件是它們對模m兩兩不同余。例如，下列序列都是模m的完全剩余系：0,1,2,…,m-1；(最小非負完全剩余系)0,m+1,…,am+a,…,(m-1)m+(m-1)；0,-m+1,…,(-1)am+a,…,(-1)m-1m+(m-1)；⑷當m為偶數(shù)時，1?！?1,…,—1,0,1,…,——1；TOC\o"1-5"\h\zmmm2。-+1,…，一1,0,1,…，二■-1,—；222當m為奇數(shù)時，-，…,-1,0,1,…,。（絕對最小完全剩余系）22定理2設meZ+,(a,m)=1，beZ,若x通過模m的一個完全剩余系，則ax+b也通過模m的一個完全剩余系，即若a,a,…,a是模m的完全剩余系，01m-1則aa+b,aa+b,…,aa+b也是模m的完全剩余系。01m-1證只需證明aa+b,aa+b,…,aa+b兩兩不同余即可，采用反證法。01m-1設aa+b三aa+b(modm)(i豐j),貝Vaa三aa(modm)，jij又(a,m)=1,于是a三a(modm)(i豐j),與已知矛盾，ij故aa+b,aa+b,…,aa+b也是模m的完全剩余系。01m-1定理3設m,meZ+,(m,m)=1,而x,x分別通過模m,m的完全剩12121212余系，則mx+mx也通過模mm的完全剩余系。211212證因為x,x分別通過m,m個整數(shù)，所以mx+mx通過mm個整數(shù),1212211212下證這mm個整數(shù)對模mm兩兩不同余。1212設mx'+mx'三mx''+mx''(modmm)，其中x',x'',x',x''分別是x,x所112211212112212通過的完全剩余系中的數(shù)，則mx'三mx''(modm),mx'三mx''(modm)2121112122又(m,m)=1,故x'三x''(modm),x'三x''(modm)，這說明mx+mx121112222112所通過的數(shù)兩兩不同余，因此，mx+mx也通過模mm的完全剩余系。211212xx例1設m三0(mod2),a,…,a及b,…,b都是模m的完全剩余系,1m1ma+b,…,a+b不是模m的完全剩余系。TOC\o"1-5"\h\z11mm證：因為a,…,a及b,…,b都是模m的完全剩余系,Eym(m+1)Eym(m+1)ma三i=三.i22i=1所以i=1(modm),同理￡所以i=12i2i=1從而￡(a+b)三乞a+￡b三+三0(modm),iiii22i=1i=1i=1若a+b,…,a+b是模m的完全剩余系，則￡(a+b)三(modm)，矛盾。11mmii2i=1因此，a+b,…,a+b不是模m的完全剩余系。11mm例2證明：對任何正整數(shù)n,存在著僅有數(shù)字1,0組成的數(shù)a,使得nIa。證：考察n+1個數(shù)：1,11,…,衛(wèi)…[，它們對模n至少有兩個在同一同余類中,n+1個1設b>c,b=J_1…二J，c=J_1…二J，b三c(modn),貝骯I(b一c)=…100…0=a。k個1s個1k-s個1s個0例3設meZ+,(a,m)=1,beZ,x通過模m的一個完全剩余系，制Vfax+b]1z八貝寸乙彳>=—(m-1)?！瞞J2x證因為x通過模m的一個完全剩余系，所以ax+b通過模m的一個完全剩余系,從而ax+剩余系,從而ax+b，通過2,丄,…,口Jmmmaxax+b]=￡+丄+...+口=丄働-1)。Jmmm2§3簡化剩余系與歐拉函數(shù)定義1歐拉函數(shù)*(a)是定義在正整數(shù)集上的函數(shù)，它的值等于序列0,1,2,…,a-1中與a互質的數(shù)的個數(shù)。注若a是質數(shù)，則*(a)=a-1；若a是合數(shù)，則*(a)<a-1。定義2如果一個模m的剩余類中的數(shù)與m互質，則稱它為一個與模m互質的剩余類。在與模m互質的全部剩余類中，從每一類各取一數(shù)所作成的數(shù)的集合稱為模m的一個簡化剩余系。定理1模m的剩余類與模m互質的充分必要條件是此類中有一數(shù)與m互質。因此，與模m互質的剩余類的個數(shù)為*(m),模m的每一簡化剩余系是由與m互質的*(m)個對模m不同余的整數(shù)組成的。證設K,K，…,K是模m的全部剩余類，若K與模m互質，則(r,m)=1；TOC\o"1-5"\h\z01m-1r反之，若有kgK,(k,m)=1,則對于K中任一數(shù)k'=qm+k，有(k',m)=1，rrrrrrr即K與模m互質。r定理2若a,a,…,a是*(m)個與m互質的整數(shù)，并且兩兩對模m不同余,12*(m)則a,a,…,a是模m的一個簡化剩余系。12*(m)定理3若(a,m)=1，x通過模m的簡化剩余系，則ax也通過模m的簡化剩余系。證ax通過*(m)個整數(shù)，而且由(a,m)=1，(x,m)=1可知(ax,m)=1，若ax三ax(modm)(i豐j)，貝Vx三x(modm)(i豐j)，與已知矛盾，ijij故ax通過模m的簡化剩余系。

定理4設m,meZ+,(m,m)=1,而x,x分別通過模m,m的簡化剩12121212余系，則mx+mx也通過模mm的簡化剩余系。211212證由上一節(jié)定理3可知,若x,x分別通過模m,m的完全剩余系,則1212mx+mx也通過模mm的完全剩余系。下證當x,x分別通過模m,m的簡2112121212化剩余系時，mx+mx通過模mm的一個完全剩余系中一切與mm互質的21121212整數(shù)。一方面，由(x,m)=(x,m)=(m,m)=1可矢口(mx,m)=1(mx,m)=1，112212211122于是(mx+mx,m)=1，(mx+mx,m)=1，從而(mx+mx,mm)=1，2112112212211212另一方面，由(mx+mx,mm)=1可知(mx+mx,m)=(mx+mx,m)=1，2112122112112212于是(mx,m)=(mx,m)=1，從而(x,m)=(x,m)=1。2111221122推論設m,meZ+，(m,m)=1，貝切(mm)=9(m)9(m)。12121212證由定理4可知，若x,x分別通過模m,m的簡化剩余系，則mx+mx12122112通過模mm的簡化剩余系，即mx+mx通過9(mm)個整數(shù)。12211212另一方面，由于x通過9(m)個整數(shù)，x通過9(m)個整數(shù)，因此，mx+mx11222112通過9(m)9(m)個整數(shù)。故9(mm)=9(m)9(m)。121212定理5設a=定理5設a=pa1pa2…pak，12k貝卩9(a)=a1——1——…1——證先證9(pa)=pa—pa-1oIp1人在模P?的完全剩余系1,2,…,pa中，與pa不互質的數(shù)為p,2p,…,pa—1p'共有pa—1個’故9(pa)=pa—pa—1。因此，9(a)=9(佇)9(pa2)…9(佟)=(佇-佇-1)(役-pa2-1)…(佟-佟-1)=af1—丄lp12丫1)■丿lp2丿k1L1)pk丿§4歐拉定理?費馬定理定理1(Euler)設mg乙m>1,(a,m)=1,貝Va9(m)三1(modm)。證設r,r，…,r是模m的簡化剩余系，則ar,ar,…,ar也是模m的簡TOC\o"1-5"\h\z129(m)129(m)化剩余系，于是(ar)(ar)…(ar)三rr…r(modm),129(m)129(m)艮卩a9(m)(rr?…r)三rr?…r(modm),又(r,m)=(r,m)=?…(r,m)=1,129(m)129(m)129(m)故(rr…r,m)=1,從而a9(m)三1(modm)。129(m)推論