■フィボナッチ数の周期性（その２）
初項１，第２項１から始まり，隣り合う２項の和が次の項となるフィボナッチ数列
１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・
の各項を２で割った余りをとると（ｍｏｄ２で考えると），
１，１，０，１，１，０，・・・
３項ごとに元に戻ることがわかる．
３で割った余りなら，
１，１，２，０，２，２，１，０，１，１，２，・・・
のように８項毎に元に戻る．
ｍｏｄ５のとき，
１，１，２，３，０，３，３，１，４，０，４，４，３，２，０，２，２，４，１，０，１，１，２，・・・
２０項毎に循環している．
ｍｏｄ７のとき，
１，１，２，３，５，１，６，０，６，６，５，４，２，６，１，０，１，１，・・・
１６項毎に循環している．
このような性質を周期性というのだが，任意の自然数でフィボナッチ数を割っていくと，必ず周期性が現れる．循環節の長さには，はたしてどういう規則があるのだろうか？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】フィボナッチ数列と有限体
いよいよ，循環節の長さにどういう規則があるのかという問題に突入します．
ｆ（ｍ）が奇数→ｍ＝２
ｆ（ｍ）＝４ｓ→Ｆ2s＝０（ｍｏｄ ｍ）
だけではつまらないでしょう．
ここでは有限体を扱うので，フィボナッチ数列を奇素数ｐを法として考えることにします．すると，奇素数ｐに対して循環する項数をｆ（ｐ）とすると，
ｆ（３）＝８，ｆ（５）＝２０，ｆ（７）＝１６，ｆ（１１）＝１０，
ｆ（１３）＝２８，ｆ（１７）＝３６，ｆ（１９）＝１８，・・・
となっていますから，
ｐ＝±１（ｍｏｄ５）のとき，ｆ（ｐ）＝ｐ−１
ｐ＝±２（ｍｏｄ５）のとき，ｆ（ｐ）＝２ｐ＋２
と予想できます．
ただし，５は例外としておき，ｐは５以外の奇素数であるとします．そのとき，ビネの公式：
Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］
はｍｏｄｐで考えても意味をもつことになります．
コラム「因数分解の算法（その３）」の復習になるのですが，
(1)もし√５すなわちｘ^2＝５の根が有限体Ｆpの中にあれば，ビネの公式はＦpの元として意味をもつ
(2)Ｆpの中になければ，その根はＦp^2の中にあり，その根の一つを√５とすれば，ビネの公式はＦp^2の元として意味をもつ
ことになります．
たとえば，ｐ＝１１であるとすると，方程式ｘ^2＝５（ｍｏｄ１１）の根として，ｘ＝４とｘ＝７の２根がありますから，√５＝４とおくと，７＝−４＝−√５
したがって，
（１＋√５）／２＝５／２＝５・６＝８
（１−√５）／２＝−３／２＝８／２＝４
より，法１１でのフィボナッチ数列の一般項は
Ｆn＝１／４（８^n−４^n）＝３・（８^n−４^n）
確認のために計算してみると
Ｆ1＝３・４＝１，Ｆ2＝３・４＝１，Ｆ3＝３・８＝２，
Ｆ4＝３・１＝３，Ｆ5＝３・９＝５，・・・
となり，正しいことが確認されます．
次に，ｐ＝７とすると，ｘ^2＝５（ｍｏｄ７）はＦ7の中には根をもたないので，ｘ^2＝５の一つの根を√５とおき，それをＦ7につけ加えて有限体Ｆ7^2をつくることができます．そのとき，もう一つの根は−√５になっており，一般項は
Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］
とまったく同じ式で与えられます．
Ｆ1 ＝１／√５［｛（１＋√５）／２｝−｛（１−√５）／２｝］
＝１／√５・√５＝１
Ｆ2 ＝１／√５［｛（１＋√５）／２｝^2−｛（１−√５）／２｝^2］
＝１／√５・√５＝１
Ｆ3 ＝１／√５［｛（１＋√５）／２｝^3−｛（１−√５）／２｝^3］
は２^3＝１を用いると
Ｆ3 ＝１／√５［（２＋√５）−（２−√５）］＝２
となって正しいことが確認されます．
５以外の奇素数ｐに対して，方程式ｘ^2＝５は
(1)ｐ＝±１（ｍｏｄ５）ならば，有限体Ｆpの中に根をもつ
(2)ｐ＝±２（ｍｏｄ５）ならば，有限体Ｆpの中に根をもちません．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
懸案の予想
ｐ＝±１（ｍｏｄ５）のとき，ｆ（ｐ）＝ｐ−１
ｐ＝±２（ｍｏｄ５）のとき，ｆ（ｐ）＝２ｐ＋２
を証明してみましょう．
これを示すには，
Ｆf(p)＝０，Ｆf(p)+1＝１
が成り立つことをいえばよいのですが，ｐ＝±１（ｍｏｄ５）のとき，ｘ^2＝５を満たす元ｃが有限体Ｆpのなかにありますから，
Ｆf(p)＝Ｆp-1
＝１／ｃ［｛（１＋ｃ）／２｝^(p-1)−｛（１−ｃ）／２｝^(p-1)］
ここで，フェルマーの定理により，有限体Ｆpのどんな元も
ａ^(p-1)＝１
（ｐ乗すると元に戻る）ですから，
Ｆf(p)＝Ｆp-1＝１／ｃ（１−１）＝０
また，
Ｆf(p)+1＝Ｆp
＝１／ｃ［｛（１＋ｃ）／２｝^p−｛（１−ｃ）／２｝^p］
＝１／ｃ［｛（１＋ｃ）／２｝−｛（１−ｃ）／２｝］
＝１／ｃ・ｃ
＝１
が示されました．
一方，ｐ＝±２（ｍｏｄ５）のとき，有限体Ｆpの中に根をもちませんから，一般項は
Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］
とまったく同じ式で与えられます．
ここで，［］の中を展開しますが，二項係数pＣiは常にｐで割り切れること，有限体Ｆp^2の元ａ＋ｂ√５（ａ，ｂは有限体Ｆpの元）に対して
（ａ＋ｂ√５）^p＝ａ−ｂ√５
となることより，
｛（１＋√５）／２｝^(2p+2)＝（３＋√５）^(p+1)／２^(p+1)
＝（３＋√５）^p（３＋√５）／４
＝（３−√５）（３＋√５）／４＝１
まったく同様にして
｛（１−√５）／２｝^(2p+2)＝１
より，
Ｆf(p)＝Ｆ2p+2＝０
さらに，
Ｆf(p)+1＝Ｆ2p+3
＝１／√５［｛（１＋√５）／２｝^(2p+3)−｛（１−√５）／２｝^(2p+3)］
＝１／√５［｛（１＋√５）／２｝−｛（１−√５）／２｝］
＝１
これで予想が証明されたことになりますが，同時に，５以外の奇素数ｐに対して，フィボナッチ数の第ｆ（ｐ）項はｐで割り切れることが示されました．
なお，この定理の証明は
［参］硲文夫「初等代数学」森北出版
に負っています．実は，小生，有限体を使ったこの意外な証明に驚いて，本コラムでも是非紹介したいと考えた次第です．如何でしたでしょうか？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
