關於國小奧數競賽專題之同餘問題

[專題介紹]：同餘問題

生活中我會經常遇到與餘數有關的問題，比如：某年級有將近400名學生。有一次演出節目排隊時出現：如果每8人站成一列則多餘1人；如果改為每9人站成一列則仍多餘1人；結果發現現成每10人結成一列，結果還是多餘1人；聰名的你知道該年級共有學生多少名嗎？

假設有一名學生不參加演出，則結果一定是不管每列站8人或9人或10人都將剛好站齊。因此此時學生人數應是8、9、10公倍數，而8、9、10的最小公倍數是360，因此可知該年級共有361人。

研究與餘數有關的問題，能幫助我們解決很多較為複雜的問題。

[分析]

1、兩個整數a和b，除以一個大於1的自然數m所得餘數相同，就稱a和b對於模m同餘或稱a和b在模m下同餘，即a≡b（modm）

2、同餘的重要性質及舉例。

〈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）

其中性質〈3〉常被稱為"同餘的可傳遞性"，性質〈4〉、〈5〉常被稱為"同餘的可乘性，"性質〈6〉常被稱為"同餘的可開方性"

注意：一般地同餘沒有"可除性"，但是：

如果：ac=bc（modm）且（c，m）=1則a≡b（modm）

3、整數分類：

〈1〉用2來將整數分類，分為兩類：

1，3，5，7，9，……（奇數）

0，2，4，6，8，……（偶數）

〈2〉用3來將整數分類，分為三類：

0，3，6，9，12，……（被3除餘數是0）

1，4，7，10，13，……（被3除餘數是1）

2，5，8，11，14，……（被3除餘數是2）

〈3〉在模6的情況下，可將整數分成六類，分別是：

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，……

[經典例題]

例1：求437×309×1993被7除的餘數。

思路分析：如果將437×309×1993算出以後，再除以7，從而引得到，即437×309×1993=269120769，此數被7除的餘數為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個數排成一行，除了兩頭的兩個數以外，每個數的三倍恰好等於它兩邊兩個數的和，這一行最左邊的幾個數是這樣的：0，1，3，8，21，……，問這一行數最右邊的一個數被6除的餘數是幾？

思路分析：如果將這70個數一一列出，得到第70個數後，再用它去除以6得餘數，總是可以的，但計算量太大。

即然這70個數中：中間的一個數的3倍是它兩邊的數的和，那麼它們被6除以後的餘數是否有類似的規律呢？

0，1，3，8，21，55，144，……被6除的餘數依次是

0，1，3，2，3，1，0，……

結果餘數有類似的規律，繼續觀察，可以得到：

0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……

可以看出餘數前12個數一段，將重複出現。

70÷2=5……10，第六段的第十個數為4，這便是原來數中第70個數被6除的餘數。

思路分析：我們被直接用除法算式，結果如何。

例4、分別求滿足下列條件的最小自然數：

（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）該數減去1以後，是3，5和7的最小公倍數105，所以該數的是105+1=106

（2）該數減去1以後是5和7的公倍數。因此我們可以以5和7的公倍數中去尋找答案。下面列舉一些同時被5除餘1，被7除餘1的數，即

1，36，71，106，141，176，211，246，……從以上數中尋找最小的被3除餘2的數。

36≡0（mod3），71≡2（mod3），符合條件的最小的數是71。

（3）我們首先列舉出被5除餘2，被7除餘2的數，2，37，72，107，142，177，212，247，……

從以上數中尋找最小的被3除餘1的'數。

2（mod3），37≡（mod3）、因此符合條件的最小的數是37。

（4）我們從被11除餘1的數中尋找答案。

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）符合

因此符合條件的數是221。

例5判斷以下計算是否正確

（1）42784×3968267=1697598942346

（2）42784×3968267=1697598981248

思路分析：若直接將右邊算出，就可判斷

41784×3968267=169778335328，可知以上兩結果均是錯的；但是計算量太大。

如果右式和左式相等，則它們除以某一個數餘數一定相同。因為求一個數除以9的餘數只需要先求這個數數字之和除以9的餘數，便是原數除以9的餘數。我考慮上式除以9的餘數，如果餘數不相同，則上式一定不成立。

（1）從個位數字可知，右式的個位數字只能是8，而右式個位為6，因此上式不成立。

（2）右式和左式的個位數字相同，因而無法斷定上式是否成立，但是

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取餘數"來驗證結果是否正確，常被稱為"棄九法"。

不過應該注意，用棄九法可發現錯誤，但用棄九法沒找出錯誤卻不能保證原題一定正確。

習題

1、求16×941×1611被7除的餘數。

3、判斷結果是否正確：（1）5483×9117=49888511

（2）1226452÷2683=334

4、乘法算式

3145×92653=291093995的橫線處漏寫了一個數字，你能以最快的辦法補出嗎？

5、13511，13903，14589被自然數m除所得餘數相同，問m最大值是多少？