初等數(shù)論教案6

1、第二章 同余式第一節(jié) 同余的基本概念與基本性質(zhì)教學(xué)目的：同余的基本定義與性質(zhì).教學(xué)重點：同余的性質(zhì).教學(xué)課時：2課時教學(xué)過程1、定義1 給定正整數(shù)m，如果整數(shù)a與b之差被m整除，則稱a與b對于模m同余，或稱a與b同余，關(guān)于模m，記為a b (mod m)，此時也稱b是a對模m的同余.如果整數(shù)a與b之差不能被m整除，則稱a與b對于模m不同余，或稱a與b不同余，模m，記為ab (mod m).2、定理1 下面的三個敘述是等價的：() 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的十進制表示，即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ù)k，使得10k -1或1 (mod m)，再將N =寫成N =的形式，再利用式(2).例2 求N =被7整除的條件，并說明1123456789能否被7整除.解：100 1，101

4、 3，102 2，103 -1 (mod 7)，因此即 7N 7.由于789 - 456 + 123 - 1 = 455，7455，所以71123456789.例3 說明是否被641整除.解：依次計算同余式22 4，24 16，28 256，216 154，232 -1 (mod 641).因此 0 (mod 641)，即641.注：一般地，計算ab (mod m)常是一件比較繁復(fù)的工作. 但是，如果利用Euler定理或Fermat定理就可以適當(dāng)簡化.例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 =的個位數(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的個位數(shù)是3.注：一般地，若求對模m的同余，可分以下步驟進行：() 求出整數(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時，有a2 = (2k + 1)2 = 4k(k + 1) + 1 1 (mod 23)，即式(4)成立.設(shè)式(4)對于n = k成立，則有 1 (mod 2k + 2) = 1 + q2k + 2，其中qZ

7、，所以= (1 + q2k + 2)2 = 1 + q 2k + 3 1 (mod 2k + 3)，其中q 是某個整數(shù).這說明式(4)當(dāng)n = k + 1也成立.由歸納法知式(4)對所有正整數(shù)n成立.例8 設(shè)p是素數(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的十進制表示是，若792n，求x，y，z.解：因為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)11n 11z - 5 + 4 - y + x - 3 + 1 = 3 - y + x 113 - y + x. (6)由于0 x, y 9，所以由式(5)與式(6)分別得出x + y