第5講 同余的概念和性質(zhì)

1、-作者xxxx-日期xxxx第5講 同余的概念和性質(zhì)【精品文檔】第5講 同余的概念和性質(zhì)解題思路：理解并熟記同余的性質(zhì)，運(yùn)用同余性質(zhì)把數(shù)化小、化易。同余定義：若兩個(gè)整數(shù)a、b被自然數(shù)m除有相同的余數(shù)，那么稱a、b對(duì)于模m同余，用式子表示為： ab（modm）. 性質(zhì)1：若ab（mod m），bc（mod m），那么ac（mod m），（傳遞性）。性質(zhì)2：若ab（mod m），cd（mod m），那么a±cb±d（mod m），（可加減性）。性質(zhì)3：若ab（mod m），cd（mod m），那么acbd（mod m）（可乘性）。性質(zhì)4：若ab（mod m），那么anbn（mo

2、d m），（其中n為自然數(shù)）。性質(zhì)5：若acbc（mod m），（c，m）=1，那么ab（mod m），（記號(hào)（c，m）表示c與m的最大公約數(shù)）。例1 判定288和214對(duì)于模37是否同余，74與20呢？例2 求乘積418×814×1616除以13所得的余數(shù)。例3 求14389除以7的余數(shù)。例4 四盞燈如圖所示組成舞臺(tái)彩燈，且每30秒鐘燈的顏色改變一次，第一次上下兩燈互換顏色，第二次左右兩燈互換顏色，第三次又上下兩燈互換顏色，這樣一直進(jìn)行下去.請(qǐng)問(wèn)開(kāi)燈1小時(shí)四盞燈的顏色如何排列？十位，上的數(shù)碼，再設(shè)M=，求證：NM（mod 9）例6 求自然數(shù)的個(gè)位數(shù)字。習(xí)題1.驗(yàn)證對(duì)于任意

3、整數(shù)a、b，式子ab（mod1）成立，并說(shuō)出它的含義。2.已知自然數(shù)a、b、c，其中c3，a除以c余1，b除以c余2，則ab除以c余多少？六月一日是星期二，這一年的十月一日是星期幾？555555553333被7除的余數(shù)。5.所有自然數(shù)如下圖排列.問(wèn)300位于哪個(gè)字母下面？6. 數(shù)，被13除余多少？7.求1993100的個(gè)位數(shù)字.第五講 同余的概念和性質(zhì)你會(huì)解答下面的問(wèn)題嗎？問(wèn)題1：今天是星期日，再過(guò)15天就是“六·一”兒童節(jié)了，問(wèn)“六·一”兒童節(jié)是星期幾？這個(gè)問(wèn)題并不難答.因?yàn)?，一個(gè)星期有7天，而15÷7=21，即157×2+1，所以“六·一”

4、兒童節(jié)是星期一。問(wèn)題2：1993年的元旦是星期五，1994年的元旦是星期幾？這個(gè)問(wèn)題也難不倒我們.因?yàn)椋?993年有365天，而365=7×52+1，所以1994年的元旦應(yīng)該是星期六?！巴唷钡母拍?如問(wèn)題1、2中的15與365除以7后，余數(shù)都是1，那么我們就說(shuō)15與365對(duì)于模7同余。同余定義：若兩個(gè)整數(shù)a、b被自然數(shù)m除有相同的余數(shù)，那么稱a、b對(duì)于模m同余，用式子表示為：ab（modm）. （*）上式可讀作：a同余于b，模m。同余式（*）意味著（我們假設(shè)ab）：a-b=mk，k是整數(shù)，即m（a-b）.例如：15365（mod7），因?yàn)?65-15=350=7×50。5

5、620（mod9），因?yàn)?6-20=369×4。900（mod10），因?yàn)?0-090=10×9。由例我們得到啟發(fā)，a可被m整除，可用同余式表示為：a0（modm）。例如，表示a是一個(gè)偶數(shù)，可以寫(xiě)a0（mod 2）表示b是一個(gè)奇數(shù)，可以寫(xiě)b1（mod 2）補(bǔ)充定義：若m（a-b），就說(shuō)a、b對(duì)模m不同余，用式子表示是：ab（modm）我們書(shū)寫(xiě)同余式的方式，使我們想起等式，而事實(shí)上，同余式與等式在其性質(zhì)上相似.同余式有如下一些性質(zhì)（其中a、b、c、d是整數(shù)，而m是自然數(shù)）。性質(zhì)1：aa（mod m），（反身性）這個(gè)性質(zhì)很顯然.因?yàn)閍-a=0=m·0。性質(zhì)2：若ab（

6、mod m），那么ba（mod m），（對(duì)稱性）。性質(zhì)3：若ab（mod m），bc（mod m），那么ac（mod m），（傳遞性）。性質(zhì)4：若ab（mod m），cd（mod m），那么a±cb±d（mod m），（可加減性）。性質(zhì)5：若ab（mod m），cd（mod m），那么acbd（mod m）（可乘性）。性質(zhì)6：若ab（mod m），那么anbn（mod m），（其中n為自然數(shù)）。性質(zhì)7：若acbc（mod m），（c，m）=1，那么ab（mod m），（記號(hào)（c，m）表示c與m的最大公約數(shù)）。注意同余式性質(zhì)7的條件（c，m）1，否則像普通等式一樣，兩邊約去，

7、就是錯(cuò)的。例如610（mod 4），而35（mod 4），因?yàn)椋?，4）1。請(qǐng)你自己舉些例子驗(yàn)證上面的性質(zhì)。同余是研究自然數(shù)的性質(zhì)的基本概念，是可除性的符號(hào)語(yǔ)言。例1 判定288和214對(duì)于模37是否同余，74與20呢？解：288-214=74=37×2。288214（mod37）。74-20=54，而3754，7420（mod37）。例2 求乘積418×814×1616除以13所得的余數(shù)。分析 “大數(shù)化小”，減少計(jì)算量。解：4182（mod13），8148（mod13），16164（mod13）， 根據(jù)同余的性質(zhì)5可得：418×814×161

8、62×8×46412（mod13）。答：乘積418×814×1616除以13余數(shù)是12。例3 求14389除以7的余數(shù)。分析 同余的性質(zhì)能使“大數(shù)化小”，凡求大數(shù)的余數(shù)問(wèn)題首先考慮用同余的性質(zhì)化大為小.這道題先把底數(shù)在同余意義下變小，然后從低次冪入手，重復(fù)平方，找找有什么規(guī)律。解法1：1433（mod7）14389389（mod 7）8964+16+8+1而322（mod 7），344（mod7），38162（mod 7），3164（mod 7），332162（mod 7），3644（mod 7）。389364·316·38·

9、;34×4×2×35（mod 7），143895（mod 7）。答：14389除以7的余數(shù)是5。解法2：證得14389389（mod 7）后，3632×342×41（mod 7），384（36）141（mod 7）。389384·34·31×4×35（mod 7）。143895（mod 7）。例4 四盞燈如圖所示組成舞臺(tái)彩燈，且每30秒鐘燈的顏色改變一次，第一次上下兩燈互換顏色，第二次左右兩燈互換顏色，第三次又上下兩燈互換顏色，這樣一直進(jìn)行下去.請(qǐng)問(wèn)開(kāi)燈1小時(shí)四盞燈的顏色如何排列？分析 與解答經(jīng)觀察試驗(yàn)我

10、們可以發(fā)現(xiàn)，每經(jīng)過(guò)4次互換，四盞燈的顏色排列重復(fù)一次，而1小時(shí)=60分鐘=120×30秒，所以這道題實(shí)質(zhì)是求120除以4的余數(shù)，因?yàn)?200（mod 4），所以開(kāi)燈1小時(shí)四盞燈的顏色排列剛好同一開(kāi)始一樣。十位，上的數(shù)碼，再設(shè)M=a0a1an，求證：NM（mod 9）。分析 首先把整數(shù)N改寫(xiě)成關(guān)于10的冪的形式，然后利用101（mod 9）。又 11（mod 9），101（mod 9），1021（mod 9），10n1（mod 9），上面這些同余式兩邊分別同乘以a0、a1、a2、an，再相加得：a0a1×10+a2×102+an×10na0a1a2an（m

11、od 9），即 NM（mod 9）.這道例題證明了十進(jìn)制數(shù)的一個(gè)特有的性質(zhì)：任何一個(gè)整數(shù)模9同余于它的各數(shù)位上數(shù)字之和。以后我們求一個(gè)整數(shù)被9除的余數(shù)，只要先計(jì)算這個(gè)整數(shù)各數(shù)位上數(shù)字之和，再求這個(gè)和被9除的余數(shù)即可。例如，求1827496被9除的余數(shù)，只要先求（1+827496），再求和被9除的余數(shù)。再觀察一下上面求和式.我們可以發(fā)現(xiàn)，和不一定要求出.因?yàn)楹褪街?8，2+7，9被9除都余0，求余數(shù)時(shí)可不予考慮.這樣只需求46被9除的余數(shù).因此，1827496被9除余數(shù)是1。有人時(shí)常利用十進(jìn)制數(shù)的這個(gè)特性檢驗(yàn)幾個(gè)數(shù)相加、相減、相乘的結(jié)果對(duì)不對(duì)，這種檢查方法叫：棄九法。棄九法最經(jīng)常地是用于乘法.我

12、們來(lái)看一個(gè)例子。用棄九法檢驗(yàn)乘式5483×911749888511是否正確？因?yàn)?54835483112（mod 9），911791170（mod 9），所以 5483×91172×00（mod 9）。但是 498885114+98+8+85+1+18（mod9），所以 5483×911749888511，即乘積不正確。要注意的是棄九法只能知道原題錯(cuò)誤或有可能正確，但不能保證一定正確。例如，987598+7+52（mod 9），487348734（mod 9），324756893+2+4+75+6+8+98（mod 9），這時(shí)，9875×487

13、32×432475689（mod 9）。但觀察個(gè)位數(shù)字立刻可以判定9875×487332475689.因?yàn)槟┪粩?shù)字5和3相乘不可能等于9。棄九法也可以用來(lái)檢驗(yàn)除法和乘方的結(jié)果。例6 用棄九法檢驗(yàn)下面的計(jì)算是否正確：23372458÷73123544。解：把除式轉(zhuǎn)化為：3544×731223372458。 354435447（mod 9），731273124（mod 9）， 3544×73127×41（mod 9），但 2337245823387（mod 9）。而 17（mod 9） 3544×731223372458，即 2

14、3372458÷73123544。例7 求自然數(shù)210031014102的個(gè)位數(shù)字。分析 求自然數(shù)的個(gè)位數(shù)字即是求這個(gè)自然數(shù)除以10的余數(shù)問(wèn)題。解：210024×256256（mod 10），310134×25·31125·313（mod 10），4102（22）100·426·66（mod 10）， 2100310141026365（mod 10），即自然數(shù)210031014102的個(gè)位數(shù)字是5. 習(xí)題五1.驗(yàn)證對(duì)于任意整數(shù)a、b，式子ab（mod1）成立，并說(shuō)出它的含義。2.已知自然數(shù)a、b、c，其中c3，a除

15、以c余1，b除以c余2，則ab除以c余多少？3.1993年的六月一日是星期二，這一年的十月一日是星期幾？555555553333被7除的余數(shù)。5.所有自然數(shù)如下圖排列.問(wèn)300位于哪個(gè)字母下面？6.數(shù)，被13除余多少？（提示：先試除，可知13|111111，而19931（mod 6）。7.用棄九法檢驗(yàn)下面運(yùn)算是否正確：845×372=315340；12345×67891=838114385；1144192613÷2899739459。100的個(gè)位數(shù)字.  習(xí)題五解答1.例：1|a-b，23（mod 1），715（mod 1），式子ab（mod 1）的含義是：任意整數(shù)a、b對(duì)模1同余.整數(shù)是模1的同余類(lèi)。2.解：a1（mod c），b2（mod c），ab2（mod c）即ab除以c余2。3.19