1、3. 1 同余的概念和性質(zhì),第三章 同 余,同余是數(shù)論中的一個基本概念。本章除介紹同余的基礎(chǔ)知識外，還要介紹它的一些應(yīng)用。,第一節(jié) 同余的基本性質(zhì),定義1 給定正整數(shù)m，如果整數(shù)a與b之差被m整除，則稱a與b對于模m同余，或稱a與b同余，模m，記為 a b (mod m)， 此時也稱b是a對模m的同余,如果整數(shù)a與b之差不能被m整除，則稱a與b對于模m不同余，或稱a與b不同余，模m，記為 a b (mod m)。,第一節(jié) 同余的基本性質(zhì),定理1 下面的三個敘述是等價的： () a b (mod m)； () 存在整數(shù)q，使得a = b qm； () 存在整數(shù)q1，q2，使得a = q1m r，

2、 b = q2m r，0 r m。,證明 留作習(xí)題。,第一節(jié) 同余的基本性質(zhì),定理2 同余具有下面的性質(zhì)： () (自反性) a a (mod m)； () (對稱性) a b (mod m) b a (mod m); () (傳遞性) a b，b c (mod m) a c (mod m)。,證明 留作習(xí)題。,第一節(jié) 同余的基本性質(zhì),定理3 設(shè)a，b，c，d是整數(shù)，并且 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，,第一節(jié) 同余的基本性質(zhì),因此

3、 m(a c) (b d)， 此即結(jié)論()；,() 由式(1)及定理1可知，存在整數(shù)q1與q2使得 a = b q1m，c = d q2m， 因此 ac = bd (q1q2m q1d q2b)m， 再利用定理1，推出結(jié)論()。證畢。,第一節(jié) 同余的基本性質(zhì),定理4 設(shè)ai，bi（0 i n）以及x，y都是整數(shù)，并且 x y (mod m)，ai bi (mod m)，0 i n， 則 (2),證明 留作習(xí)題。,第一節(jié) 同余的基本性質(zhì),定理5 下面的結(jié)論成立： () 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).,第一節(jié) 同余的基本性質(zhì),證明 結(jié)論()()的證明，留作習(xí)題。 () 由 ac bc (mod m) 得到mc(a b)，再由(c, m) = 1和第一章第三節(jié)定理4得到ma b，即 a b (mod m)。 證畢。,第一節(jié) 同余的基本性質(zhì),例1 設(shè)N =是整數(shù)N的十進制表示，即 N = an10n an 110n 1 a110 a0 ，則 ()

5、 3|N () 9|N () 11|N () 13|N ,第一節(jié) 同余的基本性質(zhì),證明 由 100 1，101 1，102 1， (mod 3) 及式(2)可知 N =(mod 3)， 由上式可得到結(jié)論()。,結(jié)論()，()用同樣方法證明。,第一節(jié) 同余的基本性質(zhì),為了證明結(jié)論()，只需利用式(2)及 100 1，101 3，102 4，103 1， (mod 13) 和,第一節(jié) 同余的基本性質(zhì),注: 一般地，在考慮使 被m除的余數(shù)時，首先是求出正整數(shù)k，使得 10k 1或1 (mod m)，,再將 寫成,的形式，再利用式(2)。,第一節(jié) 同余的基本性質(zhì),例2 求 被7整除的條件，并說明112

6、3456789能否被7整除。,解 100 1, 101 3, 102 2, 103 1 (mod 7),因此,即,第一節(jié) 同余的基本性質(zhì),由于 789 456 123 1 = 455，7455， 所以71123456789。,第一節(jié) 同余的基本性質(zhì),解 依次計算同余式 22 4，24 16，28 256，216 154，232 1 (mod 641)。,例3 說明 是否被641整除。,因此 0 (mod 641)，,即641 。,第一節(jié) 同余的基本性質(zhì),注: 一般地，計算ab (mod m)常是一件比較繁復(fù)的工作。但是，如果利用Euler定理或Fermat定理（見第四節(jié)）就可以適當(dāng)簡化。,第一

7、節(jié) 同余的基本性質(zhì),解 (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)， 即所求的余數(shù)是29。,例4 求(25733 46)26被50除的余數(shù)。,第一節(jié) 同余的基本性質(zhì),解 我們有 71 3，72 1，74 1 (mod 10)， 因此，若 77 r (mod 4)， 則,例5 求 的個位數(shù)。,現(xiàn)在 77 (1)7 1 3 (mod 4)，,第一節(jié) 同余的基本性質(zhì),所以由式(3)得到,即n的個位數(shù)是3。,注:一般地，若求對模m的同余，可分

8、以下步驟進行： () 求出整數(shù)k，使ak 1 (mod m)； () 求出正整數(shù)r, r k, 使得 bc r (mod k); () a r (mod m)。,第一節(jié) 同余的基本性質(zhì),證明 由 42n + 1 3 n + 2 = 442n 93 n = 416n 93 n 43n 93 n = 133 n 0 (mod 13),例6 證明: 若n是正整數(shù), 則1342n + 1 3 n + 2.,得證。,第一節(jié) 同余的基本性質(zhì),證明 設(shè)a = 2k 1，當(dāng)n = 1時，有 a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23)， 即式(4)成立。,例7 證明：若2 a，n是正

9、整數(shù)，則 1 (mod 2n + 2)。 (4),第一節(jié) 同余的基本性質(zhì),設(shè)式(4)對于n = k成立，則有 1 (mod 2k + 2) = 1 q2k + 2， 其中qZ，所以,=(1 q2k + 2)2=1 q 2k + 31(mod 2k + 3)， 其中q 是某個整數(shù)。這說明式(4)當(dāng)n = k 1也成立。 由歸納法知式(4)對所有正整數(shù)n成立。,第一節(jié) 同余的基本性質(zhì),證明 由 a2 1 (mod p) pa2 1 = (a 1)(a 1)， 所以必是 pa 1或pa 1，,例8 設(shè)p是素數(shù)，a是整數(shù)，則由a2 1(mod p)可以推出 a 1或a 1 (mod p)。,即a 1

10、(mod p)或a 1 (mod p)。,第一節(jié) 同余的基本性質(zhì),解 因為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 設(shè)n的十進制表示是 , 若792n,求x，y，z。,第一節(jié) 同余的基本性質(zhì),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。,第一節(jié) 同余的基本性質(zhì),這樣得到四個方程組：,其中a取值9或18，b取值0或11。在0 x, y 9的條件下解這四個方程組，得到