■(a^2+b^2−1)/abの整除性(その8)

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

  1,1,2,3,5,8,13,21,34,55,89,・・・

の各項を2で割った余りをとると(mod2で考えると),

  1,1,0,1,1,0,・・・

3項ごとに元に戻ることがわかる.

 3で割った余りなら,

  1,1,2,0,2,2,1,0,1,1,2,・・・

のように8項毎に元に戻る.

 mod5のとき,

  1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2,・・・

20項毎に循環している.

 mod7のとき,

  1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,・・・

16項毎に循環している.

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

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

【1】フィボナッチ数列と有限体

 いよいよ,循環節の長さにどういう規則があるのかという問題に突入します.

  f(m)が奇数→m=2

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

だけではつまらないでしょう.

 ここでは有限体を扱うので,フィボナッチ数列を奇素数pを法として考えることにします.すると,奇素数pに対して循環する項数をf(p)とすると,

  f(3)=8,f(5)=20,f(7)=16,f(11)=10,

  f(13)=28,f(17)=36,f(19)=18,・・・

となっていますから,

  p=±1(mod5)のとき,f(p)=p−1

  p=±2(mod5)のとき,f(p)=2p+2

と予想できます.

 ただし,5は例外としておき,pは5以外の奇素数であるとします.そのとき,ビネの公式:

  Fn =1/√5[{(1+√5)/2}^n−{(1−√5)/2}^n]

はmodpで考えても意味をもつことになります.

(1)もし√5すなわちx^2=5の根が有限体Fpの中にあれば,ビネの公式はFpの元として意味をもつ

(2)Fpの中になければ,その根はFp^2の中にあり,その根の一つを√5とすれば,ビネの公式はFp^2の元として意味をもつ

ことになります.

 たとえば,p=11であるとすると,方程式x^2=5(mod11)の根として,x=4とx=7の2根がありますから,√5=4とおくと,7=−4=−√5

したがって,

  (1+√5)/2=5/2=5・6=8

  (1−√5)/2=−3/2=8/2=4

より,法11でのフィボナッチ数列の一般項は

  Fn=1/4(8^n−4^n)=3・(8^n−4^n)

 確認のために計算してみると

  F1=3・4=1,F2=3・4=1,F3=3・8=2,

  F4=3・1=3,F5=3・9=5,・・・

となり,正しいことが確認されます.

 次に,p=7とすると,x^2=5(mod7)はF7の中には根をもたないので,x^2=5の一つの根を√5とおき,それをF7につけ加えて有限体F7^2をつくることができます.そのとき,もう一つの根は−√5になっており,一般項は

  Fn =1/√5[{(1+√5)/2}^n−{(1−√5)/2}^n]

とまったく同じ式で与えられます.

  F1 =1/√5[{(1+√5)/2}−{(1−√5)/2}]

    =1/√5・√5=1

  F2 =1/√5[{(1+√5)/2}^2−{(1−√5)/2}^2]

    =1/√5・√5=1

  F3 =1/√5[{(1+√5)/2}^3−{(1−√5)/2}^3]

は2^3=1を用いると

  F3 =1/√5[(2+√5)−(2−√5)]=2

となって正しいことが確認されます.

 5以外の奇素数pに対して,方程式x^2=5は

(1)p=±1(mod5)ならば,有限体Fpの中に根をもつ

(2)p=±2(mod5)ならば,有限体Fpの中に根をもちません.

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