◆広島県 清川 育男 さんからの解答。
【準備】
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= | αn-βn α-β |
と書ける。 |
α= | 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 |
(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で割り切れる。