五年級奧數(shù)培訓(xùn)資料同余法解題

1、五年級奧數(shù)培訓(xùn)資料第六講 同余法解題 一、 同余這個(gè)概念最初是由德國數(shù)學(xué)家高斯發(fā)明的。同余的定義是這樣的： 兩個(gè)整數(shù)，a,b,如果他們同時(shí)除以一個(gè)自然數(shù)m，所得的余數(shù)相同，則稱a,b對于模m同余。記作ab（mod.m）。讀作：a同余于b模m。 同余的性質(zhì)也比較多，主要有以下一些：1.對于同一個(gè)除數(shù)，兩個(gè)數(shù)的乘積與它們余數(shù)的乘積同余。例如20195的乘積對于除數(shù)7，與2017的余數(shù)5和957的余數(shù)4的乘積20對于7同余。2.對于同一個(gè)除數(shù)，如果有兩個(gè)整數(shù)同余，那么它們的差就一定能被這個(gè)除數(shù)整除。例如519和399對于一個(gè)除數(shù)同余，那么這個(gè)除數(shù)一定是519與399的差的因數(shù)，即519與399的差一

2、 定能被這個(gè)除數(shù)整除。3.對于同一個(gè)除數(shù)，如果兩個(gè)數(shù)同余，那么他們的乘方仍然同余。 例如20和29對于一個(gè)除數(shù)同余，那么20的任何次方都和29的相同次方對于這個(gè)除數(shù)同余，當(dāng)然余數(shù)大小隨次方變化。4對于同一個(gè)除數(shù)，若三個(gè)數(shù)ab（mod m），bc（mod m），那么a,b,c三個(gè)數(shù)對于除數(shù)m都同余 （傳遞性）例如60和76同余于模8，76和204同余于模8，那么60,76,204都同余于模8。5. 對于同一個(gè)除數(shù)， 若四個(gè)數(shù)ab（mod m），cd（mod m），那么accd（mod m），（可加減性）6. 對于同一個(gè)除數(shù)， 若四個(gè)數(shù)ab（mod m），cd（mod m），那么accd（mod

3、m），（可乘性）二、中國剩余定理解法一個(gè)數(shù)被3除余1，被4除余2，被5除余4，這個(gè)數(shù)最小是幾？解法：求3個(gè)數(shù)：第一個(gè)：能同時(shí)被3和4整除，但除以5余4，即12X224第二個(gè)：能同時(shí)被4和5整除，但除以3余1，即20X240第三個(gè)：能同時(shí)被3和5整除，但除以4余2，即15x230這3個(gè)數(shù)的最小公倍數(shù)為60，所以滿足條件的最小數(shù)字為2440+30-60=3412X224 20X240 15x230中2的來歷。三、解題技巧同余口訣：“差同減差，和同加和，余同取余，最小公倍n倍加”這是同余問題的口訣。1）、差同減差：用一個(gè)數(shù)除以幾個(gè)不同的數(shù)，得到的余數(shù)，與除數(shù)的差相同，此時(shí)反求的這個(gè)數(shù)，可以選除數(shù)的最

4、小公倍數(shù)，減去這個(gè)相同的差數(shù)，稱為：“差同減差”。例：“一個(gè)數(shù)除以4余1，除以5余2，除以6余3”，因?yàn)?-1=5-2=6-3=3，所以取-3，表示為60-3或者60n-32）、和同加和：用一個(gè)數(shù)除以幾個(gè)不同的數(shù)，得到的余數(shù)，與除數(shù)的和相同，此時(shí)反求的這個(gè)數(shù)，可以選除數(shù)的最小公倍數(shù)，加上這個(gè)相同的和數(shù)，稱為：“和同加和”。例：“一個(gè)數(shù)除以4余3，除以5余2，除以6余1”，因?yàn)?+3=5+2=6+1=7，所以取+7，表示為60n+7。3）、余同取余：用一個(gè)數(shù)除以幾個(gè)不同的數(shù)，得到的余數(shù)相同，此時(shí)反求的這個(gè)數(shù)，可以選除數(shù)的最小公倍數(shù)，加上這個(gè)相同的余數(shù)，稱為：“余同取余”。例：“一個(gè)數(shù)除以4余1，

5、除以5余1，除以6余1”，因?yàn)橛鄶?shù)都是1，所以取+1，表示為60n+1。4）、最小公倍加：所選取的數(shù)加上除數(shù)的最小公倍數(shù)的任意整數(shù)倍（即上面1、2、3中的60n）都滿足條件，稱為：“最小公倍n倍加”，也稱為：“公倍數(shù)作周期”。 三、例題解評例1：判定288和214對于模37是否同余思路點(diǎn)撥：可直接由定義判斷。解：288-214=74=372288214（mod 37）例2、 用412、133和257除以一個(gè)相同的自然數(shù)，所得的余數(shù)相同，這個(gè)自然數(shù)最大是幾？【解析】假設(shè)這個(gè)自然數(shù)是a，因?yàn)?12、133和257除以a所得的余數(shù)相同，所以a(412133),a(412257),a(257133),

6、說明a是以上三個(gè)數(shù)中任意兩數(shù)差的約數(shù)，要求最大是幾，就是求這三個(gè)差的最大公約數(shù)。(155,124,279)=31,所以a最大是31。 例3、 249388234除以19，余數(shù)是幾？【解析】如果把三個(gè)數(shù)相乘的積求出來再除以19，就太麻煩了，利用同余思想解決就容易了。因?yàn)?492（mdo19）, 3888（mdo19）,2346（mdo19）,所以2493882342861（mdo19）此題應(yīng)用了同余的可乘性，同余的傳遞性。例4：求199259除以7的余數(shù)。思路點(diǎn)撥：可應(yīng)用性質(zhì)2，將199259轉(zhuǎn)化為求1992除以7和59除以7的余數(shù)的乘積，使計(jì)算簡化。解：19924（mod 7），593（mod

7、 7）根據(jù)性質(zhì)5可得：19925943（mod 7），余數(shù)為127的余數(shù)。答：199259除以7的余數(shù)是5。例5：自然數(shù)16520、14903、14177除以m的余數(shù)相同，m的最大值是多少？思路點(diǎn)撥：自然數(shù)16520、14903、14177除以m的余數(shù)相同，也就是165201490314177（mod m）根據(jù)同余補(bǔ)充定義，這三個(gè)數(shù)同余，那么它們的差就能被m整除。要求m最大是多少，就是求它們差的最大公約數(shù)是多少。解：因?yàn)?6520-14903=161716520-14177=234314903-14177=726（1617、2343、726）=33所以m的最大值是33。評注實(shí)際上，這三個(gè)差數(shù)還

8、可以繼續(xù)兩兩相減，得到1617-726=891,891-726=165，算出726和165的最大公約數(shù)即可，通常其結(jié)果與上面相同。例6：在除13511，13903，及14598時(shí)能剩下相同余數(shù)的最大整數(shù)是幾？思路點(diǎn)撥：根據(jù)同余的性質(zhì)，若幾個(gè)數(shù)被同一個(gè)數(shù)除，余數(shù)相同，則這幾個(gè)數(shù)中兩兩相減的差必能被這個(gè)數(shù)整除。所以這個(gè)數(shù)應(yīng)是這三個(gè)數(shù)兩兩相減后所得數(shù)的最大公約數(shù)。解：這兩個(gè)數(shù)兩兩只減的差是 ：13903-13511=39214598-13903=68614589-13511=1078因?yàn)椋?92，686，1078）=98，所以這個(gè)數(shù)是98。也可以以上三個(gè)差再兩兩相減，得686-392=294，再39

9、2-294=98答：這個(gè)最大整數(shù)是98。例7：一個(gè)三位數(shù)除以9余7，除以5余2，除以4余3。這樣的三位數(shù)共有幾個(gè)？思路點(diǎn)撥：由中國剩余定理解法求。解法：求3個(gè)數(shù)：第一個(gè)：能同時(shí)被9和5整除，但除以4余3，即45X3135第二個(gè)：能同時(shí)被4和5整除，但除以9余7，即20X8160第三個(gè)：能同時(shí)被9和4整除，但除以5余2，即36x272這3個(gè)數(shù)的最小公倍數(shù)為180，所以滿足條件的最小數(shù)字為135160+72-180=18771805=907 100071806=10871000所以符合條件的三位數(shù)共有5個(gè)。分別是7180n（n=1,2,4,5）.答：這樣的三位數(shù)共有5個(gè)。例8、 有一個(gè)1997位數(shù)

10、，它的每個(gè)數(shù)位都是2，這個(gè)數(shù)除以13，商的第100位是幾？最后余數(shù)是幾？【解析】這個(gè)數(shù)除以13，商是有規(guī)律的。 商是170940六個(gè)數(shù)循環(huán)，那么，即，我們從左向右數(shù)“170940”的第4個(gè)數(shù)就是我們找的那個(gè)數(shù)“9”，所以商的第100位是9。 余數(shù)是幾呢？ 則解析過程：本題商共有1996位，每6位循環(huán)，共有332次循環(huán)后余4， 所以商的個(gè)位數(shù)字應(yīng)是“170940”中的第4個(gè)，商應(yīng)是9，個(gè)位的余數(shù)就對應(yīng)商為9時(shí)的余數(shù)5。三、練習(xí)題1. 求下列算式中的余數(shù)。 （1） （2）（3）（4）2. 6254與37的積除以7，余數(shù)是幾？3. 如果某數(shù)除482，992，1094都余74，這個(gè)數(shù)是幾？4、300、262、205被同一個(gè)整數(shù)除，得到相同的余數(shù)，這個(gè)整數(shù)是幾？5、一個(gè)自然數(shù)被247除余 63，被248除余63，求這個(gè)自然數(shù)被26除的余數(shù)。6、一個(gè)自然數(shù)N被10除余9，被9除余8，被8除余7，被7除余6，被6除余5，被5除余4，被4除余