克勞棣 發問時間: 科學數學 · 1 0 年前

費氏數列前1000項中,有幾項是170的倍數?

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

3 個解答

評分
  • 1 0 年前
    最佳解答

    有一個小小問題,就是:

    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」就好,那你的想法比較簡單,我贊成~

    參考資料: 自己~
  • 1 0 年前

    我是這樣想,

    以模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

  • 1 0 年前

    f(n)表為Fibonacci's Sequence。

    5|f(5n),34|f(9n),所以170|f(45n)

    又1000÷45=22……10,故所求= 22

    2006-07-05 14:06:59 補充:

    被你發現了。我寫完時,其實知道答案肯定是對的,但內容不夠完整。

    你真是個不苟的人!感謝你的證明!

還有問題?馬上發問,尋求解答。