關(guān)于小學奧數(shù)競賽專題之同余問題
[專題介紹]：同余問題
生活中我會經(jīng)常遇到與余數(shù)有關(guān)的問題，比如：某年級有將近400名學生。有一次演出節(jié)目排隊時出現(xiàn)：如果每8人站成一列則多余1人；如果改為每9人站成一列則仍多余1人；結(jié)果發(fā)現(xiàn)現(xiàn)成每10人結(jié)成一列，結(jié)果還是多余1人；聰名的你知道該年級共有學生多少名嗎？
假設(shè)有一名學生不參加演出，則結(jié)果一定是不管每列站8人或9人或10人都將剛好站齊。因此此時學生人數(shù)應(yīng)是8、9、10公倍數(shù)，而8、9、10的最小公倍數(shù)是360，因此可知該年級共有361人。
研究與余數(shù)有關(guān)的問題，能幫助我們解決很多較為復雜的問題。
[分析]
1、兩個整數(shù)a和b，除以一個大于1的自然數(shù)m所得余數(shù)相同，就稱a和b對于模m同余或稱a和b在模m下同余，即a≡b（modm）
2、同余的重要性質(zhì)及舉例。
〈1〉a≡a（modm）（a為任意自然）
〈2〉若a≡b（modm），則b≡a（modm）
〈3〉若a≡b（modm），b≡c（modm）則a≡c（modm）
〈4〉若a≡b（modm），則ac≡bc（modm）
〈5〉若a≡b（modm），c≡d（modm），則ac=bd（modm）
〈6〉若a≡b（modm）則an≡bm（modm）
其中性質(zhì)〈3〉常被稱為"同余的可傳遞性"，性質(zhì)〈4〉、〈5〉常被稱為"同余的可乘性，"性質(zhì)〈6〉常被稱為"同余的可開方性"
注意：一般地同余沒有"可除性"，但是：
如果：ac=bc（modm）且（c，m）=1則a≡b（modm）
3、整數(shù)分類：
〈1〉用2來將整數(shù)分類，分為兩類：
1，3，5，7，9，……（奇數(shù)）
0，2，4，6，8，……（偶數(shù)）
〈2〉用3來將整數(shù)分類，分為三類：
0，3，6，9，12，……（被3除余數(shù)是0）
1，4，7，10，13，……（被3除余數(shù)是1）
2，5，8，11，14，……（被3除余數(shù)是2）
〈3〉在模6的情況下，可將整數(shù)分成六類，分別是：
0（mod6）：0，6，12，18，24，……
1（mod6）：1，7，13，19，25，……
2（mod6）：2，8，14，20，26，……
3（mod6）：3，9，15，21，27，……
4（mod6）：4，10，16，22，29，……
5（mod6）：5，11，17，23，29，……
[經(jīng)典例題]
例1：求437×309×1993被7除的余數(shù)。
思路分析：如果將437×309×1993算出以后，再除以7，從而引得到，即437×309×1993=269120769，此數(shù)被7除的余數(shù)為1。但是能否尋找更為簡變的辦法呢？
473≡3（mod7）
309≡1（mod7）
由"同余的可乘性"知：
437×309≡3×1（mod7）≡3（mod7）
又因為1993≡5（mod7）
所以：437×309×1993≡3×5（mod7）
≡15（mod7）≡1（mod7）
即：437×309×1993被7除余1。
例2：70個數(shù)排成一行，除了兩頭的兩個數(shù)以外，每個數(shù)的三倍恰好等于它兩邊兩個數(shù)的和，這一行最左邊的幾個數(shù)是這樣的'：0，1，3，8，21，……，問這一行數(shù)最右邊的一個數(shù)被6除的余數(shù)是幾？
思路分析：如果將這70個數(shù)一一列出，得到第70個數(shù)后，再用它去除以6得余數(shù)，總是可以的，但計算量太大。
即然這70個數(shù)中：中間的一個數(shù)的3倍是它兩邊的數(shù)的和，那么它們被6除以后的余數(shù)是否有類似的規(guī)律呢？
0，1，3，8，21，55，144，……被6除的余數(shù)依次是
0，1，3，2，3，1，0，……
結(jié)果余數(shù)有類似的規(guī)律，繼續(xù)觀察，可以得到：
0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……
可以看出余數(shù)前12個數(shù)一段，將重復出現(xiàn)。
70÷2=5……10，第六段的第十個數(shù)為4，這便是原來數(shù)中第70個數(shù)被6除的余數(shù)。
思路分析：我們被直接用除法算式，結(jié)果如何。
例4、分別求滿足下列條件的最小自然數(shù)：
�。�1）用3除余1，用5除余1，用7除余1。
�。�2）用3除余2，用5除余1，用7除余1。
�。�3）用3除余1，用5除余2，用7除余2。
（4）用3除余2，用7除余4，用11除余1。
思路分析：
（1）該數(shù)減去1以后，是3，5和7的最小公倍數(shù)105，所以該數(shù)的是105+1=106
�。�2）該數(shù)減去1以后是5和7的公倍數(shù)。因此我們可以以5和7的公倍數(shù)中去尋找答案。下面列舉一些同時被5除余1，被7除余1的數(shù)，即
1，36，71，106，141，176，211，246，……從以上數(shù)中尋找最小的被3除余2的數(shù)。
36≡0（mod3），71≡2（mod3），符合條件的最小的數(shù)是71。
�。�3）我們首先列舉出被5除余2，被7除余2的數(shù)，2，37，72，107，142，177，212，247，……
從以上數(shù)中尋找最小的被3除余1的數(shù)。
2（mod3），37≡（mod3）、因此符合條件的最小的數(shù)是37。
（4）我們從被11除余1的數(shù)中尋找答案。
1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，……
1（mod3）；1（mod7），不符合
12≡0（mod3），12≡5（mod7）不符合
23≡2（mod3），23≡2（mod7）不符合
34≡1（mod3），34≡6（mod7）不符合
45≡0（mod3），45≡3（mod7）不符合
56≡2（mod3），56≡0（mod7）不符合
67≡1（mod3），67≡4（mod7）不符合
78≡0（mod3），78≡1（mod7）不符合
89≡2（mod3），89≡5（mod7）不符合
100≡1（mod3），100≡2（mod7）不符合
122≡2（mod3），122≡3（mod7）不符合
133≡1（mod3），133≡0（mod7）不符合
144≡1（mod3），144≡4（mod7）不符合
155≡2（mod3），155≡1（mod7）不符合
166≡1（mod3），166≡5（mod7）不符合
177≡0（mod3），177≡2（mod7）不符合
188≡2（mod3），188≡6（mod7）不符合
199≡1（mod3），199≡3（mod7）不符合
210≡0（mod3），210≡0（mod7）不符合
221≡2（mod3），221≡4（mod7）符合
因此符合條件的數(shù)是221。
例5判斷以下計算是否正確
�。�1）42784×3968267=1697598942346
�。�2）42784×3968267=1697598981248
思路分析：若直接將右邊算出，就可判斷
41784×3968267=169778335328，可知以上兩結(jié)果均是錯的；但是計算量太大。
如果右式和左式相等，則它們除以某一個數(shù)余數(shù)一定相同。因為求一個數(shù)除以9的余數(shù)只需要先求這個數(shù)數(shù)字之和除以9的余數(shù)，便是原數(shù)除以9的余數(shù)。我考慮上式除以9的余數(shù)，如果余數(shù)不相同，則上式一定不成立。
�。�1）從個位數(shù)字可知，右式的個位數(shù)字只能是8，而右式個位為6，因此上式不成立。
（2）右式和左式的個位數(shù)字相同，因而無法斷定上式是否成立，但是
4+2+7+8+4=25，25≡7（mod9）
3+9+6+8+2+6+7=41，41≡5（mod9）
42784≡7（mod9）；3968267≡5（mod9）
42784×3968267≡35（mod9）
≡8（mod9）
�。�1+6+9+7+5+9+8+9+4+2+3+4+8）≡3（mod9）
因此（2）式不成立
以上是用"除9取余數(shù)"來驗證結(jié)果是否正確，常被稱為"棄九法"。
不過應(yīng)該注意，用棄九法可發(fā)現(xiàn)錯誤，但用棄九法沒找出錯誤卻不能保證原題一定正確。
習題
1、求16×941×1611被7除的余數(shù)。
3、判斷結(jié)果是否正確：（1）5483×9117=49888511
�。�2）1226452÷2683=334
4、乘法算式
3145×92653=291093995的橫線處漏寫了一個數(shù)字，你能以最快的辦法補出嗎？
5、13511，13903，14589被自然數(shù)m除所得余數(shù)相同，問m最大值是多少？
【小學奧數(shù)競賽專題之同余問題】相關(guān)文章：
小學奧數(shù)專題之博弈問題07-13
小學奧數(shù)競賽專題07-12
小學奧數(shù)關(guān)于年齡問題的競賽專題07-12
小學奧數(shù)競賽時鐘問題的專題練習07-13
奧數(shù)專題之追及問題08-01
奧數(shù)專題之工程問題08-02
奧數(shù)專題之還原問題07-13
奧數(shù)專題之盈虧問題精選07-13