初項１，第２項１から始まり，隣り合う２項の和が次の項となるフィボナッチ数列

　　１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・

の各項を２で割った余りをとると（ｍｏｄ２で考えると），

　　１，１，０，１，１，０，・・・

３項ごとに元に戻ることがわかる．

　３で割った余りなら，

　　１，１，２，０，２，２，１，０，１，１，２，・・・

のように８項毎に元に戻る．

　ｍｏｄ５のとき，

　　１，１，２，３，０，３，３，１，４，０，４，４，３，２，０，２，２，４，１，０，１，１，２，・・・

２０項毎に循環している．

　ｍｏｄ７のとき，

　　１，１，２，３，５，１，６，０，６，６，５，４，２，６，１，０，１，１，・・・ １６項毎に循環している．

　このような性質を周期性というのだが，任意の自然数でフィボナッチ数を割っていくと，必ず周期性が現れる．循環節の長さには，はたしてどういう規則があるのだろうか？

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

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

　フィボナッチ数Ｆ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＝−１（ｍｏｄｐ）

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

まとめ

mod pのフィボナッチ数の周期c(p)は

[1]ｐ＝±１（ｍｏｄ５）のとき、p-1の約数

[2]ｐ＝±２（ｍｏｄ５）のとき、2(p+1)の約数

mod n=pqのフィボナッチ数の周期c(p)は

c(p)=LCM{c(p),c(q)}

mod n=p^eのフィボナッチ数の周期c(p^e)は

c(p)=p^(e-1)c(p)

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