1、第二章 同余式第一節(jié) 同余的基本概念與基本性質(zhì)教學(xué)目的：同余的基本定義與性質(zhì).教學(xué)重點(diǎn)：同余的性質(zhì).教學(xué)課時(shí)：2課時(shí)教學(xué)過(guò)程1、定義1 給定正整數(shù)m，如果整數(shù)a與b之差被m整除，則稱(chēng)a與b對(duì)于模m同余，或稱(chēng)a與b同余，關(guān)于模m，記為a b (mod m)，此時(shí)也稱(chēng)b是a對(duì)模m的同余.如果整數(shù)a與b之差不能被m整除，則稱(chēng)a與b對(duì)于模m不同余，或稱(chēng)a與b不同余，模m，記為ab (mod m).2、定理1 下面的三個(gè)敘述是等價(jià)的：() a b (mod m)；() 存在整數(shù)q，使得a = b + qm；() 存在整數(shù)q1，q2，使得a = q1m + r，b = q2m + r，0 r 0 a b

2、(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, L, mk)；() a b (mod m) (a, m) = (b, m)；() ac bc (mod m)，(c, m) = 1 a b (mod m).證明：結(jié)論()()的證明，留作習(xí)題.() 由ac bc (mod m)得到mc(a - b)，再由(c, m) = 1，得到ma - b，即a b (mod m).證畢.例1 設(shè)N =是整數(shù)N的十進(jìn)制表示，即N = an10n + an - 110n - 1 + L + a

3、110 + a0 ，則() 3N 3；() 9N 9；() 11N 11；() 13N 13.解：由100 1，101 1，102 1，L (mod 3)及式(2)可知N =(mod 3)，由上式可得到結(jié)論().結(jié)論()，()用同樣方法證明.為了證明結(jié)論()，只需利用式(2)及100 1，101 -3，102 -4，103 -1，L (mod 13)和N = .注：一般地，在考慮使N =被m除的余數(shù)時(shí)，首先是求出正整數(shù)k，使得10k -1或1 (mod m)，再將N =寫(xiě)成N =的形式，再利用式(2).例2 求N =被7整除的條件，并說(shuō)明1123456789能否被7整除.解：100 1，101

4、 3，102 2，103 -1 (mod 7)，因此即 7N 7.由于789 - 456 + 123 - 1 = 455，7455，所以71123456789.例3 說(shuō)明是否被641整除.解：依次計(jì)算同余式22 4，24 16，28 256，216 154，232 -1 (mod 641).因此 0 (mod 641)，即641.注：一般地，計(jì)算ab (mod m)常是一件比較繁復(fù)的工作. 但是，如果利用Euler定理或Fermat定理就可以適當(dāng)簡(jiǎn)化.例4 求(25733 + 46)26被50除的余數(shù).解：利用定理4有(25733 + 46)26 (733 - 4)26 = 7(72)16 -

5、 426 7( -1)16 - 426 = (7 - 4)26 326 = 3(35)5 3(-7)5 = -37(72)2 -21 29 (mod 50)，即所求的余數(shù)是29.例5 求n =的個(gè)位數(shù).解：我們有71 -3，72 -1，74 1 (mod 10)，因此，若77 r (mod 4)，則n = (mod 10). (3)現(xiàn)在 (-1)7 -1 3 (mod 4)，所以由式(3)得到n = 73 (-3)3 -7 3 (mod 10)，即n的個(gè)位數(shù)是3.注：一般地，若求對(duì)模m的同余，可分以下步驟進(jìn)行：() 求出整數(shù)k，使ak 1 (mod m)；() 求出正整數(shù)r，r k，使得 r

6、(mod k)；() a r (mod m).例6 證明：若n是正整數(shù)，則1342n + 1 + 3 n + 2 .解：由42n + 1 + 3 n + 2 = 442n + 93 n = 416n + 93 n 43n + 93 n = 133 n 0 (mod 13)得證.例7 證明：若2a，n是正整數(shù)，則 1 (mod 2n + 2). (4)解：設(shè)a = 2k + 1，當(dāng)n = 1時(shí)，有a2 = (2k + 1)2 = 4k(k + 1) + 1 1 (mod 23)，即式(4)成立.設(shè)式(4)對(duì)于n = k成立，則有 1 (mod 2k + 2) = 1 + q2k + 2，其中qZ

7、，所以= (1 + q2k + 2)2 = 1 + q 2k + 3 1 (mod 2k + 3)，其中q 是某個(gè)整數(shù).這說(shuō)明式(4)當(dāng)n = k + 1也成立.由歸納法知式(4)對(duì)所有正整數(shù)n成立.例8 設(shè)p是素?cái)?shù)，a是整數(shù)，則由a2 1(mod p)可以推出a 1或a -1 (mod p).解：由a2 1 (mod p) pa2 - 1 = (a + 1)(a - 1)，所以必是pa + 1或pa - 1，即a -1 (mod p)或a 1 (mod p).例9 設(shè)n的十進(jìn)制表示是，若792n，求x，y，z.解：因?yàn)?92 = 8911，故792n 8n，9n及11n.我們有8n 8 z = 6，以及9n 91 + 3 + x + y + 4 + 5 + z = 19 + x + y 9x + y + 1， (5)11n 11z - 5 + 4 - y + x - 3 + 1 = 3 - y + x 113 - y + x. (6)由于0 x, y 9，所以由式(5)與式(6)分別得出x + y