同余的基本概念和性质

.,3.1同余的概念和性质,.,第三章同余,同余是数论中的一个基本概念。本章除介绍同余的基础知识外，还要介绍它的一些应用。,.,第一节同余的基本性质,定义1给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为ab(modm)，此时也称b是a对模m的同余,如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为ab(modm)。,.,第一节同余的基本性质,定理1下面的三个叙述是等价的：()ab(modm)；()存在整数q，使得a=bqm；()存在整数q1，q2，使得a=q1mr，b=q2mr，0r0ab(modd);()ab(modm),k0,kNakbk(modmk)；()ab(modmi)，1ikab(modm1,m2,mk)；()ab(modm)(a,m)=(b,m)；()acbc(modm),(c,m)=1ab(modm).,.,第一节同余的基本性质,证明结论()()的证明，留作习题。()由acbc(modm)得到mc(ab)，再由(c,m)=1和第一章第三节定理4得到mab，即ab(modm)。证毕。,.,第一节同余的基本性质,例1设N=是整数N的十进制表示，即N=an10nan110n1a110a0，则()3|N()9|N()11|N()13|N,.,第一节同余的基本性质,证明由1001，1011，1021，(mod3)及式(2)可知N=(mod3)，由上式可得到结论()。,结论()，()用同样方法证明。,.,第一节同余的基本性质,为了证明结论()，只需利用式(2)及1001，1013，1024，1031，(mod13)和,.,第一节同余的基本性质,注:一般地，在考虑使被m除的余数时，首先是求出正整数k，使得10k1或1(modm)，,再将写成,的形式，再利用式(2)。,.,第一节同余的基本性质,例2求被7整除的条件，并说明1123456789能否被7整除。,解1001,1013,1022,1031(mod7),因此,即,.,第一节同余的基本性质,由于7894561231=455，7455，所以71123456789。,.,第一节同余的基本性质,解依次计算同余式224，2416，28256，216154，2321(mod641)。,例3说明是否被641整除。,因此0(mod641)，,即641。,.,第一节同余的基本性质,注:一般地，计算ab(modm)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化。,.,第一节同余的基本性质,解(2573346)26(7334)26=7(72)164267(1)16426=(74)26326=3(35)53(7)5=37(72)22129(mod50)，即所求的余数是29。,例4求(2573346)26被50除的余数。,.,第一节同余的基本性质,解我们有713，721，741(mod10)，因此，若77r(mod4)，则,例5求的个位数。,现在77(1)713(mod4)，,.,第一节同余的基本性质,所以由式(3)得到,即n的个位数是3。,注:一般地，若求对模m的同余，可分以下步骤进行：()求出整数k，使ak1(modm)；()求出正整数r,rk,使得bcr(modk);()ar(modm)。,.,第一节同余的基本性质,证明由42n+13n+2=442n93n=416n93n43n93n=133n0(mod13),例6证明:若n是正整数,则1342n+13n+2.,得证。,.,第一节同余的基本性质,证明设a=2k1，当n=1时，有a2=(2k1)2=4k(k1)11(mod23)，即式(4)成立。,例7证明：若2a，n是正整数，则1(mod2n+2)。(4),.,第一节同余的基本性质,设式(4)对于n=k成立，则有1(mod2k+2)=1q2k+2，其中qZ，所以,=(1q2k+2)2=1q2k+31(mod2k+3)，其中q是某个整数。这说明式(4)当n=k1也成立。由归纳法知式(4)对所有正整数n成立。,.,第一节同余的基本性质,证明由a21(modp)pa21=(a1)(a1)，所以必是pa1或pa1，,例8设p是素数，a是整数，则由a21(modp)可以推出a1或a1(modp)。,即a1(modp)或a1(modp)。,.,第一节同余的基本性质,解因为792=8911，故792n8n，9n及11n。我们有8n8z=6，,以及9n913xy45z=19xy9xy1，(5),例9设n的十进制表示是,若792n,求x，y，z。,.,第一节同余的基本性质,11n11z54yx31=3yx113yx。(6),由于0x,y9，所以由式(5)与式(6)分别得出xy1=9或18，3yx=0或11。,.,第一节同余的基本性质,这样得到四个方程组：,其中a取值9或18，b取值0或11。在0x,y9的条件下解这四个方程组，得到x=8，y=0，z=6。,.,习题一,1.证明定