同余的基本概念和性質(zhì)（課堂PPT）

1、.13. 1 同余的概念和性質(zhì).2第三章第三章 同同 余余 同余是數(shù)論中的一個(gè)基本概念。本同余是數(shù)論中的一個(gè)基本概念。本章除介紹同余的基礎(chǔ)知識(shí)外，還要章除介紹同余的基礎(chǔ)知識(shí)外，還要介紹它的一些應(yīng)用。介紹它的一些應(yīng)用。.3第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)定義定義1 給定正整數(shù)給定正整數(shù)m，如果整數(shù)，如果整數(shù)a與與b之差被之差被m整整除，則稱除，則稱a與與b對(duì)于模對(duì)于模m同余，或稱同余，或稱a與與b同余，同余，模模m，記為，記為a b (mod m)， 此時(shí)也稱此時(shí)也稱b是是a對(duì)模對(duì)模m的同余的同余 如果整數(shù)如果整數(shù)a與與b之差不能被之差不能被m整除，則稱整除，則稱a與與b對(duì)于模對(duì)于模m

2、不同余，或稱不同余，或稱a與與b不同余，模不同余，模m，記為記為 a b (mod m)。 .4第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)定理定理1 下面的三個(gè)敘述是等價(jià)的：下面的三個(gè)敘述是等價(jià)的：() a b (mod m)；() 存在整數(shù)存在整數(shù)q，使得，使得a = b qm；() 存在整數(shù)存在整數(shù)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

3、m) (a, m) = (b, m)；() ac bc(modm), (c, m) =1 a b (mod m).10第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)證明證明 結(jié)論結(jié)論()()的證明，留作習(xí)題。的證明，留作習(xí)題。() 由由ac bc (mod m)得到得到mc(a b)，再由，再由(c, m) = 1和第一章第三和第一章第三節(jié)定理節(jié)定理4得到得到ma b，即，即a b (mod m)。證畢。證畢。.11第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)例例1 設(shè)設(shè)N =是整數(shù)是整數(shù)N的十進(jìn)制表示，即的十進(jìn)制表示，即N = an10n an 110n 1 a110 a0 ，則，則() 3|N

4、() 9|N () 11|N () 13|N ;0|3 niia;0| 9 niia;)1(0|11 niiia.|13345012 aaaaaa.12第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)證明證明 由由100 1，101 1，102 1， (mod 3)及式及式(2)可知可知 N =(mod 3)，由上式可得到結(jié)論由上式可得到結(jié)論()。結(jié)論結(jié)論()，()用同樣方法證明。用同樣方法證明。.13第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)為了證明結(jié)論為了證明結(jié)論()，只需利用式，只需利用式(2)及及100 1，101 3，102 4，103 1， (mod 13)和和.101033450012

5、0121 aaaaaaaaaaNnn.14第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)注注: 一般地，在考慮使一般地，在考慮使 被被m除的余數(shù)時(shí)，首先是求出正整數(shù)除的余數(shù)時(shí)，首先是求出正整數(shù)k，使得，使得10k 1或或1 (mod m)，0121aaaaNnn 再將再將 寫成寫成0121aaaaNnn kkhkkkaaaaaaaN1010221200121的形式，再利用式的形式，再利用式(2)。.15第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)例例2 求求 被被7整除的條件，并整除的條件，并說(shuō)明說(shuō)明1123456789能否被能否被7整除。整除。 0121aaaaNnn 解解 100 1, 101

6、3, 102 2, 103 1 (mod 7),因因此此，)7(mod1010678345012334500120121 aaaaaaaaaaaaaaaaaaaNnn即即 678345012|7|7aaaaaaaaaN.16第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)由于由于789 456 123 1 = 455，7 455，所以所以7 1123456789。.17第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)解解 依次計(jì)算同余式依次計(jì)算同余式22 4，24 16，28 256，216 154，232 1 (mod 641)。例例3 說(shuō)明說(shuō)明 是否被是否被641整除。整除。 1252 1252 因此

7、因此 0 (mod 641)，即即641 。1252 .18第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)注注: 一般地，計(jì)算一般地，計(jì)算ab (mod m)常是一件比較繁常是一件比較繁復(fù)的工作。但是，如果利用復(fù)的工作。但是，如果利用Euler定理或定理或Fermat定理（見(jiàn)第四節(jié)）就可以適當(dāng)簡(jiǎn)化。定理（見(jiàn)第四節(jié)）就可以適當(dāng)簡(jiǎn)化。.19第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(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 = 3 7 (72)2 21 29 (mod 50)

8、， 即所求的余數(shù)是即所求的余數(shù)是29。例例4 求求(25733 46)26被被50除的余數(shù)。除的余數(shù)。 .20第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)解解 我們有我們有71 3，72 1，74 1 (mod 10)，因此，若因此，若77 r (mod 4)，則則 例例5 求求 的個(gè)位數(shù)。的個(gè)位數(shù)。 777 n)3()10(mod7777rn 現(xiàn)在現(xiàn)在 77 ( 1)7 1 3 (mod 4)，.21第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)所以由式所以由式(3)得到得到)10(mod37)3(773377 n即即n的個(gè)位數(shù)是的個(gè)位數(shù)是3。注注:一般地，若求對(duì)模一般地，若求對(duì)模m的同余，可分以

9、下步的同余，可分以下步驟進(jìn)行：驟進(jìn)行：() 求出整數(shù)求出整數(shù)k，使，使ak 1 (mod m)；() 求出正整數(shù)求出正整數(shù)r, r k, 使得使得 bc r (mod k);() a r (mod m)。cba.22第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)證明證明 由由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是正整數(shù)是正整數(shù), 則則13 42n + 1 3 n + 2.得證。得證。.23第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)證明證明 設(shè)設(shè)a = 2k 1，

10、當(dāng)，當(dāng)n = 1時(shí)，有時(shí)，有a2 = (2k 1)2 = 4k(k 1) 1 1 (mod 23)，即式即式(4)成立。成立。例例7 證明：若證明：若2 a，n是正整數(shù)，則是正整數(shù)，則 1 (mod 2n + 2)。 (4)| na2.24第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)設(shè)式設(shè)式(4)對(duì)于對(duì)于n = k成立，則有成立，則有 1 (mod 2k + 2) = 1 q2k + 2，其中其中q Z，所以，所以 =(1 q2k + 2)2=1 q 2k + 3 1(mod 2k + 3)，其中其中q 是某個(gè)整數(shù)。這說(shuō)明式是某個(gè)整數(shù)。這說(shuō)明式(4)當(dāng)當(dāng)n = k 1也也成立。成立。由歸納法知式

11、由歸納法知式(4)對(duì)所有正整數(shù)對(duì)所有正整數(shù)n成立。成立。12 ka.25第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)證明證明 由由a2 1 (mod p) p a2 1 = (a 1)(a 1)，所以必是所以必是p a 1或或p a 1，例例8 設(shè)設(shè)p是素?cái)?shù)，是素?cái)?shù)，a是整數(shù)，則由是整數(shù)，則由a2 1(mod p)可以推出可以推出 a 1或或a 1 (mod p)。即即a 1 (mod p)或或a 1 (mod p)。.26第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)解解 因?yàn)橐驗(yàn)?92 = 8 9 11，故，故792 n 8 n，9 n及及11 n。我們有我們有 8 n 8 z = 6，以及以及

12、 9 n 9 1 3 x y 4 5 z = 19 x y 9 x y 1， (5)例例9 設(shè)設(shè)n的十進(jìn)制表示是的十進(jìn)制表示是 , 若若792 n,求求x，y，z。zxy4513.27第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)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。.28第一節(jié)第一節(jié) 同余的基本性質(zhì)同余的基本性質(zhì)這樣得到四個(gè)方程組：這樣得到四個(gè)方程組： bxyayx31其中其中a取值取值9或或18，b取值取值0或或11。在。在0 x, y 9的條件下解這四個(gè)方程組，得到的條件下解這四個(gè)方程組，得到 x = 8，y = 0，z = 6。.29習(xí)習(xí) 題