■フィボナッチ数の周期性

 コラム「電卓のちから」で,フェルマー数の周期性について取り上げましたが,ここではフィボナッチ数の周期性について調べてみます.

===================================

【1】フィボナッチ数の周期性

 フィボナッチ数Fnにはある程度の周期性があります.たとえば,フィボナッチ数の1の位は周期60で循環します.すなわち,F1,F61,F121の1の位は等しくなります.周期はずっと長くなりますが,下2桁(300周期),下3桁(1500周期)でも周期性があります.

 1の位が60の周期をもつことのFnの1の位とは,単にFn(mod10)のことです.Fn(mod m)も周期的になるのですが,ここで,Fn(mod m)の循環部分の長さを表にしてみましょう.

     m  Fn の周期     m  Fn の周期

     1    1       9   24

     2    3      10   60

     3    8      11   10

     4    6      12   24

     5   20      25  100

     6   24     100  300

     7   16    1000 1500

     8   12

 周期の長さはいろいろですが,そこには何か規則性が隠されているように感じられます.実際,フィボナッチ数列をmで割った余りについての周期の長さをf(m)とすると,

  f(m)が奇数→m=2

  f(m)=4s→F2s=0(mod m)

が成り立ちます.

 また,周期性はいくつかの整数を法とする合同で計算(わり算)を行ったときの余りに関連することなので,整除性(ある特定の整数で割り切れるという性質)と密接に関係します.

 F3=2ですが,2の倍数は3項ごとに現れます.以下,

  F4=3 → 3の倍数は4項ごとに現れる

  F5=5 → 5の倍数は5項ごとに現れる

  F6=8 → 8の倍数は6項ごとに現れる

 これにより,フィボナッチ数はきれいな規則性に従って並んでいることがわかりますが,フィボナッチ数の整除性をまとめると,

(1)各素数pに対して,pで割り切れるようなFnがある.

(2)奇素数p(p≠5)に対して

  p=±1(mod5)→Fp-1=0(modp)

  p=±2(mod5)→Fp+1=0(modp)

すなわち,

  p=±1(mod5)に対するFp-1はpで割り切れる.

  p=±2(mod5)に対するFp+1はpで割り切れる.

  p=5ならばp=Fp

(3)奇素数に対して

  Fp=5^((p-1)/2)(mod5)

なので,

  p=±1(mod5)←→Fp=+1(modp)

  p=±2(mod5)←→Fp=−1(modp)

===================================