奧數(shù)-同余的概念及性質(zhì)+詳解過(guò)程講解學(xué)習(xí)

1、第五講 同余的概念和性質(zhì)你會(huì)解答下面的問(wèn)題嗎？問(wèn)題1今天是星期日，再過(guò)15天就是“六一”兒童節(jié)了，問(wèn)“六一”兒童節(jié)是 星期幾？這個(gè)問(wèn)題并不難答因?yàn)椋粋€(gè)星期有7天，而15- 7=21,即15= 7X 2+1,所以 “六一”兒童節(jié)是星期一。問(wèn)題 2： 1993 年的元旦是星期五， 1994 年的元旦是星期幾？這個(gè)問(wèn)題也難不倒我們.因?yàn)椋?993年有365天，而365=7X 52+1，所以1994年的元 旦應(yīng)該是星期六。問(wèn)題 1、2 的實(shí)質(zhì)是求用 7去除某一總的天數(shù)后所得的余數(shù) . 在日常生活中，時(shí)常要注 意兩個(gè)整數(shù)用某一固定的自然數(shù)去除， 所得的余數(shù)問(wèn)題 .這樣就產(chǎn)生了“同余”的概念. 如問(wèn)題

2、1、2中的 15與 365除以 7后，余數(shù)都是 1，那么我們就說(shuō) 15與 365對(duì)于模 7 同余。同余定義：若兩個(gè)整數(shù)a、b被自然數(shù)m除有相同的余數(shù)，那么稱a、b對(duì)于模m同余， 用式子表示為：a= b (modr) .(*)上式可讀作：a同余于b，模m同余式(*)意味著(我們假設(shè)a> b)：a-b=mk，k 是整數(shù)，即 m|( a-b).例如： 15三365 ( mod7，因?yàn)?365-15=350=7 X 50。 56三20 (mod9，因?yàn)?56-20=36 = 9X4。 90三 0 (mod10，因?yàn)?90-0 = 90=10X 9。由例我們得到啟發(fā)，a可被m整除，可用同余式表示為

3、：a= 0 (modm。例如，表示a是一個(gè)偶數(shù)，可以寫a= 0 (mod 2)表示 b 是一個(gè)奇數(shù)，可以寫b 三 1 (mod 2)補(bǔ)充定義：若m(a-b)，就說(shuō)a、b對(duì)模m不同余，用式子表示是：a b ( modm)我們書寫同余式的方式， 使我們想起等式， 而事實(shí)上， 同余式與等式在其性質(zhì)上相似 同余式有如下一些性質(zhì)(其中 a、b、c、d是整數(shù)，而m是自然數(shù))。性質(zhì)1: a=a (mod m，(反身性)這個(gè)性質(zhì)很顯然.因?yàn)閍-a=0=m - 0。性質(zhì)2：若a= b ( mod m，那么b= a (mod m ,(對(duì)稱性)。'性質(zhì) 3: 若 a= b ( mod m , b= c (m

4、od m)，那么 a= c (mod m),(傳遞性)。性質(zhì) 4：若 a= b ( mod m , c= d (mod m，那么 a±c=b±d (mod m ,(可加減性 。性質(zhì) 5：若 a= b ( mod m , c= d (mod m)，那么 ac= bd (mod m (可乘性)。性質(zhì)6:若a= b ( mod m，那么an= bn (mod m),(其中n為自然數(shù))。'性質(zhì) 7： 若 ac= bc (mod m , ( c, m) =1, 那么 a= b (mod m，(記號(hào)(c, m)表示c與m的最大公約數(shù))。注意同余式性質(zhì)7的條件(c, n)二1,否

5、則像普通等式一樣，兩邊約去，就是錯(cuò)的。例如 6= 10 (mod 4)，而 35 (mod 4)，因?yàn)?2, 4)工 1。請(qǐng)你自己舉些例子驗(yàn)證上面的性質(zhì)。同余是研究自然數(shù)的性質(zhì)的基本概念,是可除性的符號(hào)語(yǔ)言。例 1 判定 288 和 214 對(duì)于模 37 是否同余, 74 與 20 呢？解：288-214=74=37X 2。 288三214 (mod37) 74-20=54，而 3754, 7420 (mod37。例2求乘積418X 814X 1616除以13所得的余數(shù)。分析 若先求乘積，再求余數(shù)，計(jì)算量太大 . 利用同余的性質(zhì)可以使“大數(shù)化小”，減 少計(jì)算量。解：418三 2 (mod13

6、,814三 8 (mod13 , 1616三 4 ( mod13 , 根據(jù)同余的性質(zhì) 5可得：418X 814X 1616三2X 8X 4三64三 12 (mod13。答：乘積 418X 814X 1616除以 13余數(shù)是 12。例 3 求 14389除以 7 的余數(shù)。分析 同余的性質(zhì)能使 “大數(shù)化小” ,凡求大數(shù)的余數(shù)問(wèn)題首先考慮用同余的性質(zhì)化大 為小. 這道題先把底數(shù)在同余意義下變小,然后從低次冪入手, 重復(fù)平方, 找找有什么規(guī)律。解法 1：t 143三 3 (mod789 89 143 = 3 (mod 7 )/ 89= 64+16+8+1而 32= 2 (mod 7),43 = 4 (

7、mod7 ,38三 16三 2 ( mod 7),36=4 (mod 7),332三 16三 2 (mod 7),364=4 (mod 7)。.389三364 316 38 3三4X 4X 2X 3三5 (mod 7),14389= 5 (mod 7)。答：14389除以7的余數(shù)是5。解法 2:證得 14389= 389 (mod 7)后，6243 三3 X 3 三2X 4三 1 (mod 7),.384=( 36) 14= 1 (mod 7)。.389三384 34 3三 1 X4X 3三5 (mod 7)。89.143 = 5 (mod 7)。例4四盞燈如圖所示組成舞臺(tái)彩燈，且每 30秒鐘

8、燈的顏色改變一次，第一次上下兩 燈互換顏色，第二次左右兩燈互換顏色，第三次又上下兩燈互換顏色，這樣一直 進(jìn)行下去請(qǐng)問(wèn)開(kāi)燈1小時(shí)四盞燈的顏色如何排列？1=30秒?yún)T囿30秒華一次甫二歡分析 與解答經(jīng)觀察試驗(yàn)我們可以發(fā)現(xiàn)，每經(jīng)過(guò)4次互換，四盞燈的顏色排列重復(fù)一次， 而1小時(shí)=60分鐘=120X 30秒，所以這道題實(shí)質(zhì)是求120除以4的余數(shù)，因?yàn)?20三0(mod 4),所以開(kāi)燈1小時(shí)四盞燈的顏色排列剛好同一開(kāi)始一樣。例5設(shè)自然數(shù)N =尙細(xì)廠町師其中彌、葉蚣細(xì)分別是個(gè)位 十位，上的數(shù)碼，再設(shè) M=a肝a1 + an，求證：NM(mod 9)。分析 首先把整數(shù)N改寫成關(guān)于10的幕的形式，然后利用10=

9、1 (mod 9) <證明；T W=気亦/=X 100 0+! x 100-0+- + a/X10+ac二備X lOjVi *嘰t十坷X 10+又 1 = 1 (mod 9)，10= 1 (mod 9)，210 = 1 ( mod 9)，10n= 1 ( mod 9),上面這些同余式兩邊分別同乘以 a。、ai、a2、an,再相加得：2ao+ ai x 10+比 x 1。+anX 10n=ao+ ai+ a2 + + an (mod 9),即 N = M (mod 9).這道例題證明了十進(jìn)制數(shù)的一個(gè)特有的性質(zhì)：任何一個(gè)整數(shù)模 9 同余于它的各數(shù)位上數(shù)字之和。以后我們求一個(gè)整數(shù)被 9除的余數(shù)

10、,只要先計(jì)算這個(gè)整數(shù)各數(shù)位上數(shù)字之和,再求這 個(gè)和被 9 除的余數(shù)即可。例如,求 1 827496被9除的余數(shù),只要先求( 1+8+2+7+4+9+6),再求和被 9除 的余數(shù)。再觀察一下上面求和式 .我們可以發(fā)現(xiàn),和不一定要求出 . 因?yàn)楹褪街?1+8, 2+7, 9 被9除都余 0,求余數(shù)時(shí)可不予考慮 .這樣只需求 4+6被9除的余數(shù).因此, 1827496 被9除余數(shù)是 1。有人時(shí)常利用十進(jìn)制數(shù)的這個(gè)特性檢驗(yàn)幾個(gè)數(shù)相加、相減、相乘的結(jié)果對(duì)不對(duì),這種 檢查方法叫：棄九法。棄九法最經(jīng)常地是用于乘法 . 我們來(lái)看一個(gè)例子。用棄九法檢驗(yàn)乘式5483x 9117三49888511是否正確？因?yàn)?5

11、483 三5+ 4+ 8+ 3三 11 三2 (mod 9),9117三 9+ 1 + 1 + 7三 0 (mod 9),所以 5483 x 9117三2X 0三0 ( mod 9)。但是 49888511 三 4+9+ 8+8+8+ 5+1+1=8 (mod9 ,所以5483 x 9117工49888511，即乘積不正確。要注意的是棄九法只能知道原題錯(cuò)誤或有可能正確,但不能保證一定正確。例如，9875= 9+ 8+7+5= 2 (mod 9), 4873= 4+ 8+ 7+ 3= 4 (mod 9),32475689三 3+2+4+7+ 5+6+8+9=8 (mod 9),這時(shí)，9875X4

12、873三2X4三32475689 (mod 9)。但觀察個(gè)位數(shù)字立刻可以判定 9875X 4873工32475689.因?yàn)槟┪粩?shù)字5和3相乘不可 能等于 9。棄九法也可以用來(lái)檢驗(yàn)除法和乘方的結(jié)果。例 6 用棄九法檢驗(yàn)下面的計(jì)算是否正確：23372458- 7312= 3544。解：把除式轉(zhuǎn)化為：3544X 7312= 23372458。3544 = 3+ 5 + 4+ 4= 7 (mod 9),7312三 7+ 3+ 1+ 2= 4 (mod 9), 3544 X 7312= 7X 4= 1 (mod 9),但 23372458=2+3+3+8=7(mod 9)。而 17( mod 9) 3544 X 7312工 23372458,即 23372458 - 7312工3544。例 7 求自然數(shù) 2100+ 3101 + 4102 的個(gè)位數(shù)字。分析 求自然數(shù)的個(gè)位