巧解整除問題（18年9月19日）

來自專欄每天來道奧數題4 人贊了文章

這是奧數君第624天給出奧數題講解。

今天的題目是整除問題，

所用知識不超過小學5年級。

題目（5星難度）：

有一個自然數n，最後四位數字是2018，且n是59的整數倍。滿足條件的n最小是多少？

輔導辦法:

題目寫給小朋友，讓他自行思考解答，若20分鐘還不能解答，由家長講解。

講解思路：

這道題如果直接求解，

就是採用除法的逆過程，

逐步從商的個位開始起湊，

這種方法雖可行但較繁瑣。

下面我們介紹另一種簡單的做法，

利用餘數的性質簡化計算。

先複習兩個知識點：

設m,n,p,q,a,b都是正整數,

p除以n的餘數是a,

q除以n的餘數是b,

(1)若m=p+q,

則m與a+b除以n的餘數相同；

(2)若m=p*q,

則m與a*b除以n的餘數相同。

為解題方便，

假設n=a*10000+2018,

其中a是個自然數。

步驟1：

先思考第一個問題，

n除以59的餘數如何用a表示？

如果a除以59的餘數是b，

則因為10000=169*59+29，

2018=34*59+12，

故應用上面兩個知識點可得，

29b+12是59的整數倍,

因此存在一個自然數k，

使29b+12=59k。

步驟2：

再思考第二個問題，

滿足步驟1條件的b可能是多少？

顯然b的範圍是0到58，

對步驟1的結論進行化簡變形，

即29(b-2k)+12=k。

注意到b和k的範圍，

k只能是12，

此時b-2k=0,

因此b=24。

步驟3：

綜合上述兩個問題，

考慮滿足條件的最小的n。

要使n最小，a也應最小，

根據步驟2的結論，

a除以59的餘數是24，

顯然a最小是24，

所以n最小是242018。

思考題 (4星難度)：

在1到2018的所有自然數中，使49n+13是99的整數倍的n有多少個？

獲得思考題答案方法：

關注微信公眾號「每天3道奧數題」（tiantianaoshu)

微信回復「20180919」可獲得思考題答案。

註：過4個月之後，關鍵詞回復可能失效。