『フィボナッチ数列の性質 Part5』解答


◆広島県 清川 育男 さんからの解答。

【準備】

F(m)はF(mn)を割り切る。すべての自然数m,n

n=1のとき、F(m) | F(m)
成立。

n=kのとき、F(m) | F(mk)が成立すると仮定する。

F(m(k+1))=F(mk+m)=F(mk-1)*F(m)+F(mk)*F(m+1)

F(m) | F(mk) であるから、F(m) | F(m(k+1))

n=k+1 でも成立。


n=F(n) →n=5 (***)


pが7以上の素数のとき
F(p) | F(p) または 1 | F(p)

p≠F(p) であるから、(p,F(p))=1 .............(1)

オイラーの定理より、

ψ(p)=p-1=2*k(偶数)..........................(2)

であり、

(p,F(P))=1 ならば、F(p)ψ(p)≡1 (mod p)......(3)

である。 

(1),(2),(3)より、

(F(P)2)k≡1 (mod p).......................(4)

ゆえに、 F(P)2≡1 (mod p).......................(5) 

(F(n)+1)*(F(n)-1)≡0 (mod p) Final answer

p=2のときも成立。 
pを素数にしたとき、p=5 が例外となりますね。


◆茨城県 小川 康幸 さんからの解答。

フィボナッチ数列を一般化して次のような数列を考える。

U0=0、U1=1、
n≧2のとき、 Un=a*Un-1-b*Un-2
aとbは整数とする。

また、整数dを、d=a2-4*bと定義する。

【問題】

dとbを割り切らない任意の奇素数pに対して、

(1) 任意の整数sに対して、s2-dがpで割り切れない時、
Up+1はpで割り切れる。

(2) ある整数sに対して、s2-dがpで割り切れる時、
Up-1はpで割り切れる。

【解答】

2次方程式 x2-a*x+b=0の解を、α、βとすると、

Un= αnn
α-β
と書ける。

α= a+√d
2
、β=a-√d
2
を代入して整理すると、

nが偶数のとき(nが奇数の場合は使わない)

2n-1*Un= (n-2)/2
Σ
i=0
nC2*i+1*an-1-2*i*di
と書ける。

以降、整数u、v、rに対して、u-vがrで割り切れる時、
u≡v (mod r)と書くことにする。

(1)任意の整数sに対して、s2-dがpで割り切れない時、
Up+1はpで割り切れる。

2p*Up+1= (p-1)/2
Σ
i=0
p+1C2*i+1*ap-2*i*di

1<2*i+1<pなる任意のiに対して、

(2*i+1)!*p+1C2*i+1=(p+1)*p*・・・*(p-2*i)だから、
p+1C2*i+1はpで割り切れる。

よって、

(p-1)/2
Σ
i=0
p+1C2*i+1*ap-2*i*di
p+1C1*ap+p+1Cp*a*d(p-1)/2
≡ap+a*d(p-1)/2
≡a+a*d(p-1)/2 (mod p)

(1)の仮定より、d(p-1)/2≡-1 (mod p)だから、
a+a*d(p-1)/2≡a-a≡0 (mod p)

ゆえに、2p*Up+1≡0 (mod p)

これより、Up+1≡0 (mod p)

証終

(2)ある整数sに対して、s2-dがpで割り切れる時、
Up-1はpで割り切れる。

2p-2*Up-1= (p-3)/2
Σ
i=0
p-1C2*i+1*ap-2-2*i*di

1≦2*i+1≦p-1なる任意のiに対して、

(2*i+1)!*p-1C2*i+1
≡(p-1)*(p-2)*・・・*(p-2*i-1)
≡(-1)2*i+1*(2*i+1)! (mod p)

より、

p-1C2*i+1≡(-1)2*i+1≡-1 (mod p)となるから、

(p-3)/2
Σ
i=0
p-1C2*i+1*ap-2-2*i*di ≡- (p-3)/2
Σ
i=0
ap-2-2*i*di (mod p)

a2*2p-2*Up-1≡- (p-3)/2
Σ
i=0
ap-2*i*di (mod p)

d*2p-2*Up-1
≡- (p-3)/2
Σ
i=0
ap-2*(i+1)*di+1
≡- (p-1)/2
Σ
i=1
ap-2*i*di (mod p)

よって、

4*b*2p-2*Up-1
≡(a2-d)*2p-2*Up-1
≡-(ap-a*d(p-1)/2)
≡-(a-a*d(p-1)/2) (mod p)

(2)の仮定より、d(p-1)/2≡1 (mod p)

よって、-(a-a*d(p-1)/2)≡-(a-a)≡0 (mod p)となる。

これより、2p-2*Up-1≡0 (mod p)

つまり、Up-1≡0 (mod p)となる。

証終

【おまけ】

もともとの問題は、a=1、b=-1 よってd=5の特別な場合
よって、5より大きな任意の素数でUp-1あるいは、Up+1はpで割り切れる。


 『フィボナッチ数列の性質 Part5』へ

 数学の部屋へもどる