《同余的基本概念和性质PPT课件.ppt》由会员分享，可在线阅读，更多相关《同余的基本概念和性质PPT课件.ppt（29页珍藏版）》请在三一文库上搜索。
1、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
2、r， b = q2m r，0 r m。,证明 留作习题。,第一节 同余的基本性质,定理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，,第一节 同余的基本性质,
3、因此 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 (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
4、 (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(modm), (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 ，则
5、() 3|N () 9|N () 11|N () 13|N ,第一节 同余的基本性质,证明 由 100 1，101 1，102 1， (mod 3) 及式(2)可知 N =(mod 3)， 由上式可得到结论()。,结论()，()用同样方法证明。,第一节 同余的基本性质,为了证明结论()，只需利用式(2)及 100 1，101 3，102 4，103 1， (mod 13) 和,第一节 同余的基本性质,注: 一般地，在考虑使 被m除的余数时，首先是求出正整数k，使得 10k 1或1 (mod m)，,再将 写成,的形式，再利用式(2)。,第一节 同余的基本性质,例2 求 被7整除的条件，并说明1
6、123456789能否被7整除。,解 100 1, 101 3, 102 2, 103 1 (mod 7),因此,即,第一节 同余的基本性质,由于 789 456 123 1 = 455，7455， 所以71123456789。,第一节 同余的基本性质,解 依次计算同余式 22 4，24 16，28 256，216 154，232 1 (mod 641)。,例3 说明 是否被641整除。,因此 0 (mod 641)，,即641 。,第一节 同余的基本性质,注: 一般地，计算ab (mod m)常是一件比较繁复的工作。但是，如果利用Euler定理或Fermat定理（见第四节）就可以适当简化。,
7、第一节 同余的基本性质,解 (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除的余数。,第一节 同余的基本性质,解 我们有 71 3，72 1，74 1 (mod 10)， 因此，若 77 r (mod 4)， 则,例5 求 的个位数。,现在 77 (1)7 1 3 (mod 4)，,第一节 同余的基本性质,所以由式(3)得到,即n的个位数是3。,注:一般地，若求对模m的同余，
8、可分以下步骤进行： () 求出整数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.,得证。,第一节 同余的基本性质,证明 设a = 2k 1，当n = 1时，有 a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23)， 即式(4)成立。,例7 证明：若2 a，n
9、是正整数，则 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，,例8 设p是素数，a是整数，则由a2 1(mod p)可以推出 a 1或a 1 (mod p)。,即a
10、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 ，求与。,