数论02 1008new

《数论02 1008new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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£r

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)。59证明(ⅰ)由式(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，再利

3、用定理1，推出结论(ⅱ)。证毕。定理4设ai，bi（0£i£n）以及x，y都是整数，并且xºy(modm)，aiºbi(modm)，0£i£n，则(modm)。(2)证明留作习题。定理5下面的结论成立：(ⅰ)aºb(modm)，d½m，d>0Þaºb(modd)；(ⅱ)aºb(modm)，k>0，kÎNÞakºbk(modmk)；(ⅲ)aºb(modmi)，1£i£kÞaºb(mod[m1,m2,L,mk])；(ⅳ)aºb(modm)Þ(a,m)=(b,m)；(ⅴ)acºbc(modm)，(c,m)=1Þaºb(modm)。证明结论(ⅰ)—(

4、ⅳ)的证明，留作习题。(ⅴ)由acºbc(modm)得到m│c(a-b)，再由(c,m)=1和第一章第三节定理4得到m│a-b，即aºb(modm)。证毕。例1设N=是整数N的十进制表示，即N=an10n+an-110n-1+L+a110+a0，则59(ⅰ)3│NÛ3；(ⅱ)9│NÛ9；(ⅲ)11│NÛ11；(ⅳ)13│NÛ13│。解由100º1，101º1，102º1，L(mod3)及式(2)可知N=(mod3)，由上式可得到结论(ⅰ)。结论(ⅱ)，(ⅲ)用同样方法证明。为了证明结论(ⅳ)，只需利用式(2)及100º1，101º-3，102

5、º-4，103º-1，L(mod13)和N=。注：一般地，在考虑使N=被m除的余数时，首先是求出正整数k，使得10kº-1或1(modm)，再将N=写成N=的形式，再利用式(2)。例2求N=被7整除的条件，并说明1123456789能否被7整除。解100º1，101º3，102º2，103º-1(mod7)，因此59即7½NÛ7½。由于789-456+123-1=455，7½455，所以7½1123456789。例3说明是否被641整除。解依次计算同余式22º4，24º16，28º256，216º154，232º-1(mod641)。因此º0

6、(mod641)，即641½。注：一般地，计算ab(modm)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化。例4求(25733+46)26被50除的余数。解利用定理4有(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。例5证明：若n是正整数，则13½42n+1+3n+2。解由42n+1+3n+2=4×42n+9×

7、3n=4×16n+9×3nº4×3n+9×3n=13×3nº0(mod13)得证。例6证明：若2a，n是正整数，则º1(mod2n+2)。(4)解设a=2k+1，当n=1时，有a2=(2k+1)2=4k(k+1)+1º1(mod23)，即式(4)成立。设式(4)对于n=k成立，则有59º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成立。例7设p是素数，a是整数，则由a2º1(modp

8、)可以推出aº1或aº-1(modp)。解由a2º1(modp)Þp½a2-1=(a+1)(a-1)，所以必是p½a+1或p½a-1，即aº-1(modp)或aº1