1、第五講 同余的概念和性質你會解答下面的問題嗎？問題1：今天是星期日，再過15天就是“六一”兒童節了，問“六一”兒童節是星期幾？這個問題并不難答.因為，一個星期有7天，而157=21，即1572+1，所以“六一”兒童節是星期一。問題2：1993年的元旦是星期五，1994年的元旦是星期幾？這個問題也難不倒我們.因為，1993年有365天，而365=752+1，所以1994年的元旦應該是星期六。問題1、2的實質是求用7去除某一總的天數后所得的余數.在日常生活中，時常要注意兩個整數用某一固定的自然數去除，所得的余數問題.這樣就產生了“同余”的概念.如問題1、2中的15與365除以7后，余數都是1，那么

2、我們就說15與365對于模7同余。同余定義：若兩個整數a、b被自然數m除有相同的余數，那么稱a、b對于模m同余，用式子表示為：ab（modm）. （*）上式可讀作：a同余于b，模m。同余式（*）意味著（我們假設ab）：a-b=mk，k是整數，即m（a-b）.例如：15365（mod7），因為365-15=350=750。5620（mod9），因為56-20=3694。900（mod10），因為90-090=109。由例我們得到啟發，a可被m整除，可用同余式表示為：a0（modm）。例如，表示a是一個偶數，可以寫a0（mod 2）表示b是一個奇數，可以寫b1（mod 2）補充定義：若m（a-b）

3、，就說a、b對模m不同余，用式子表示是：ab（modm）我們書寫同余式的方式，使我們想起等式，而事實上，同余式與等式在其性質上相似.同余式有如下一些性質（其中a、b、c、d是整數，而m是自然數）。性質1：aa（mod m），（反身性）這個性質很顯然.因為a-a=0=m0。性質2：若ab（mod m），那么ba（mod m），（對稱性）。性質3：若ab（mod m），bc（mod m），那么ac（mod m），（傳遞性）。性質4：若ab（mod m），cd（mod m），那么acbd（mod m），（可加減性）。性質5：若ab（mod m），cd（mod m），那么acbd（mod m）（可乘性

4、）。性質6：若ab（mod m），那么anbn（mod m），（其中n為自然數）。性質7：若acbc（mod m），（c，m）=1，那么ab（mod m），（記號（c，m）表示c與m的最大公約數）。注意同余式性質7的條件（c，m）1，否則像普通等式一樣，兩邊約去，就是錯的。例如610（mod 4），而35（mod 4），因為（2，4）1。請你自己舉些例子驗證上面的性質。同余是研究自然數的性質的基本概念，是可除性的符號語言。例1 判定288和214對于模37是否同余，74與20呢？解：288-214=74=372。288214（mod37）。74-20=54，而3754，7420（mod37）。

5、例2 求乘積4188141616除以13所得的余數。分析 若先求乘積，再求余數，計算量太大.利用同余的性質可以使“大數化小”，減少計算量。解：4182（mod13），8148（mod13），16164（mod13）， 根據同余的性質5可得：41881416162846412（mod13）。答：乘積4188141616除以13余數是12。例3 求14389除以7的余數。分析 同余的性質能使“大數化小”，凡求大數的余數問題首先考慮用同余的性質化大為小.這道題先把底數在同余意義下變小，然后從低次冪入手，重復平方，找找有什么規律。解法1：1433（mod7）14389389（mod 7）8964+16

6、+8+1而322（mod 7），344（mod7），38162（mod 7），3164（mod 7），332162（mod 7），3644（mod 7）。38936431638344235（mod 7），143895（mod 7）。答：14389除以7的余數是5。解法2：證得14389389（mod 7）后，363234241（mod 7），384（36）141（mod 7）。3893843431435（mod 7）。143895（mod 7）。例4 四盞燈如圖所示組成舞臺彩燈，且每30秒鐘燈的顏色改變一次，第一次上下兩燈互換顏色，第二次左右兩燈互換顏色，第三次又上下兩燈互換顏色，這樣一直進行

7、下去.請問開燈1小時四盞燈的顏色如何排列？分析 與解答經觀察試驗我們可以發現，每經過4次互換，四盞燈的顏色排列重復一次，而1小時=60分鐘=12030秒，所以這道題實質是求120除以4的余數，因為1200（mod 4），所以開燈1小時四盞燈的顏色排列剛好同一開始一樣。十位，上的數碼，再設M=a0a1an，求證：NM（mod 9）。分析 首先把整數N改寫成關于10的冪的形式，然后利用101（mod 9）。又 11（mod 9），101（mod 9），1021（mod 9），10n1（mod 9），上面這些同余式兩邊分別同乘以a0、a1、a2、an，再相加得：a0a110+a2102+an10na

8、0a1a2an（mod 9），即 NM（mod 9）.這道例題證明了十進制數的一個特有的性質：任何一個整數模9同余于它的各數位上數字之和。以后我們求一個整數被9除的余數，只要先計算這個整數各數位上數字之和，再求這個和被9除的余數即可。例如，求1827496被9除的余數，只要先求（1+827496），再求和被9除的余數。再觀察一下上面求和式.我們可以發現，和不一定要求出.因為和式中18，2+7，9被9除都余0，求余數時可不予考慮.這樣只需求46被9除的余數.因此，1827496被9除余數是1。有人時常利用十進制數的這個特性檢驗幾個數相加、相減、相乘的結果對不對，這種檢查方法叫：棄九法。棄九法最經

9、常地是用于乘法.我們來看一個例子。用棄九法檢驗乘式5483911749888511是否正確？因為 54835483112（mod 9），911791170（mod 9），所以 54839117200（mod 9）。但是 498885114+98+8+85+1+18（mod9），所以 5483911749888511，即乘積不正確。要注意的是棄九法只能知道原題錯誤或有可能正確，但不能保證一定正確。例如，987598+7+52（mod 9），487348734（mod 9），324756893+2+4+75+6+8+98（mod 9），這時，987548732432475689（mod 9）。但觀察個位數字立刻可以判定9875487332475689.因為末位數字5和3相乘不可能等于9。棄九法也可以用來檢驗除法和乘方的結果。例6 用棄九法檢驗下面的計算是否正確：2337245873123544。解：把除式轉化為：3544731223372458。 354435447（mod 9），731273124（mod 9）， 35447312741（mod 9），但 2337245823387（mod 9）。而 17（mod 9） 3544731223372458，即 2337245873123544。例7 求自然數210031014102的個位