同余的基本概念和性质

§3.1同余的概念和性质第三章同余•同余是数论中的一个基本概念。本章除介绍同余的基础知识外，还要介绍它的一些应用。第一节同余的基本性质定义1给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为ab(modm)，此时也称b是a对模m的同余如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为ab(modm)。第一节同余的基本性质定理1下面的三个叙述是等价的：(ⅰ)ab(modm)；(ⅱ)存在整数q，使得a=bqm；(ⅲ)存在整数q1，q2，使得a=q1mr，b=q2mr，0rm。证明留作习题。第一节同余的基本性质定理2同余具有下面的性质：(ⅰ)(自反性)aa(modm)；(ⅱ)(对称性)ab(modm)ba(modm);(ⅲ)(传递性)ab，bc(modm)ac(modm)。证明留作习题。第一节同余的基本性质定理3设a，b，c，d是整数，并且ab(modm)，cd(modm)，(1)则(ⅰ)acbd(modm)；(ⅱ)acbd(modm)。证明(ⅰ)由式(1)及定义1可知mab，mcd，第一节同余的基本性质因此m(ac)(bd)，此即结论(ⅰ)；(ⅱ)由式(1)及定理1可知，存在整数q1与q2使得a=bq1m，c=dq2m，因此ac=bd(q1q2mq1dq2b)m，再利用定理1，推出结论(ⅱ)。证毕。第一节同余的基本性质定理4设ai，bi（0in）以及x，y都是整数，并且xy(modm)，aibi(modm)，0in，则(2)证明留作习题。).(mod00mybxaniiiniii第一节同余的基本性质定理5下面的结论成立：(ⅰ)ab(modm),dm,d0ab(modd);(ⅱ)ab(modm),k0,kNakbk(modmk)；(ⅲ)ab(modmi)，1ikab(mod[m1,m2,,mk])；(ⅳ)ab(modm)(a,m)=(b,m)；(ⅴ)acbc(modm),(c,m)=1ab(modm).第一节同余的基本性质证明结论(ⅰ)—(ⅳ)的证明，留作习题。(ⅴ)由acbc(modm)得到mc(ab)，再由(c,m)=1和第一章第三节定理4得到mab，即ab(modm)。证毕。第一节同余的基本性质例1设N=是整数N的十进制表示，即N=an10nan110n1a110a0，则(ⅰ)3|N(ⅱ)9|N(ⅲ)11|N(ⅳ)13|N;0|3niia;0|9niia;)1(0|11niiia.|13345012aaaaaa第一节同余的基本性质证明由1001，1011，1021，(mod3)及式(2)可知N=(mod3)，由上式可得到结论(ⅰ)。结论(ⅱ)，(ⅲ)用同样方法证明。第一节同余的基本性质为了证明结论(ⅳ)，只需利用式(2)及1001，1013，1024，1031，(mod13)和.1010334500120121aaaaaaaaaaNnn第一节同余的基本性质注:一般地，在考虑使被m除的余数时，首先是求出正整数k，使得10k1或1(modm)，0121aaaaNnn再将写成0121aaaaNnnkkhkkkaaaaaaaN1010221200121的形式，再利用式(2)。第一节同余的基本性质例2求被7整除的条件，并说明1123456789能否被7整除。0121aaaaNnn解1001,1013,1022,1031(mod7),因此，)7(mod1010678345012334500120121aaaaaaaaaaaaaaaaaaaNnn即678345012|7|7aaaaaaaaaN第一节同余的基本性质由于7894561231=455，7455，所以71123456789。第一节同余的基本性质解依次计算同余式224，2416，28256，216154，2321(mod641)。例3说明是否被641整除。12521252因此0(mod641)，即641。1252第一节同余的基本性质注:一般地，计算ab(modm)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化。第一节同余的基本性质解(2573346)26(7334)26=[7(72)164]26[7(1)164]26=(74)26326=3(35)53(7)5=37(72)22129(mod50)，即所求的余数是29。例4求(2573346)26被50除的余数。第一节同余的基本性质解我们有713，721，741(mod10)，因此，若77r(mod4)，则例5求的个位数。777n)3()10(mod7777rn现在77(1)713(mod4)，第一节同余的基本性质所以由式(3)得到)10(mod37)3(773377n即n的个位数是3。注:一般地，若求对模m的同余，可分以下步骤进行：(ⅰ)求出整数k，使ak1(modm)；(ⅱ)求出正整数r,rk,使得bcr(modk);(ⅲ)ar(modm)。cba第一节同余的基本性质证明由42n+13n+2=442n93n=416n93n43n93n=133n0(mod13)例6证明:若n是正整数,则1342n+13n+2.得证。第一节同余的基本性质证明设a=2k1，当n=1时，有a2=(2k1)2=4k(k1)11(mod23)，即式(4)成立。例7证明：若2a，n是正整数，则1(mod2n+2)。(4)|na2第一节同余的基本性质设式(4)对于n=k成立，则有1(mod2k+2)=1q2k+2，其中qZ，所以=(1q2k+2)2=1q2k+31(mod2k+3)，其中q是某个整数。这说明式(4)当n=k1也成立。由归纳法知式(4)对所有正整数n成立。12ka第一节同余的基本性质证明由a21(modp)pa21=(a1)(a1)，所以必是pa1或pa1，例8设p是素数，a是整数，则由a21(modp)可以推出a1或a1(modp)。即a1(modp)或a1(modp)。第一节同余的基本性质解因为792=8911，故792n8n，9n及11n。我们有8n8z=6，以及9n913xy45z=19xy9xy1，(5)例9设n的十进制表示是,若792n,求x，y，z。zxy4513第一节同余的基本性质11n11z54yx31=3yx113yx。(6)由于0x,y9，所以由式(5)与式(6)分别得出xy1=9或18，3yx=0或11。第一节同余的基本性质这样得到四个方程组：bxyayx31其中a取值9或18，b取值0或11。在0x,y9的条件下解这四个方程组，得到x=8，y=0，z=6。习题一1.证明定理1和定理2。2.证明定理4。3.证明定理5中的结论(ⅰ)—(ⅳ)。4.求81234被13除的余数。5.设f(x)是整系数多项式，并且f(1),f(2),,f(m)都不能被m整除,则f(x)=0没有整数解.6.已知99，求与。42762