週末燒燒腦：超5星難度的奧數題

今天的題目是關於最大公約數問題，

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

題目（超5星難度）：

如果兩個正整數的最大公約數是1，就稱它們互素。在1到2018的所有自然數中，使5n+3和3n+4互素的自然數n共有多少個？

答案：1835。

輔導辦法:

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

講解思路：

碰見涉及到最大公約數的問題，

都要回想起輾轉相除法，

該方法又叫歐幾里得除法，

是求最大公約數的常用方法。

奧數君在17年4月16日曾詳細介紹，

如需深入瞭解，

點擊進入輾轉相除法介紹。

本題中將借用這種思路。

步驟1：

先思考第一個問題，

5n+3和3n+4的最大公約數可能是多少？

當n在1-2018中時，

5n+3總大於3n+4，

借用輾轉相除法的思路:

(5n+3)=(3n+4)+(2n-1),

(3n+4)=(2n-1)+(n+5),

(2n-1)=(n+5)+(n-6)

(n+5)=(n-6)+11,

故最大公約數一定是11的約數，

而11是素數，

故5n+3和3n+4的最大公約數是1或11。

步驟2：

再思考第二個問題，

5n+3和3n+4的最大公約數何時是11？

從步驟1的過程中知道，

如果二者最大公約數是11，

則(2n-1)、(n+5)和(n-6)都是11的整數倍，

即n+5是11的整數倍，

所以n=6,17,28,39……,

規律是前後相差11。

步驟3：

再思考第三個問題，

滿足題目中條件的n有多少個？

由於2018=6+182*11+10，

故滿足步驟2的n最大是2008，

即共有183個。

根據步驟1的結論，

二者的最大公約數不是11就是1，

因此用總數減去183就是要求的結果，

所以答案是2018-183=1835個。