關於費式數列的餘數問題

Question

（一） 數列：1,1,2,3,5,8,13,.........每個數是前兩個數的和。   這個數列中第 1995 個數除以 8 所得的餘數是多少？   該不會真的要代入公式，求出第 1995 個數後再來除吧！ （二）那前 1999 個數字和除以 6 的餘數是多少？   這兩題應該是不一樣的吧！作法會差不多嗎？   已經知道答案，但想了好幾天都想不出來，會的人教教我吧！

厲害，你答對了。感謝你的解法。
那第二題也是類似的觀念嗎？

Answer 1

第一題
以同餘的觀念解，把費式數列的每個數都求出模8的餘數，則
下式仍然成立：第n項≡第(n-1)項+第(n-2)項(mod 8)
於是我們可以重新寫過費式數列
1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3......(每一項等於前兩項之和再模8的餘數)
每12位為一個循環，1995=166*12+3，所以餘2

第二題
跟第一題有大同小異之處
以模6來寫費式數列
1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,2,5,1,0,1,1,2,3.......
24位是一個循環，
而一個循環的餘數會1+1+2+3+5+2+1+3+4+1+5+0+5+5+4+3+1+4+5+3+2+5+1+0≡0(mod 6)
所以前24n項之和除以6都餘0，
1999=83*24+7
1+1+2+3+5+2+1≡3(mod 6)(取前7項)
所以餘3

附帶一提，何時開始循環？當連續兩項是1,1時就開始循環了。

Answer 2

是啊..厲害了.這種東西就是靠實力的..沒有地方可以轉貼了吧...

Answer 3

兩個高手同台較勁囉.........

Answer 4

==========解題之前先看一下==========

其實fibonacci sequence有不少漂亮的性質



1.連續f(n)與f(n+1)互質, 也就是gcd(f(n),f(n+1))=1



2.f(m) | f(mn)



3.m=qn+r....其中0≦r


4.gcd(f(m),f(n))=f(gcd(m,n))



5.f(m) | f(n) iff m | n




==========先看第一題好了==========

由5可知

f(6) | f(n) iff 6 | n

f(6)剛好就是8

所以f(6k)都是8的倍數

我原本是想說會不會

f(n)模8=f(n模6)

後來發現是不對的

因為f(7)模8=5並不等於f(7模6)=f(1)=1

不過很剛好的

再下一次的就會等於了

也就是f(13)模8=1=f(13模6)



所以要當n很大時

f(n)模8=f(n模12)模8

f(1995)模8=f(1995模12)模8=f(3)模8=2



==========解第二題之前先看一下==========
fibonacci的前n項的和會是什麼
其實不難看出來
s(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
這時候我們把s(n)加上1也就是f(2)
那會變成
1+s(n)=f(2)+f(1)+f(2)+f(3)+f(4)+...+f(n)
=f(3)+f(2)+f(3)+f(4)+...+f(n)
=f(4)+f(3)+f(4)+...+f(n)
=...
=f(n+1)+f(n)
=f(n+2)
所以
s(n)=f(n+2)-1
所以要算前n項和模6其實就在算第n+2項-1模6

==========再回頭來看第二題==========
這問題就類似第一題了
但是6並不是fibonacci number
不過6=2*3
2跟3都是fibonacci number
再加上前面的2
所以我們可以推得
f(3) | f(n) iff 3 | n
f(4) | f(n) iff 4 | n
而f(3)=2, f(4)=3
又gcd(2,3)=1
所以
f(3)f(4) | f(n)
iff f(3) | f(n) 且 f(4) | f(n)
iff 3 | n 且 4 | n
iff 12 | n

那同第一題的
是不是
f(n)模6=f(n模12)
但是很不幸的
跟第一題一樣
是不會的
但又很巧的第二次時就會了
也就是
f(n)模6=f(n模24)模6s(1999)=f(2001)-1f(2001)模6=f(2001模24)模6=f(9)模6=34模6=4所以s(1999)模6=4-1=3==========最後來看看這個巧合==========二題都很巧的在第二次就會同餘了那麼是不是就是說f(2m+1) ≡ f(1) (mod f(m))其實不對的因為當m=7時f(15) ≡ -1 (mod13)但是四次就又同餘了接下來我試了不少的數都是四次就同餘了那是不是f(4m+1) ≡ f(1) (mod f(m))這就留給大家去想想嚕其實還有一些想法啦不過再寫下去就沒完沒了了so就此打住嚕