數(shù)論之同余與余數(shù)問題

1、主動學習網(wǎng)理念：激發(fā)興趣，挖掘潛力，培優(yōu)教育網(wǎng)址：電話62923545第14講 數(shù)論之同余與余數(shù)問題1、 被除數(shù)除數(shù)=商余數(shù)，被除數(shù)=除數(shù)商+余數(shù)2、 和差積的余數(shù)同余余數(shù)的和差積。3、 同余：ax余r, bx余r，則(a-b)是x的倍數(shù)，這種技巧常用于求除數(shù)的題目。4、 求被除數(shù)三大類問題:余同(最小公倍數(shù)的倍數(shù)加余數(shù))，差同（最小公倍數(shù)的倍數(shù)減差），都不同（剩余定理）。5、 整除與余數(shù)：除以3或9的余數(shù)看數(shù)字之和，7、11、13是三位一格，奇位和減偶位和（減不夠加7、11、13的若干倍），11也可以一位一格，奇位和減偶位和（減不夠加11的若干倍）6、 個位數(shù)字：

2、自然數(shù)的m次方的個位數(shù)字都可以看成4次方1個周期。7、 有規(guī)律的余數(shù)問題，常利用“和差積的余數(shù)同余余數(shù)的和差積”，結合周期簡化題目。【和差積的余數(shù)同余余數(shù)的和差積】【1】【解析】（9+7+2）(9-7)(7-2)=1825=180，180除以11余4.【2】【解】、除以3，余數(shù)是0，所以只須看表達式除以3余幾注意：如果a除以3余, b 除以3余. ，那 ab 除以3所得的余數(shù)就是內除以3所得的余數(shù)因為4、7除以3余1，所以、，除以3，余數(shù)也是1 . 因為5、8除以3余2，所以、除以3，余數(shù)與, 除以3的余數(shù)相同而=16 除以3余1，所以=2除以3 余2 , =除以3余l(xiāng)（=11） 于是除以3，

3、所得余數(shù)與l4l211除以3，所得余數(shù)相同，即余數(shù)是1 . 【3】【解】 有已知，乙，丙，丁三人取走的七盒中，糖的塊數(shù)是丁所取糖塊數(shù)的5倍.八盒糖的總塊數(shù)是917242830313344=216 216除以5的余數(shù)為1，所以甲取走的一盒除以5余1.因此甲取走的一盒中有31塊奶糖.【4】【解法1】 甲余11人，乙余3611=25人.甲團人數(shù)與乙團人數(shù)的積除以36，余數(shù)與1125除以36的余數(shù)相同，即余23.所以最后一卷拍了23張，還可拍3623=13張.【解法2】因為除去最后一輛車，其它個車里兩團代表人數(shù)都是36的倍數(shù)，所以剩下膠片是最后一輛車里兩團代表拍完照留下的. 251136=723 還可

4、拍3623=13(張).【5】【分析】任何數(shù)乘方的尾數(shù)都是4 個數(shù)一周期7是7、9、3、1循環(huán)，因為20104 502 2，所以 尾數(shù)是9. 8 是8、4、2、6循環(huán)，因為98 4余2，所以尾數(shù)是4 . 9 是9、1、9、9循環(huán)，因為20094余1 ，所以尾的數(shù)是9 . 9+94=45，個位為5.【6】【分析】 求結果除以l0的余數(shù)即求從l 到2005 這2005 個數(shù)的個位數(shù)字是10 個一循環(huán)的，而對于一個數(shù)的冪方的個位數(shù)，我們知道它總是4 個一循環(huán)的，因此把每個加數(shù)的個位數(shù)按20 個一組，則不同組中對應的數(shù)字應該是一樣的 首先計算的個位數(shù)字為m . 2005 個加數(shù)中有100 組多5 個數(shù)

5、，100 組的個位數(shù)是m100的個位數(shù)即o , 另外5 個數(shù)為，它們和的個位數(shù)字是1476523 的個位數(shù)3.【7】【分析】 同余的性質的應用【解】 1433 ( mod7 ) ( mod 7) 1(mod 7) 5 (mod 7) . 【評析】 這類題都是通過找?guī)状畏匠?得余數(shù)1作為突破，大大簡化題目的難度?！眷柟獭俊窘馕觥?0118余3，與除以8的余數(shù)相同，33除以8余1，所以【同余-用于求除數(shù)】同余：ax余r, bx余r，則(a-b)是x的倍數(shù)?！净A知識練習】 【分析】 所求自然數(shù)減去 63 的差可被 247 與 248 整除，再考慮這個差被 26 除的余數(shù)【解】 設所求自然數(shù)減去6

6、3，差是 a ，則 a 被 247 與 248 整除，247 = 1913 , 248=2 124 所以 a 被13與2整除，13與2 互質，得 a 被 26 整除原來的自然數(shù)是 a + 63 ，所以只要考慮 63 被 26 除后的余數(shù) 63 = 262+ 11 因此這個自然數(shù)被 26 除余11 答：所求余數(shù)是11. 【評析】 如果一個整數(shù)能被甲、乙兩數(shù)整除，并不能得出它被甲、乙兩數(shù)的積整除在甲、乙兩數(shù)互質時，才能導出這個數(shù)被甲、乙兩數(shù)的積整除 【1】【解析】由85-69=16，93-85=8，推出a=8或4或2，978=121.所以丁團分成每組a人的若干組后還剩1人?！?】【解析】 這個數(shù)a

7、除55l,745個數(shù)去除551,745,1,1133,1327,所得的余數(shù)相同,所以有551,745,1133,1327兩兩做差而得到的數(shù)一定是除數(shù)a的倍數(shù) 1327-1133=194,1133-745=388,745-551=194,1327-745=582,1327-551=776,1133-551=582 這些數(shù)都是a的倍數(shù),所以a是它們的公約數(shù),而它們的最大公約數(shù)(194，388，194，582，776，582)=194 所以,這個數(shù)最大可能為194【3】【分析與解】 設這個除數(shù)為m,設它除63,90,130所得的余數(shù)依次為a,b,c,商依次為a,b,c 63m=aa 90m=bb 1

8、30m=cc a+b+c=25,則(63+90+130)-(a+b+c)=(a+b+c)m,即283-25=258=(a+b+c)m所以m是258的約數(shù).258=2343,顯然當除數(shù)m為2、3、6時,3個余數(shù)的和最大為3(2-1)=3，3(3-1)=6,3(6-1)=15,所以均不滿足 而當除數(shù)m為432,433,4323時,它除63的余數(shù)均是63,所以也不滿足 那么除數(shù)m只能是43,它除63,90,130的余數(shù)依次為20,4,1,余數(shù)的和為25,滿足顯然這3個余數(shù)中最大的為20【余數(shù)三大類問題-用于求被除數(shù)】(1)余同：最小公倍數(shù)的倍數(shù)+余數(shù)，（2）差同(差=除數(shù)-余數(shù))：最小公倍數(shù)的倍數(shù)-

9、差 (3)都不同：結合中國剩余定理與不定方程兩邊對某數(shù)求余數(shù)的方法。【1】【分析】 n 加上 1 ，就可以被 10 、 9 、 8 、 、 2 整除【解】 由于n十l被10、9、8、2整除，而10、 9 、 8 、 、 2 的最小公倍數(shù)是 5987=2520 因此， n 十 1 被 2520 整除 n 的最小值是 2520 一 1 = 2519 答： n 的最小值是 2519 . 【2】【解】設這個數(shù)為23a7，因為它除以19余9，所以，23a7一9 =19a4a一2被19整除，即4a一2被19整除令a = l , 2 ，代入檢驗，在 a = 10 時，4a2 = 38 第一次被19整除，所以

10、所求的自然教最小是23107 = 237 【3】【分析與解】設這個圓圈有n個孔,那么有n除以3余1,n除以5余1.n能被7整除則將n-1是3、5的倍數(shù),即是15的倍數(shù),所以n=15t+1,又因為凡是7的倍數(shù),即15t+1=7a,將系數(shù)與常數(shù)對7取模,有t+10(mod7),所以t取6或6與7的倍數(shù)和. 對應孔數(shù)為156+l=91或91與105的倍數(shù)和，滿足題意的孔數(shù)只有91即這個圓圈上共有91個孔【活學活用】【1】 【解析一：教材方法】甲、乙兩數(shù)的差被 3 整除，即甲、乙兩數(shù)被 3 除的余數(shù)相同 一個自然數(shù)被 3 除，余數(shù)只有 3 種情況，即0、1、2. 由分析可知：甲、乙兩數(shù)被 3 除，余數(shù)

11、相同，下面分三種情況討論（1） 如果甲、乙兩數(shù)被 3 除都余 1 ，那么，它們的和被 3 整除，不符合題意（2） 如果甲、乙兩數(shù)被 3 除都余 1 ，那么，它們的和被 3 除余 2 , 也不符合題意（3） 如果甲、乙兩數(shù)被 3 除都余 2 ，那么，它們的和被 3 除正好余 l . 答：甲數(shù)被 3 除的余數(shù)是 2 . 【解析二：致遠推薦】a+b=3m+1，a-b=3n，解得2a=3m+3n+1，所以a=3(m+n)+12，無論m+n為奇數(shù)還是偶數(shù)，a除以3余2.【2】【解析】 設a、b、c為連續(xù)三項，則c= 3b一a考慮原數(shù)列各項除以3所得的余數(shù)，組成數(shù)列 0 , l , 0 , 2 , 0 ,

12、 l , 0 , 2， 每4項重復出現(xiàn)考慮原數(shù)列各項除以2所得的余數(shù)，組成數(shù)列0，1，1，0，1，1，0，1，1，每3項重復出現(xiàn).因此，原數(shù)列最右邊的（第70個）數(shù)，除以3余1（70 = 4172），除以2 所余0（70=3231）于是最右一個數(shù)被6除余4.【3】【分析】 算出 7 所得的余數(shù)，便可推得結論若把 2004連乘，用所得的結果除以 7 ，計算太復雜了！因此先找出與 2004 除以 7同余的最小數(shù)，然后根據(jù)余數(shù)的有關性質解題【解】 因為 2004 除以 7 的余數(shù)是 2 . 所以 7 與7 的余數(shù)相同而= = = 所以7與7=17的余數(shù)相同.故 7 的余數(shù)為 1 . 因為今天是星期一

13、，所以再過天是星期二【評析】 若 a =pqr，則q與q 余數(shù)相同，在遇到一些非常大的數(shù)的若干次冪時，可使用冪的相關性質進行分解，使大數(shù)化成小數(shù)，如：=,=【天天練】【1】【解】 甲數(shù)是13的倍數(shù)加7，乙數(shù)是13的倍數(shù)加9，所以它們的積是13的倍數(shù)加79，而79除以13余11，所以甲、乙的積除以13余11 . 【2】【解】 甲、乙手中卡片上的數(shù)之和必是3的倍數(shù). 六張卡片上的數(shù)分別除以3，依次余2、1、0、0、1、l，推知只有后五個數(shù)之和能被3整除，所以丙手中卡片上的數(shù)是1193 . 【3】【解析】如下表所示：號碼101126173193盤數(shù)10121031262215173120319301

14、01101，126，173，193被3除的余數(shù)分別為2，0，2，1，故他們之間的比賽盤數(shù)如上表，由表可以看出，126號運動員打了5盤是最多的?！?】【解】 1477一49 = 1428 是這兩位數(shù)的倍數(shù)又1428=223717 =5128=6821 =8417 因此，所求的兩位數(shù)51或68或84【5】【解】由199246=43 14得1992=464314，所以a= 43,r =14.【6】【分析】 這個整數(shù)除300、262得到相同的余數(shù)所以300一262的差，一定被這個整數(shù)整除也就是說，這個整數(shù)是300一262的因數(shù)同樣，這個整數(shù)也是300一205的因數(shù)【解】 300一 262 = 38 =

15、219 300 一 205 = 95 = 519所以這個整數(shù)是 19 . 答：這個整數(shù)是 19 .【評析】 同余問題轉化為整除問題，是解決這類問題的常用方法 【7】【解】 200一5 = 195 . 300一l = 299 , 400一10 = 390 195 , 299 , 390 的最大公約數(shù)是13于是，這個數(shù)是13 . 【8】【解】2008 被這樣的自然數(shù)除余數(shù)是10 ，那么，1998 就是這些自然數(shù)的倍數(shù)，換句話說，我們要求1998 的約數(shù)有幾個，但注意到除數(shù)比余數(shù)大，所以我們要求的是1998 的約數(shù)中那些大于10 的，枚舉顯然不可取，我們考慮用約數(shù)個數(shù)公式： 1998237 , d

16、(1998) (ll)(3l) (1l) 16 其中小于10 的約數(shù)有l(wèi), 2, 3, 6, 9，去掉它們還有11 個，因此這樣的自然數(shù)共有11個【評析】 注意到除數(shù)比余數(shù)大【9】【分析】 同余的性質5的應用若ab ( mod m) , cd ( mod m)，那么acbd ( mod m) （可乘性）. 【解】 4182 (mod 13), 8148 (mod 13), 16164(mod 13), 根據(jù)同余的性質5 可得41881416162846412 (mod 13) . 所以，乘積418 火81 生只1616 除以13 余數(shù)是12 . 【評析】 若先求乘積，再求余數(shù)，計算量太大利用同

17、余的性質可以使“大數(shù)化小”，減少計算量【10】【分析】a 與b 的和除以c的余數(shù)，等于a , b 分別除以c的余數(shù)之和（或這個和除以c 的余數(shù)）當余數(shù)之和大于除數(shù)時，所求余數(shù)等于余數(shù)之和再除以c 的余數(shù)【解】 根據(jù)遞推關系把這串數(shù)除以9的余數(shù)列出來如下：l、3、8、4、6、2、7、o、5、l、3， 發(fā)現(xiàn)恰好每9個一循環(huán)，2000被9 除余數(shù)是2 ，所以第200個和第2 個一樣除以9 的余數(shù)是3 . 【11】【解】 去掉3人后，總數(shù)被3、5、7整除，因而是105的倍數(shù)，原人數(shù)在90110之間，因而是1053=108.【12】【解】 3,4,5,6=60,601=59(人) 答：上體育課的同學最少有59名.【13】【解析】 到會人數(shù)加上1，正好是9與7的公倍數(shù)，因而是63的倍數(shù). 這個數(shù)除以5余4，在63的小于200的倍數(shù)63 , 126 , 189中，只有189滿足這一條件. 因此到會的代表有l(wèi)88（= 189一l）人【14】【解析】如果 a = 35 ，則它被 14 除的余數(shù)是 7 . 如果 a 大于 35 ，則 a 一 35 能被 1981 和 1982 整除又 1981=7283能被 7 整除，且 1982 能被 2 整除，所以 a 一 35