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

1、第三十八周 應(yīng)用同余問題專題簡(jiǎn)析：同余這個(gè)概念最初是由偉大的 德國(guó)數(shù)學(xué)家 高斯 發(fā)現(xiàn)的。同余的定義是這樣的：兩個(gè)整數(shù) a， b，如果它們除以同一自然數(shù) m 所得的余數(shù)想同，則稱 a， b 對(duì)于模 m 同余。記作： ab （ mod ）。讀做：同余于模。比如， 12 除以 5，47 除以 5 ，它們有相同的余數(shù) 2，這時(shí)我們就說， 對(duì)于除數(shù) 5，12 和 47 同余，記做 12 47 （ mod 5）。同余的性質(zhì)比較多，主要有以下一些：性質(zhì)（ 1）：對(duì)于同一個(gè)出書，兩個(gè)數(shù)之和（或差）與它們的余數(shù)之和（或差）同余。比如：32 除以 5余數(shù)是 2，19 除以 5 余數(shù)是 4，兩個(gè)余數(shù)的和是 2+4=

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

3、為求一個(gè)較小的數(shù)除以這個(gè)數(shù)的余數(shù)，使復(fù)雜的題變簡(jiǎn)單，使困難的題變?nèi)菀?。例題 1： 求 1992×59 除以 7 的余數(shù)。分析：應(yīng)用同余性質(zhì) （ 2）可將 1992 ×59 轉(zhuǎn)化為求 1992 除以 7 和 59 除以 7 的余數(shù)的乘積， 使計(jì)算簡(jiǎn)化。 1992 除以 7 余 4，59 除以 7 余 3。根據(jù)同余性質(zhì)， “4×3”除以7 的余數(shù)與“1992 ×59 ”除以7 的余數(shù)應(yīng)該是相同 的，通過求“4 ×3 ”除以7 的余數(shù)就可知道 1992 ×59 除以 7 的余數(shù)了。因?yàn)?1992 ×59 4 ×3 5（

4、mod 7 ）所以 1992 ×59 除以 7 的余數(shù)是 5。練習(xí)一1、求 4217×364 除以 6 的余數(shù)。2、求 1339655× 12除以 13 的余數(shù)。3、求 879× 4376× 5283除以 11 的余數(shù)。例題 2：已知 2001 年的國(guó)慶節(jié)是星期一，求 2010年的國(guó)慶節(jié)是星期幾？分析： 一星期有 7 天，要求 2010 年的國(guó)慶節(jié)是星期幾，就要求從 2001 年到 2010 年的國(guó)慶節(jié)的總天數(shù)被 7 除的余數(shù)就行了。但在甲酸中，如果我們能充分利用同余性質(zhì)，就可以不必算出這個(gè)總天數(shù)。2001 年國(guó)慶節(jié)到 2010 年國(guó)慶節(jié)之間共

5、有 2 個(gè)閏年 7 個(gè)平年，即有“ 366 ×2+365 ×7”天。因?yàn)?66 ×22× 24（mod 7 ）， 365 ×71 ×7 0（ mod 7 ）， 366 ×2+365 ×72 ×2+1 ×7 4+0 4 （ mod 7）答： 2010 年的國(guó)慶節(jié)是星期五。練習(xí)二1、已知 2002 年元旦是星期二。求 2008 年元旦是星期幾？2、已知 2002年的“七月一日”是星期一。求2015 年的“十月一日”是星期幾？3、今天是星期四，再過 365的 15次方是星期幾？例題 3：求 2001

6、的 2003 次方除以 13 的余數(shù)。分析： 2001 除以 13 余 12，即 2001 12 （ mod 13 ）。根據(jù)同余性質(zhì)（ 4），可知 2001 的 2003 次方12 的 2003 次方（ mod 13 ），但 12 的 2003 次方仍然是一個(gè)很大的值，要求它的余數(shù)比較困難。這時(shí)的關(guān)鍵就 是要找出 12 的幾次方對(duì)模 13 與 1是同余的。經(jīng)試驗(yàn)可知 12 的平方1（ mod 13），而 2003 2×1001+1 。所 以（12的平方）的 1001次方1的1001（mod 13 ），即12的2002 次方1（mod 13 ），而12的2003 次方 12 的 200

7、2 次方×12 。根據(jù)同余性質(zhì)（ 2）可知 12 的 2002 次方×121×12 12 （ mod 13 ）因?yàn)椋?2001 的 2003 次方12 的 2003 次方（ mod 13 ）12 的平方1 （mod 13 ），而 2003 2×1001+112 的 2003 次方12 的 2002 次方×12 1 ×12 12 （mod 13 ）所以 2001 的 2003 次方除以 13 的余數(shù)是 12 。練習(xí)三1、求 12 的 200 次方除以 13 的余數(shù)。2、求 3 的 92 次方除以 21 余幾。3、9個(gè)小朋友坐成一圈，要把

8、 35的 7次方粒瓜子平均分給他們，最后剩下幾粒？例題 4： 自然數(shù) 16520， 14903， 14177 除以 m的余數(shù)相同， m最大是多少？分析：自然數(shù) 16520 ，14903 ，14177 除以 m 的余數(shù)相同，換句話說就是 16520 14903 14177（ mod m ）。 根據(jù)同余性質(zhì)（ 3 ），這三個(gè)餓數(shù)同余，那么它們的差就能被m 整除。要求 m 最大是多少，就是求它們差的最大公約數(shù)是多少？因?yàn)?16520 14903=1617=3 ×7 的平方×1116520 14177=2343=3 ×11×7114903 14177=726=2

9、 ×3×11 的平方M 是這些差的公約數(shù)， m 最大是 3 ×11=33 。練習(xí)四1、若 2836、4582、5164、6522 四個(gè)整數(shù)都被同一個(gè)兩位數(shù)相除，所得的余數(shù)相同。除數(shù)是多少？2、一個(gè)整數(shù)除 226、192、141 都得到相同的余數(shù)，且余數(shù)不為0，這個(gè)整數(shù)是幾？3、當(dāng) 1991 和 1769 除以某一個(gè)自然數(shù) m 時(shí)，余數(shù)分別為 2 和 1，那么 m 最小是多少？例題 5：某數(shù)用 6除余 3，用7除余5，用 8除余1，這個(gè)數(shù)最小是幾？分析：我們可從較大的除數(shù)開始嘗試。首先考慮與 1模8同余的數(shù)， 91（mod 8），但 9輸以 7余數(shù)不是5，所以某數(shù)不是 9。171（mod 8 ），17除以 7的余數(shù)也不是 5 。25 1（mod 8 ），25除以 7的余數(shù)也不 是5。331（mod 8），33 除以 7的余數(shù)正好是 5，而且 33 除以 6余數(shù)正好是 3，所以這個(gè)數(shù)最小是 33。上面的方法實(shí)際是一種列舉法，也可以簡(jiǎn)化為下面的格式：被8除余 1的數(shù)有： 9，17，25，33，41，49，57，65，73，81，89，其中被 7除余 5的數(shù)有：33 ， 89，這些數(shù)中被 6除余 3的數(shù)最小是 33。練習(xí)五1、某數(shù)除以 7余 1，除以 5余 1，除以 12余 9。這個(gè)數(shù)最小是幾？2、某數(shù)除以