同余的基本概念和性质.ppt

《同余的基本概念和性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§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=q

2、2mr，0r

3、ⅱ)由式(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)证明留作习题。第一节同余的基本性质定理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(m

4、od[m1,m2,,mk])；(ⅳ)ab(modm)(a,m)=(b,m)；(ⅴ)acbc(modm),(c,m)=1ab(modm).第一节同余的基本性质证明结论(ⅰ)—(ⅳ)的证明，留作习题。(ⅴ)由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a110a0，则(ⅰ)3

5、N(ⅱ)9

6、N(ⅲ)11

7、N(ⅳ)13

8、N第一节同余的基本性质证明由10

9、01，1011，1021，(mod3)及式(2)可知N=(mod3)，由上式可得到结论(ⅰ)。结论(ⅱ)，(ⅲ)用同样方法证明。第一节同余的基本性质为了证明结论(ⅳ)，只需利用式(2)及1001，1013，1024，1031，(mod13)和第一节同余的基本性质注:一般地，在考虑使被m除的余数时，首先是求出正整数k，使得10k1或1(modm)，再将写成的形式，再利用式(2)。第一节同余的基本性质例2求被7整除的条件，并说明1123456789能否被7整除。解1001,1013,1022,1031(m

10、od7),因此即第一节同余的基本性质由于7894561231=455，7455，所以71123456789。第一节同余的基本性质解依次计算同余式224，2416，28256，216154，2321(mod641)。例3说明是否被641整除。因此0(mod641)，即641。第一节同余的基本性质注:一般地，计算ab(modm)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化。第一节同余的基本性质解(2573346)26(7334)26=[7(72)164]2

11、6[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求的个位数。现在77(1)713(mod4)，第一节同余的基本性质所以由式(3)得到即n的个位数是3。注:一般地，若求对模m的同余，可分以下步骤进行：(ⅰ)求出整数k，使ak1(modm)；(ⅱ)求出正整数r,r<

12、k,使得bcr(modk);(ⅲ)ar(modm)。第一节同余的基本性质证明由42n+13n+2=442n93n=416n93n43n93n=133n0(mod1