第38講應(yīng)用同余問題

1、第 38 講 應(yīng)用同余問題一、知識要點同余這個概念最初是由偉大的德國數(shù)學家高斯發(fā)現(xiàn)的。同余的定義是這樣的：兩個整數(shù)a, b,如果它們除以同一自然數(shù) m所得的余數(shù)想同，則稱a, b對于模m同余。 記作：a= b (mod m)。讀做：a同余于b模m。比如，12除以5, 47除以5,它們有相同 的余數(shù)2,這時我們就說，對于除數(shù) 5, 12和47同余，記做12三47 ( mod 5)。同余的性質(zhì)比較多,主要有以下一些：性質(zhì)( 1)：對于同一個除數(shù),兩個數(shù)之和(或差)與它們的余數(shù)之和(或差)同余。比 如： 32 除以 5 余數(shù)是 2, 19 除以 5 余數(shù)是 4,兩個余數(shù)的和是 2+4=6。 “32+

2、19”除以 5 的余 數(shù)就恰好等于它們的余數(shù)和 6 除以 5 的余數(shù)。也就是說,對于除數(shù) 5,“32+19”與它們的余 數(shù)和 “2+4” 同余，用符號表示就是：32= 2 (mod 5), 19= 4 (mod 5), 32+192+4= 1 (mod5)兩個數(shù)的乘積與它們余數(shù)的乘積同余。性質(zhì)( 2)：對于同一個除數(shù)，如果有兩個整數(shù)同余，那么它們的差就一定能被這個除數(shù)性質(zhì)( 3)：對于同一個除數(shù)，整除。如果兩個整數(shù)同余，那么它們的乘方仍然同余。性質(zhì)( 4)：對于同一個除數(shù)，應(yīng)用同余性質(zhì)幾萼體的關(guān)鍵是要在正確理解的基礎(chǔ)上靈活運用同余性質(zhì)。把求一個較大 的數(shù)除以某數(shù)的余數(shù)問題轉(zhuǎn)化為求一個較小的數(shù)除

3、以這個數(shù)的余數(shù)，使復雜的題變簡單，使 困難的題變?nèi)菀?。二、精講精練【例題 1】求 1992X 59 除以 7 的余數(shù)。應(yīng)用同余性質(zhì)( 2)可將 1992X 59 轉(zhuǎn)化為求 1992 除以 7和 59 除以 7 的余數(shù)的乘積，使 計算簡化。1992除以7余4, 59除以7余3。根據(jù)同余性質(zhì)，“4X 3”除以7的余數(shù)與“ 1992 X 59”除以 7的余數(shù)應(yīng)該是相同的，通過求“ 4X 3”除以 7 的余數(shù)就可知道 1992X 59 除以 7 的余數(shù)了。因為 1992X 59三4X 3三 5 ( mod 7)所以 1992X 59 除以 7 的余數(shù)是 5。 練習 1 ：1、求4217X 364除以6

4、的余數(shù)。2、求1339655X 12除以13的余數(shù)。3、求879X 4376X 5283除以11的余數(shù)。例題 2】已知 2001 年的國慶節(jié)是星期一，求 2010年的國慶節(jié)是星期幾？一星期有 7天，要求 2010年的國慶節(jié)是星期幾， 就要求從 2001年到 2010年的國慶節(jié)的總天數(shù)被 7 除的余數(shù)就行了。但在甲酸中，如果我們能充分利用同余性質(zhì)，就可以不必算出 這個總天數(shù)。2001年國慶節(jié)到2010年國慶節(jié)之間共有2個閏年7個平年，即有“366X 2+365X 7”天。因為 366X 2三2X 2三4 ( mod 7), 365X 7三 1 X 7三0 (mod 7), 366X 2+365X

5、 7三2X 2+1X 7三 4+0= 4 (mod 7)答：2010年的國慶節(jié)是星期五。練習 2：1 、已知 2002 年元旦是星期二。求 2008 年元旦是星期幾？2、已知 2002年的“七月一日”是星期一。求 2015年的“十月一日”是星期幾？3、今天是星期四，再過 365的 1 5次方是星期幾？例題 3】求 2001的 2003次方除以 13的余數(shù)。2001除以13余12,即2001三12 (mod 13)。根據(jù)同余性質(zhì)(4),可知2001的2003次方三12的2003次方(mod 13),但12的2003次方仍然是一個很大的值，要求它的余數(shù)比較 困難。這時的關(guān)鍵就是要找出12的幾次方對

6、模13與1是同余的。經(jīng)試驗可知12的平方三1(mod13),而 2003三2X 1001+1。所以(12 的平方)的 1001 次方三 1 的 1001 (mod13),即 12的2002次方三1 ( mod13),而12的2003次方三12的2002次方X 12。根據(jù)同余性質(zhì)(2) 可知 12 的 2002 次方 X 12三 1X 12三 12 ( mod 13)因為：2001的2003次方三12的2003次方(mod 13)12 的平方三 1 (mod 13),而 2003三2X 1001+112 的 2003 次方三 12 的 2002 次方 X 12三 1X 12三 12 (mod 1

7、3)所以 2001 的 2003次方除以 13 的余數(shù)是 12。練習 3：1、求 12的 200次方除以 13的余數(shù)。2、求 3的 92次方除以 21余幾。3、9個小朋友坐成一圈，要把 35的 7次方粒瓜子平均分給他們，最后剩下幾粒？【例題4】自然數(shù)16520, 14903, 14177除以m的余數(shù)相同，m最大是多少？自然數(shù)16520, 14903, 14177除以m的余數(shù)相同，換句話說就是 16520三14903三14177 (mod m。根據(jù)同余性質(zhì)(3),這三個餓數(shù)同余，那么它們的差就能被m整除。要求m最大是多少，就是求它們差的最大公約數(shù)是多少？因為 16520 14903=1617=3

8、X 7 的平方 X 1116520 14177=2343=3X 11 X 7114903 14177=726=2X 3X 11 的平方M是這些差的公約數(shù)，m最大是3X 11=33。練習 4：1、若 2836、4582、5164、6522 四個整數(shù)都被同一個兩位數(shù)相除，所得的余數(shù)相同。除 數(shù)是多少？2、一個整數(shù)除 226、192、141 都得到相同的余數(shù)，且余數(shù)不為 0，這個整數(shù)是幾？3、當1991和1769除以某一個自然數(shù) m時，余數(shù)分別為2和1,那么m最小是多少?【例題 5】某數(shù)用6除余3，用7除余5，用8除余1，這個數(shù)最小是幾?我們可從較大的除數(shù)開始嘗試。首先考慮與 1模8同余的數(shù)，9三1

9、 (mod 8),但9輸以 7余數(shù)不是5,所以某數(shù)不是9。17三1 (mod8), 17除以7的余數(shù)也不是5。25三1 (mod8), 25除以7的余數(shù)也不是5。33-1 (mod 8), 33除以7的余數(shù)正好是5,而且33除以6余數(shù) 正好是 3，所以這個數(shù)最小是 33。上面的方法實際是一種列舉法，也可以簡化為下面的格式：被8除余1的數(shù)有：9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89,其中被7除余 5的數(shù)有：33, 89,這些數(shù)中被6除余3的數(shù)最小是33。練習 5：除以 12余9。這個數(shù)最小是幾？1、某數(shù)除以 7余1，除以 5余1，2、某數(shù)除以 7余6，除以 5余