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

《同余的基本概念和性质.ppt》由会员分享，可在线阅读，更多相关《同余的基本概念和性质.ppt（29页珍藏版）》请在三一办公上搜索。

1、3.1 同余的概念和性质,第三章 同 余,同余是数论中的一个基本概念。本章除介绍同余的基础知识外，还要介绍它的一些应用。,第一节 同余的基本性质,定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为a b(mod m)，此时也称b是a对模m的同余,如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为 a b(mod m)。,第一节 同余的基本性质,定理1 下面的三个叙述是等价的：()a b(mod m)；()存在整数q，使得a=b qm；()存在整数q1，q2，使得a=q1m r，b=q2m r，0 r m。,证

2、明 留作习题。,第一节 同余的基本性质,定理2 同余具有下面的性质：()(自反性)a a(mod m)；()(对称性)a b(mod m)b a(mod m);()(传递性)a b，b c(mod m)a c(mod m)。,证明 留作习题。,第一节 同余的基本性质,定理3 设a，b，c，d是整数，并且a b(mod m)，c d(mod m)，(1)则()a c b d(mod m)；()ac bd(mod m)。,证明()由式(1)及定义1可知 ma b，mc d，,第一节 同余的基本性质,因此 m(a c)(b d)，此即结论()；,()由式(1)及定理1可知，存在整数q1与q2使得a=

3、b q1m，c=d q2m，因此ac=bd(q1q2m q1d q2b)m，再利用定理1，推出结论()。证毕。,第一节 同余的基本性质,定理4 设ai，bi（0 i n）以及x，y都是整数，并且x y(mod m)，ai bi(mod m)，0 i n，则(2),证明 留作习题。,第一节 同余的基本性质,定理5 下面的结论成立：()a b(mod m),dm,d0 a b(mod d);()a b(mod m),k 0,kN ak bk(mod mk)；()a b(mod mi)，1 i k a b(mod m1,m2,mk)；()a b(mod m)(a,m)=(b,m)；()ac bc(m

4、odm),(c,m)=1 a b(mod m).,第一节 同余的基本性质,证明 结论()()的证明，留作习题。()由ac bc(mod m)得到mc(a b)，再由(c,m)=1和第一章第三节定理4得到ma b，即a b(mod m)。证毕。,第一节 同余的基本性质,例1 设N=是整数N的十进制表示，即N=an10n an 110n 1 a110 a0，则()3|N()9|N()11|N()13|N,第一节 同余的基本性质,证明 由100 1，101 1，102 1，(mod 3)及式(2)可知 N=(mod 3)，由上式可得到结论()。,结论()，()用同样方法证明。,第一节 同余的基本性质

5、,为了证明结论()，只需利用式(2)及100 1，101 3，102 4，103 1，(mod 13)和,第一节 同余的基本性质,注:一般地，在考虑使 被m除的余数时，首先是求出正整数k，使得10k 1或1(mod m)，,再将 写成,的形式，再利用式(2)。,第一节 同余的基本性质,例2 求 被7整除的条件，并说明1123456789能否被7整除。,解 100 1,101 3,102 2,103 1(mod 7),因此,即,第一节 同余的基本性质,由于789 456 123 1=455，7455，所以71123456789。,第一节 同余的基本性质,解 依次计算同余式22 4，24 16，2

6、8 256，216 154，232 1(mod 641)。,例3 说明 是否被641整除。,因此 0(mod 641)，,即641。,第一节 同余的基本性质,注:一般地，计算ab(mod m)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化。,第一节 同余的基本性质,解(25733 46)26(733 4)26=7(72)16 426 7(1)16 426=(7 4)26 326=3(35)5 3(7)5=37(72)2 21 29(mod 50)，即所求的余数是29。,例4 求(25733 46)26被50除的余数。,第一节 同余的基本性质,解

7、 我们有71 3，72 1，74 1(mod 10)，因此，若77 r(mod 4)，则,例5 求 的个位数。,现在 77(1)7 1 3(mod 4)，,第一节 同余的基本性质,所以由式(3)得到,即n的个位数是3。,注:一般地，若求对模m的同余，可分以下步骤进行：()求出整数k，使ak 1(mod m)；()求出正整数r,r k,使得 bc r(mod k);()a r(mod m)。,第一节 同余的基本性质,证明 由42n+1 3 n+2=442n 93 n=416n 93 n 43n 93 n=133 n 0(mod 13),例6 证明:若n是正整数,则1342n+1 3 n+2.,得

8、证。,第一节 同余的基本性质,证明 设a=2k 1，当n=1时，有a2=(2k 1)2=4k(k 1)1 1(mod 23)，即式(4)成立。,例7 证明：若2 a，n是正整数，则 1(mod 2n+2)。(4),第一节 同余的基本性质,设式(4)对于n=k成立，则有 1(mod 2k+2)=1 q2k+2，其中qZ，所以,=(1 q2k+2)2=1 q 2k+31(mod 2k+3)，其中q 是某个整数。这说明式(4)当n=k 1也成立。由归纳法知式(4)对所有正整数n成立。,第一节 同余的基本性质,证明 由a2 1(mod p)pa2 1=(a 1)(a 1)，所以必是pa 1或pa 1，

9、,例8 设p是素数，a是整数，则由a2 1(mod p)可以推出 a 1或a 1(mod p)。,即a 1(mod p)或a 1(mod p)。,第一节 同余的基本性质,解 因为792=8911，故792n 8n，9n及11n。我们有 8n 8 z=6，,以及 9n 91 3 x y 4 5 z=19 x y 9x y 1，(5),例9 设n的十进制表示是,若792n,求x，y，z。,第一节 同余的基本性质,11n 11z 5 4 y x 3 1=3 y x 113 y x。(6),由于0 x,y 9，所以由式(5)与式(6)分别得出x y 1=9或18，3 y x=0或11。,第一节 同余的基本性质,这样得到四个方程组：,其中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，求与。,