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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

　フィボナッチ数Ｆnにはある程度の周期性があります．たとえば，フィボナッチ数の１の位は周期６０で循環します．すなわち，Ｆ1，Ｆ61，Ｆ121の１の位は等しくなります．周期はずっと長くなりますが，下２桁（３００周期），下３桁（１５００周期）でも周期性があります．

　１の位が６０の周期をもつことのＦnの１の位とは，単にＦn（ｍｏｄ１０）のことです．Ｆn（ｍｏｄ　ｍ）も周期的になるのですが，ここで，Ｆn（ｍｏｄ　ｍ）の循環部分の長さを表にしてみましょう．

　　　　　ｍ　　Ｆn の周期　　　　　ｍ　　Ｆn の周期

　　　　　１　　　　１　　　　　　　９　　　２４

　　　　　２　　　　３　　　　　　１０　　　６０

　　　　　３　　　　８　　　　　　１１　　　１０

　　　　　４　　　　６　　　　　　１２　　　２４

　　　　　５　　　２０　　　　　　２５　　１００

　　　　　６　　　２４　　　　　１００　 ３００

　　　　　７　　　１６　　　　１０００　１５００

　　　　　８　　　１２

　周期の長さはいろいろですが，そこには何か規則性が隠されているように感じられます．実際，フィボナッチ数列をｍで割った余りについての周期の長さをｆ（ｍ）とすると，

　　ｆ（ｍ）が奇数→ｍ＝２

　　ｆ（ｍ）＝４ｓ→Ｆ2s＝０（ｍｏｄ　ｍ）

が成り立ちます．

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

　Ｆ3＝２ですが，２の倍数は３項ごとに現れます．以下，

　　Ｆ4＝３　→　３の倍数は４項ごとに現れる

　　Ｆ5＝５　→　５の倍数は５項ごとに現れる

　　Ｆ6＝８　→　８の倍数は６項ごとに現れる

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

(1)各素数ｐに対して，ｐで割り切れるようなＦnがある．

(2)奇素数ｐ（ｐ≠５）に対して

　　ｐ＝±１（ｍｏｄ５）→Ｆp-1＝０（ｍｏｄｐ）

　　ｐ＝±２（ｍｏｄ５）→Ｆp+1＝０（ｍｏｄｐ）

すなわち，

　　ｐ＝±１（ｍｏｄ５）に対するＦp-1はｐで割り切れる．

　　ｐ＝±２（ｍｏｄ５）に対するＦp+1はｐで割り切れる．

　　ｐ＝５ならばｐ＝Ｆp

(3)奇素数に対して

　　Ｆp＝５^((p-1)/2)（ｍｏｄ５）

なので，

　　ｐ＝±１（ｍｏｄ５）←→Ｆp＝＋１（ｍｏｄｐ）

　　ｐ＝±２（ｍｏｄ５）←→Ｆp＝−１（ｍｏｄｐ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝