初等数论第三章同余

第三章同余§1同余的概念及其基本性质定义1设meZ+,称之为模。若用m去除两个整数a与b所得的余数相同，则称a,b对模m同余，记作：a三b(modm)；若所得的余数不同，则称a,b对模m不同余，记作：a丰b(modm)。例如，8三l(mod7),；所有偶数a三0(mod2)，所有奇数a三l(mod2)。同余是整数之间的一种关系，它具有下列性质：1、a三a(modm)；(反身性)2、若a三b(modm)，贝Vb三a(modm)；(对称性)3、若a三b(modm)，b三c(modm)，贝Va三c(modm)；(传递性)故同余关系是等价关系。定理1整数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的任一公因数，贝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两数之一，则d必能整除a,b中的另一数。例1求3406写成十进位数时的个位数码。解事实上，只需求满足3406三a(mod10),0<a<9的数a。因为32三9=-1(mod10),所以3406三(32)203三(-1)203三一1三9(mod10),即个位数码是9。例2证明：当n为奇数时，3I2n+1,当n为偶数时，3J2n+1。证明因为2三-1(mod3),所以2n+1三(-1)n+1(mod3),当n为奇数时，2n+1三(-1)n+1三-1+1三0(mod3)，故3I2n+1,当n为偶数时，2n+1三(-1)n+1三1+1三2(mod3),故3J2n+1。同余性质在算术中的一些应用。一、检查因数的方法1、一整数能被3(或9)整除的充分必要条件是它的十进位数码之和能被3(或9)整除。证明只需讨论正整数即可。任取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、设正整数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整除。二、弃九法(验算整数计算结果的方法)例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)利用同样的方法可以用来验证整数的加、减运算的正确性。§2剩余类及完全剩余系定理1设m>0,则全体整数可分成m个集合，记作：K,K，…,K，其01m-1中K={qm+rIqgZ},r=0,1，…,m-1,这些集合具有下列性质：r每个整数必包含在而且仅在上述的一个集合中；两个整数同在一个集合的充分必要条件是对模m同余。证(1)设a是任一整数，贝9必有a=mq+r，0<r<m，aa于是由r的存在性可知agK，由r的唯一性可知a只能在K中。TOC\o"1-5"\h\zararaa(2)设整数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数称为它同类数的剩余。若m个整数a,a，…,a中任何两个数都不在同一剩余类，贝临,a，…,a01m-101m-1称为模m的一个完全剩余系。推论m个整数作成模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为偶数时，1。——，——+1,…,—1,0,1,…,——1；TOC\o"1-5"\h\zmmm2。-+1,…，一1,0,1,…，二■-1,—；222当m为奇数时，-，…,-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个整数，所以mx+mx通过mm个整数,1212211212下证这mm个整数对模mm两两不同余。1212设mx'+mx'三mx''+mx''(modmm)，其中x',x'',x',x''分别是x,x所112211212112212通过的完全剩余系中的数，则mx'三mx''(modm),mx'三mx''(modm)2121112122又(m,m)=1,故x'三x''(modm),x'三x''(modm)，这说明mx+mx121112222112所通过的数两两不同余，因此，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证明：对任何正整数n,存在着仅有数字1,0组成的数a,使得nIa。证：考察n+1个数：1,11,…,卫…[，它们对模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)。〔mJ2x证因为x通过模m的一个完全剩余系，所以ax+b通过模m的一个完全剩余系,从而ax+剩余系,从而ax+b，通过2,丄,…,口Jmmmaxax+b]=£+丄+...+口=丄働-1)。Jmmm2§3简化剩余系与欧拉函数定义1欧拉函数*(a)是定义在正整数集上的函数，它的值等于序列0,1,2,…,a-1中与a互质的数的个数。注若a是质数，则*(a)=a-1；若a是合数，则*(a)<a-1。定义2如果一个模m的剩余类中的数与m互质，则称它为一个与模m互质的剩余类。在与模m互质的全部剩余类中，从每一类各取一数所作成的数的集合称为模m的一个简化剩余系。定理1模m的剩余类与模m互质的充分必要条件是此类中有一数与m互质。因此，与模m互质的剩余类的个数为*(m),模m的每一简化剩余系是由与m互质的*(m)个对模m不同余的整数组成的。证设K,K，…,K是模m的全部剩余类，若K与模m互质，则(r,m)=1；TOC\o"1-5"\h\z01m-1r反之，若有kgK,(k,m)=1,则对于K中任一数k'=qm+k，有(k',m)=1，rrrrrrr即K与模m互质。r定理2若a,a,…,a是*(m)个与m互质的整数，并且两两对模m不同余,12*(m)则a,a,…,a是模m的一个简化剩余系。12*(m)定理3若(a,m)=1，x通过模m的简化剩余系，则ax也通过模m的简化剩余系。证ax通过*(m)个整数，而且由(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证由上一节定理3可知,若x,x分别通过模m,m的完全剩余系,则1212mx+mx也通过模mm的完全剩余系。下证当x,x分别通过模m,m的简2112121212化剩余系时，mx+mx通过模mm的一个完全剩余系中一切与mm互质的21121212整数。一方面，由(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)个整数。12211212另一方面，由于x通过9(m)个整数，x通过9(m)个整数，因此，mx+mx11222112通过9(m)9(m)个整数。故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不互质的数为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)推论