斐波那契數列第8項,21=3*7是什麼意思?
01-15
題主不是數學專業的,純粹是好奇。比如8:21=3*716:987=3*7*4719:4181=37*113前面我懂,但是3*7和37*113這些數字是怎麼來的?有什麼規律嗎?
總不能是剛好是相等就寫上的吧。如果後面的演算法有規律可循,請朋友們教我。
已有幾位答主和評論 @王某魚@王贇 Maigo@劉熙航@嗜睡狂魔 提到這是質因數分解,我想已經解答了題主的疑問。實際上,在這個文檔:1-300項斐波那契數列的文檔簡介中就已經寫到:
第1--300項斐波那契數列及其分解質因數
但是,我之前關注這個問題的時候留了個心眼:為什麼要列出這些數的質因數分解呢?
其實我的第一反應是這個定理:
定理1:對於任意的n,、與兩兩互質。
證明:由Euclid輾轉相除法,顯然。
事實上,這個定理還能進一步推廣:
根據定理2可以得出一個推論:定理2:
(GCD指的是最大公因數Greatest Common Divisor)為了證明這一點,可以根據如下引理引理1:當且僅當證明:由數學歸納法即證得(注意到)
推論1:若是質數,則n是質數(反之未必)
所以我一開始猜測的,之所以要在算出斐波那契數之後列出質因數分解,是為了對這些性質進行驗證。
不過,我剛才去找了一下這篇文檔,才發現另外的玄機:
由於題主是用的手機,所以文檔里的顏色沒有顯示出來,實際上這個文檔中的數字是上色的,如下圖:左邊一列的紅色是所有質數。右邊一列的綠色是所有斐波那契數的質因數分解中每個質數的第一次出現。這些綠色的質數被稱為這個斐波那契數的primitive prime factors(本原質因數)
這就又涉及到兩個非常有趣的結論:
定理3(Carmichael定理):對於n&>12,一定有至少一個本原質因數。
(實際上Carmichael定理可以推廣到任意Lucas sequence,即把斐波那契數列的開頭兩項0,1換成其它數字,再按照同樣規則生成的數列)
所以這個質因數分解看似冗餘,實際上卻是有深刻的背景的。推論2:n是質數當且僅當的所有質因數都是本原質因數(需要排除n=2和4)
(這個推論由定理2顯然)
推薦閱讀:
※如何證明斜率確定的直線過橢圓中心時被橢圓所截的弦最長?
※為什麼「試圖構架完整的數學體系」對理工科學生是個危險的想法?
※你身為MOer或OIer,有多麼聰明勤奮?
※大家都是怎麼提高做題速度的呢?或者一般以怎樣的做題速度來對待作業,課外練習和考試的呢?