費波那契數列大難題，請高手出馬吧！

Question

大家好！我是兔喵貓！既然我誠心誠意的發問了，您就大發慈悲的回答喵貓吧！費波那契數列（１，１，２，３，５，８．．）中令Ｆｎ為數列中第ｎ項（１）　　試證明：除了Ｆ４（＝３）之外　　若Ｆｎ為質數，則ｎ為質數（２）證明其逆不真如果這真的很難，試著證明一部分吧！如果這很簡單，就請證明之讓喵貓體認自己的才疏學淺

Answer 1

其逆不真的例子
F19=4181=113*37
這是最小的反例，藉助Excel和這個找質數的網站http://www.kwuntung.net/hkunit/prime/prtop.php

看錯儲存格....

2006-06-03 23:34:19 補充：
先參考這題，不管我的證明好不好，總之這個公式是正確的。http://tw.knowledge.yahoo.com/question/?qid=1306031510698f(m+n)=f(m+1)*f(n)+f(m)*f(n-1)----抱歉，改小寫比較好打令m=a，n=ak，則f(a+ak)=f(a+1)*f(ak)+f(a)*f(ak-1)現在要證明f(a) | f(ab)，f(a)是已給定的某項當b=1時，f(a) | f(a)成立假設b=k時，f(a) | f(ak)成立，當b=k+1時，f(a(k+1))≡f(a+ak)≡f(a+1)*f(ak)+f(a)*f(ak-1)≡f(a+1)*f(ak)≡0(mod f(a))故b=k+1時也成立，根據數學歸納法的原理，f(a) | f(ab)恆真。證明「f(ｎ)為質數，則ｎ為質數」等於證明「ｎ為合數，則f(ｎ)為合數」由f(a) | f(ab)可知，n必可寫成a,b的乘積，且f(a) | f(n)，且f(a)≠1且f(a)≠f(n)，故f(n)為合數(因為它有1和本身以外的因數)。為什麼必可找到a，使得f(a)≠1且f(a)≠f(n)呢？因為你已排除掉f(4)=3，故n≧6，6以上的合數必有「1,2,本身」以外的因數，但費氏數列等於1的只有f(1)和f(2)而已，故得知。換個說法好了，f(a) | f(ab)恆真，包括f(4)=3也不例外：f(1) | f(4)且f(2) | f(4)且f(4) | f(4)，但很可憐，f(4)依然是個質數，因為f(1),f(2),f(4)分別是1,1,3。其逆不真，最小的反例：f(19)=4181=37*113

2006-06-03 23:47:52 補充：
這並不太簡單，你實在才濟學廣喔！
之所以這麼快答出來，是因為我以前證過f(a)|f(ab)。
在這之前，"不小心"發現f(m+n)=f(m+1)*f(n)+f(m)*f(n-1)這個重要公式，然後又"不小心"發現它可以證f(a)|f(2a)，然後又"不小心"發現可以推廣到f(a)|f(ab)，三個不小心都摸索了很久，因為我很懶，懶得看書，都自己拿紙亂算。

Answer 2

引理一：費波那契數列F(n)，F(n+m)=F(n-1)F(m)+F(n)F(m+1)
證明：對m用數學歸納法證明
(1)
m=1時，因F(1)=F(2)=1，F(n+1)=F(n-1)F(1)+F(n)F(2)=F(n-1)+F(n)，成立
m=2時，F(n+2)=F(n-1)F(2)+F(n)F(3)=F(n-1)+F(n)[F(1)+F(2)]=F(n+1)+F(n)，成立
(2)
假設m=k與m=k+1時，式子成立
則F(n+k)=F(n-1)F(k)+F(n)F(k+1) 且 F(n+k+1)=F(n-1)F(k+1)+F(n)F(k+2)
兩式相加得F(n+k)+F(n+k+1)=F(n-1)[F(k)+F(k+1)]+F(n)[F(k+1)+F(k+2)]
即F(n+k+2)=F(n-1)F(k+2)+F(n)F(k+3)，m=k+2時，成立
由數學歸納法得證

引理二：費波那契數列F(n)，若m|n，則F(m)|F(n)
證明：
設n=mk，對k用數學歸納法證明
(1)k=1，則n=m，F(m)|F(n)成立
(2)假設對k，F(m)|F(mk)成立
由引理一，F(m(k+1))=F(mk+m)=F(mk-1)F(m)+F(mk)F(m+1)
因F(m)|F(mk)，故F(m)|F(m(k+1))
由數學歸納法得證

定理：若n≠4，n為合成數，則F(n)也是合成數
證明：
設n=ab，n≠4，1＜a＜n，1＜b＜n，則 a＞2或b＞2
不妨設a＞2，由引理二得知F(a)|F(n)，所以F(n)是合成數

推論：定理的逆否命題成立：n≠4，若F(n)是質數，則n是質數

Answer 3

113*17=4181??

2006-06-03 23:52:07 補充：
@@我...我慢慢看....