同余的基本概念和性质

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不同余，或称

2、不同余，或称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 0 a b (mod d);() a b (mod m), k 0, k N ak bk (mod mk)；() a b (mod mi )，1 i k a b (mod m1, m2, , mk)；() a b (mod m) (a, m

3、) = (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 ，则，则() 3|N () 9|N () 11|

4、N () 13|N ;0|3 niia;0| 9 niia;)1(0|11 niiia.|13345012 aaaaaa第一节第一节 同余的基本性质同余的基本性质证明证明 由由100 1，101 1，102 1， (mod 3)及式及式(2)可知可知 N =(mod 3)，由上式可得到结论由上式可得到结论()。结论结论()，()用同样方法证明。用同样方法证明。第一节第一节 同余的基本性质同余的基本性质为了证明结论为了证明结论()，只需利用式，只需利用式(2)及及100 1，101 3，102 4，103 1， (mod 13)和和.1010334500120121 aaaaaaaaaaNnn第

5、一节第一节 同余的基本性质同余的基本性质注注: 一般地，在考虑使一般地，在考虑使 被被m除的余数时，首先是求出正整数除的余数时，首先是求出正整数k，使得，使得10k 1或或1 (mod m)，0121aaaaNnn 再将再将 写成写成0121aaaaNnn kkhkkkaaaaaaaN1010221200121的形式，再利用式的形式，再利用式(2)。第一节第一节 同余的基本性质同余的基本性质例例2 求求 被被7整除的条件，并整除的条件，并说明说明1123456789能否被能否被7整除。整除。 0121aaaaNnn 解解 100 1, 101 3, 102 2, 103 1 (mod 7),因

6、因此此，)7(mod1010678345012334500120121 aaaaaaaaaaaaaaaaaaaNnn即即 678345012|7|7aaaaaaaaaN第一节第一节 同余的基本性质同余的基本性质由于由于789 456 123 1 = 455，7 455，所以所以7 1123456789。第一节第一节 同余的基本性质同余的基本性质解解 依次计算同余式依次计算同余式22 4，24 16，28 256，216 154，232 1 (mod 641)。例例3 说明说明 是否被是否被641整除。整除。 1252 1252 因此因此 0 (mod 641)，即即641 。1252 第一节第

7、一节 同余的基本性质同余的基本性质注注: 一般地，计算一般地，计算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 = 3 7 (72)2 21 29 (mod 50)， 即所求的余数是即所求的余数是29。例例4 求求(25733 46)26

8、被被50除的余数。除的余数。 第一节第一节 同余的基本性质同余的基本性质解解 我们有我们有71 3，72 1，74 1 (mod 10)，因此，若因此，若77 r (mod 4)，则则 例例5 求求 的个位数。的个位数。 777 n)3()10(mod7777rn 现在现在 77 ( 1)7 1 3 (mod 4)，第一节第一节 同余的基本性质同余的基本性质所以由式所以由式(3)得到得到)10(mod37)3(773377 n即即n的个位数是的个位数是3。注注:一般地，若求对模一般地，若求对模m的同余，可分以下步的同余，可分以下步骤进行：骤进行：() 求出整数求出整数k，使，使ak 1 (mo

9、d m)；() 求出正整数求出正整数r, r k, 使得使得 bc r (mod k);() a r (mod m)。cba第一节第一节 同余的基本性质同余的基本性质证明证明 由由42n + 1 3 n + 2 = 4 42n 9 3 n = 4 16n 9 3 n 4 3n 9 3 n = 13 3 n 0 (mod 13)例例6 证明证明: 若若n是正整数是正整数, 则则13 42n + 1 3 n + 2.得证。得证。第一节第一节 同余的基本性质同余的基本性质证明证明 设设a = 2k 1，当，当n = 1时，有时，有a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23)

10、，即式即式(4)成立。成立。例例7 证明：若证明：若2 a，n是正整数，则是正整数，则 1 (mod 2n + 2)。 (4)| na2第一节第一节 同余的基本性质同余的基本性质设式设式(4)对于对于n = k成立，则有成立，则有 1 (mod 2k + 2) = 1 q2k + 2，其中其中q Z，所以，所以 =(1 q2k + 2)2=1 q 2k + 3 1(mod 2k + 3)，其中其中q 是某个整数。这说明式是某个整数。这说明式(4)当当n = k 1也也成立。成立。由归纳法知式由归纳法知式(4)对所有正整数对所有正整数n成立。成立。12 ka第一节第一节 同余的基本性质同余的基本

11、性质证明证明 由由a2 1 (mod p) p a2 1 = (a 1)(a 1)，所以必是所以必是p a 1或或p a 1，例例8 设设p是素数，是素数，a是整数，则由是整数，则由a2 1(mod p)可以推出可以推出 a 1或或a 1 (mod p)。即即a 1 (mod p)或或a 1 (mod p)。第一节第一节 同余的基本性质同余的基本性质解解 因为因为792 = 8 9 11，故，故792 n 8 n，9 n及及11 n。我们有我们有 8 n 8 z = 6，以及以及 9 n 9 1 3 x y 4 5 z = 19 x y 9 x y 1， (5)例例9 设设n的十进制表示是的十

12、进制表示是 , 若若792 n,求求x，y，z。zxy4513第一节第一节 同余的基本性质同余的基本性质11 n 11 z 5 4 y x 3 1 = 3 y x 11 3 y x。 (6)由于由于0 x, y 9，所以由式，所以由式(5)与式与式(6)分别得出分别得出x y 1 = 9或或18，3 y x = 0或或11。第一节第一节 同余的基本性质同余的基本性质这样得到四个方程组：这样得到四个方程组： bxyayx31其中其中a取值取值9或或18，b取值取值0或或11。在。在0 x, y 9的条件下解这四个方程组，得到的条件下解这四个方程组，得到 x = 8，y = 0，z = 6。习习 题题 一一1