費氏數列前1000項中，有幾項是170的倍數？

Question

費氏數列：fn=fn-1+fn-2，f1=f2=1請問費氏數列前1000項中，有幾項是170的倍數？

Answer 1

有一個小小問題，就是：
f(5)|f(5n)→5|f(5n)
一定沒問題，但是僅僅只有m=5n時，才有5|f(m)嗎?
會不會有不是5的倍數讓5|f(m)??
從證明中看不見這個證明，只能說22個是最少的。
我想答案沒錯，但是各位高手有辦法嚴謹證明嗎？？

2006-07-05 10:50:33 補充：
[定理1]
利用輾轉相除法以及 f(n+2)＝f(n+1)＋f(n)，則得到：
（f(n)，f(n-1)）＝（f(n-1)，f(n-2)）＝……＝（f(2)，f(1)）＝1
換句話說，對任意 n>1 有 f(n) 與 f(n-1) 互質。
[定理2]
假若 n 為最小正整數使得 s | f(n) ，則有 s | f(m) 若且唯若 n | m。
【證明】
1° 當 k < n → f(k) 不為 s 的倍數。

2° 由 [定理1] f(n-1) 與 f(n) 互質。

3° 因為 f(1) ＝ f(2) ＝ 1，所以
f(n+1)≡ f(n) + f(n-1) ≡ f(n-1) ≡ f(n-1)*f(1) （mod s）
f(n+2)≡ f(n+1) + f(n) ≡ f(n+1) ≡ f(n-1)*f(2) （mod s）
f(n+3)≡ f(n+1) + f(n+2) ≡ f(n-1)*（f(1)＋f(2)）≡ f(n-1)*f(3)（mod s）
……
所以得知
當 k < n → f(n+k) ≡f(n-1)*f(k)（mod s）不為 s 的倍數。
當 k = n → f(2n) ＝ f(n+n) ≡ f(n-1)*f(n) ≡ 0（mod s）為 s 的倍數。

再由 [定理1] 可知（f(2n-1)，f(2n)）＝（f(3n-1)，f(3n)）＝…＝1，同理可證
當 k < n → f(a*n+k) ≡f(a*n-1)*f(k)（mod s）不為 s 的倍數。
當 k = n → f((a+1)*n) ＝ f(a*n+n) ≡ f(a*n-1)*f(n) ≡ 0（mod s）為 s 的倍數。
◆得證◆

由 [定理2] 可知：
因為170 ＝ 2 × 5 × 17 又依序找出最小正整數 2 | f(3)＝2、5 | f(5)＝5、17 | f(9)＝34。
可知 n＝[3，5，9]＝45 為最小正整數使得 170 | f(n) → 170 | f(m) 若且唯若 45 | m。
所以前1000項為 170 的倍數之個數為 [1000 / 45] = 22 個。

2006-07-05 12:08:04 補充：
由 [定理2] 可以推出更強的定理：f(a) | f(m) 若且唯若 a | m【證明】因為 f(n) 為遞增數列，所以 n＝a 為最小正整數使得 f(a) | f(n)所以 f(a) | f(m) 若且唯若 a | m。

2006-07-05 19:46:40 補充：
互相學習、成長！！這樣奇摩知識才能發揮功能阿^_^

2006-07-07 21:43:32 補充：
我一開始也是這樣測試的，但是用「臆測」的規則常常出問題。
可能就會發生數字大一些時，就脫離規則。而且對任意數都要測試看看，就不嚴謹也不方便。
所以我的作法就是直接觀察「模 n」時的情形，而且「模 n」是個環(Ring)，所以一開始就想到「最小正整數」的問題，結果順利證明。

2006-07-10 20:39:56 補充：
當然阿～你想想，用「眼睛」看到的規則可以算是「定理」嗎？
還有類似「模17」的時候，我們可以利用餘數概念直觀一定會有「循環」的時候，這沒問題，就像你找出的每「36」個是一個循環，可是你有沒有發現，你要的並不是「36」這個數字，而是需要「9」這個數字，那你的想法中，是否一定保證「9個」必循環，對「模數9」會不會發生像這樣：
112358437180……63033603360…
這樣不就掛掉了～
所以要證明每個「餘數0」的前一個項餘數必須與此「模數」互質是重要的部分。
我這樣說明可以嗎～分享經驗！

2006-07-10 20:51:54 補充：
在提供一個小小的概念，有理數在化為小數時，我們知道「10進位」等同於「模10」的概念，所以也一定循環，但是並不是從小數第一位就開始循環：
1011/99999＝0.(01011)(01011)…
我們知道它 5 個循環一次，但是0 呢？
他是小點數第「5k+1」、「5k+3」位才循環，其實有非常多的數列有類似這樣的性質，那我們就無法直接說「每 n 個」才有一個0，這樣不就更難計算個數，所以我在你的問題中，不敢直接斷言就是因為有這類的數列，故採用嚴格的證明。
身為學習「代數領域」的我，曾被「直觀」與「臆測」陷入危險當中，所以養成嚴謹的習慣。

2006-07-12 02:06:06 補充：
所以我說你應該說：
「模17」是36個循環一次，又剛好「每9個」又有一個「0」
那請問一下：你可以斷言對於任意「模n」若是「m個」大循環一次，是否保證有一個k|m，而使得「k個」小循環一次，所以我的重點是擺在那「小循環」而不是大循環，這樣你有稍稍瞭解我的意思嗎？
所以我證明了如果「模n」的「最小循環」是k個，那保證只有當k|m的時候，第m個保證整除，而不必須一定要找出「大循環」來，尤其當「n」很大時～
謝謝指教^_^

2006-07-12 02:25:34 補充：
當初我就是你擔心把「大循環必為小循環的倍數」當成「一定的性質」，所以我才會說屬於「臆測」範圍，造成對你的誤會，在此說聲「抱歉～」
我只是希望把類似的題目一併解決，所以作了「一般性證明」。（手癢～）
並且現在已經確定知道「大循環」必為「最小循環」的倍數時，所以只要找到「小循環」就可以停止，就像你「模17」的找法，其實只要找到「9個小循環」就可以停止了，不必要辛苦找到「36個大循環」，這樣是不是可以省掉許多時間，而且這樣真的對於任意的「模n」都可以應用，變成「一般性定理」不就更好嘛！^_^

2006-07-12 18:40:39 補充：
那個例子是「假設性」，只是說明對某一個「模數」會不會只存在「大循環」而沒有「小循環」！
再者對於「模170」會轉換成「模2」、「模5」、「模17」問題，因為發現都有「小循環」的存在，所以才乾脆直接證明任意「模n」都必存在「小循環」。
我想學習「數學」碰到「好像有規律」的感覺，應該都會想要直接證明一般性，可能是我個人習慣吧！
上面補充也說啦～我以為你已對一般「模n」的「小循環」認為是一定的規則，所以才會說「臆測」，需要經過證明驗證，而且是我學藝不精沒學過這樣的定理，才會想要證明看看。若只是針對「模170」就好，那你的想法比較簡單，我贊成～

Answer 2

我是這樣想，
以模2重寫費氏數列，
110110110....(3位一個循環)，可知2|f(n)，若且唯若3|n

以模5重寫費氏數列，
1123033140443202241011....(20位一個循環)，可知5|f(n)，若且唯若5|n

以模17重寫費氏數列，
112358(13)40448(12)3(15)1(16)0(16)(16)(15)(14)(12)94(13)0(13)(13)95(14)2(16)1011....(36位一個循環)，可知17|f(n)，若且唯若9|n
[3,5,9]=45
所以170|f(n)，若且唯若45|n

2006-07-09 23:19:29 補充：
臆測？你說這是臆測？

2006-07-10 23:01:34 補充：
不太了解你在說什麼，
112358(13)40448(12)3(15)1(16)0(16)(16)(15)(14)(12)94(13)0(13)(13)95(14)2(16)10
的確是剛好每9項才出現一個0呀！
「連續出現兩個1就開始循環」，所以每36位一個循環，所以說17|f(n)，若且唯若9|n，這是模17。


如果模9的話，
11235843718088764156281011....
所以每24位一個循環，24位中只有第12和第24位是0，所以9|f(n)，若且唯若12|n，哪有63033603360呢？

2006-07-10 23:07:06 補充：
會有循環並不是一個直觀，那是因為數列終於連續出現了2個1(要連續2個1，只有一個1不行)，根據費氏數列的性質，它當然會循環下去。你可能沒注意到我的刪節號前面兩位是11唷！

2006-07-12 09:35:56 補充：
其實你證的這個定理我早就知道了，只是我無法完整證明它，當然我不是不懂得用它，但我的習慣是(大部分時候)自己無法證明的定理就不使用，因為我無法說服我自己它是對的，所以我才用"非一般性"的找循環的方式來做。
是的，它是不能推廣到任意n，但對於這題已經足夠了不是嗎？

它是嚴謹、非直觀、不只用眼睛看到還用數學知識看到的，只是沒有"一般性"，結果你說這是"臆測"，我就有點......

如果我認定模17是每9位若且唯若會整除，我算到第18位就好了，何必算到36位？就是要等1,1呀！換句話說，最後兩位是1,0才是一個完整的循環，而不是遇到0就好。

2006-07-12 09:41:04 補充：
而且你說
對「模數9」會不會發生像這樣：
112358437180……63033603360…
這個63033603360到底是怎麼來的？我不明白。
明明是112358437180887641562810

Answer 3

f(n)表為Fibonacci's Sequence。
5|f(5n)，34|f(9n)，所以170|f(45n)
又1000÷45=22……10，故所求= ２２

2006-07-05 14:06:59 補充：
被你發現了。我寫完時，其實知道答案肯定是對的，但內容不夠完整。
你真是個不苟的人！感謝你的證明！