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


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

n=7m−2 mは自然数

f(n)
n
は整数になる。

フィボナッチ数列が無限にあれば、求めるそれも無限にあることになる。

証明は正五角形の頂点と対応するように回転を利用するのでしょうね。
残念ながらその方法を忘れてしまいました。


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

間違っていました。考えが混線していました。

1,5,12,24,25,36,48,60,72,96,108,
120,125,144,168,180,192,216,240,
288,300,324,336,360,384,432,480,
504,540,552,576,600,612,625,648,
660,672,684,720,768,840,864,900,
960,972,1008,1080, 1104,1152,1176,
1200,1224,1296,1320

12の倍数で不適なもの。

84=2*2*3*7 132=2*2*3*11
156=2*2*3*13 204=2*2*3*17
228=2*2*3*19 256=2*2*2*2*2*2*2*2
268=2*2*67 280=2*2*2*5*7
312=2*2*2*3*13 348=2*2*3*29
372=2*2*3*31 396=2*2*3*3*11
408=2*2*2*3*17 420=2*2*3*5*7


◆東京都 未菜実 さんからの解答。

自然数になるのは、
1、5、12、24、25、36、48、60、72、96・・・とあります。

無数にある証明です。

F(n)をn番目のフィボナッチ数とすると次の公式が成立します。

F(2n)=F(n)×(F(n) +2×F(n‐1))

ここで
F(12)、F(24)、F(48)、F(96)、F(192)…を考えます。

F(12)
12
144
12
=12
で割り切れます。

F(24)=F(12)×L(12)=F(12)×(F(12)+2×F(11))

ここで、F(12)=24×32で2の倍数ですから

F(24)=2×F(12)×( F(12)
2
+F(11))
と表せますからF(24)は24で割り切れます。

以下、同様になりますから、

n=12,24,48,96,192,…はすべて
F(n)
n
が自然数になります。

よって
F(n)
n
が自然数になるものは無限に存在します。


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

十進ベーシック(1000桁)でプログラミングしました。

4800以上はフィボナッチ数が1000桁を越えてしまいます。
予想としては、N=5k(kは自然数)は条件を満たすのではないでしょうか?

1344 1368 1440 
1500 1512 1536 
1620 1656 1680 
1728 1800 1836 
1860 1920 1944 
1980 2016 2052 
2160 2184 2208 
2256 2304 2352 
2400 2448 2460 
2520 2592 2640 
2688 2700 2736 
2760 2880 2916 
3000 3024 3060 
3072 3125 3240 
3300 3312 3360 
3420 3456 3528 
3600 3660 3672 
3720 3840 3852 
3864 3888 3960 
4032 4104 4200 
4320 4368 4416 
4500 4512 4536 
4608 4704 4800


◆東京都 未菜実 さんからのコメント。

解答ではないのですが・・・

清川さんの指摘されている、
「予想としては、N=5k(kは自然数)は条件を満たすのではないでしょうか?」
は多分そうだと思います。
(証明はまだ、 難しいですね。)

その検討途中で気づいた面白い性質があったので、報告です。^^;

「N=5kを満たす…」は
F(5n)=5×F(n)×R(n)を証明すればいいわけです。

で、その報告とは、R(n)は素因数分解するとすべて末尾が1になる素数に分解されそうだと言うことです。

なぜだかよくわかりませんが、おもしろいですね。

R(1)=1  (これは1ですが素数ではないですね。)
R(2)=11
R(3)=61
R(4)=11×41
R(5)=3001
R(6)=11×31×61
R(7)=141961
R(8)=11×41×2161
R(9)=61×109441
R(10)=101×151×3001
R(11)=661×474541
R(12)=11×31×41×61×2521
R(13)=14736206161
R(14)=11×71×911×141961
R(15)=230686501×3001
R(16)=11×41×1601×3041×2161
R(17)=3415914041×9521
R(18)=11×31×61×181×541×109441


◆東京都 未菜実 さんからの解答。

F(5n)
n
が自然数になる。」
の証明を考えて見ました。
これで、合っているのでしょうか?

フィボナッチ数をF(n) 『ルカ数列』をL(n)とし

α= 1+
2

β= 1-
2
と置く。

まず、
F(5n)= α5n5n
 = 55)*S(n)
 =5*S(n) ・・・(1)
(括った項以外をS(n)とする)

一方、公式
2*F(n+m)=L(n)*F(m)+L(m)*F(n) でm=4nと置き
公式 F(2n)=F(n)*L(n)を使用すると

F(5n)= L(4n)*F(n)+L(n)*F(4n)
 = L(4n)*F(n)+L(n)*(F(2n)*L(2n))
 = L(4n)*F(n)+L(n)*F(n)L(n)L(2n)
 = F(n)(L(4n)+L(2n)*L(n)2)
・・・(2)

以上より
F(5n)=5*F(n)*R(n)の形式に書ける。
よって
F(5n)
n
は自然数になる。


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

性質らしいものを見つけました。
素数を求めるときの逆の方法に似ています。

  5,25,125,625,3125,..,
 12,24,48,96,192,384,768,1536,3072,.., 
 36,72,144,288,576,1152,2304,4608,..,
 60,120,240,480.960,1920,3840,..,
108,216,432,864,1728,3456,..,
168,336,672,1344,2688,..,
...................
...................
結局は未菜実さんが証明されたことと同じことですが。
各行の先頭にくる数の求め方は?。


◆東京都 未菜実 さんからの解答。

清川さんのコメントの中の各行の先頭に来る数字を検討してみました。
(証明は未検討です。)

12を起点とし
12×3n×5mはすべて含まれるようです。
(nは自然数,mは0以上の整数)

これに含まれないものは

168=23×3×7
552=23×3×23
612=22×32×17
660=22×3×5×11
684=22×32×19
1176=23×3×72
1860=22×3×5×31

この規則が問題ですね。
(168、1176は×7でなにかありそうですね。)


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

未菜実さんの発見の追加

R(19)=761×29641×67735001
R(20)=101×151×401×3001×570601
R(21)=61×141961×8288823481
R(22)=11×11×331×661×39161×474541
すばらしい発見ですね。


◆東京都 未菜実 さんからの解答。

清川さんの検討の追加です。

R(23)=1381*2441738887963981    
R(24)=11×31×41×61×241×2161×2521×20641
R(25)=158414167964045700001    素数かどうか不明
R(26)=11×131×2081×24571×14736206161 
R(27)=61×109441×1114769954367361
R(28)=11×41×71×911×141961×12317523121
R(29)=349619996930737079890201 素数かどうか不明
R(30)=101×151×3001×12301×18451×230686501

◆東京都 未菜実 さんからのコメント。

解答ではありませんが・・・。

この件に関して、フィボナッチ数についての詳しいHPをつくっておられるサリー大学(UK)のロン・ノット博士に聞いてみたところ、次のような回答がありました。
参考までに、原文を下に示します。

Yes - that's right.
Vajda says this is true on page 84 of "Fibonacci Numbers and Lucas Numbers and the Golden section".
He seems to imply that this is unusual and a unique series as if N=p*q then often there is a p for which F(p) does NOT divide exactly into F(N).

I have not tried very hard yet, but it should not be difficult to show that F(5N) is always an *odd* multiple of 5 and hence when divided by 5 and by F(N), will always end in 1.

と、いうことで「should not be difficult」。
誰か証明をお願い。^_^;


◆埼玉県 \aleph_0 さんからの解答。

整数nに対してn | Fnとなるための必要十分条件を求めたいと思います。

まず、整数m,nに対して次のことが成り立つことを思い起こしてください。

(1) Fm+n=Fm+1Fn+FmFn-1.

(2) m | n ⇒ Fm | Fn.

証明は、「多項式の列」の問題を参照してください。

次に、任意のi≧0に対して次の等式が成り立つことに注意してください。

(3)

Fmn
=Fn2(F(m-2)n+2+2Fn-1F(m-3)n+2+...+(i-1)Fn-1i-2F(m-i)n+2)+iFnFn-1i-1F(m-i)n+1+Fn-1iF(m-i)n.
これは、iに関する帰納法により(1)を用いて示されます。

(3)でi=mとおけば、m≧0に対して次の等式が成り立つことが分かります。

(4)

Fmn=Fn2(F(m-2)n+2+2Fn-1F(m-3)n+2+...+(m-1)Fn-1m-2)+mFnFn-1m-1.
これより、整数m,n,kに対して次のことが成り立ちます。

(5) m | Fn, k | Fn⇒ mk | Fmn.

さて、整数mに対してρ(m)をm | Fnとなる最小の正の整数nと定義します。

例えば、
ρ(2)=3,ρ(3)=4,ρ(4)=6,ρ(5)=5,
ρ(7)=8,ρ(11)=10,ρ(13)=7です。

奇素数pに対しては、
ρ(p) | ψ(p)=p-(5/p)が成り立つことが知られています。
((a/p)はLegendre記号)

特にp≠5ならば(p=2の場合も含めて)、
 (p,ρ(p))=1が成り立ちます。

一方、整数m,nに対して次のことが成り立ちます。

(6)m | Fn ⇔ ρ(m) | n.

これは、(1)および(2)を用いて容易に示されます。

また、mを整数とするとき、任意のe≧1に対して次のことが成り立ちます。

(7)ρ(me) | me-1ρ(m).

これは、eに関する帰納法により(5)および(6)を用いて示されます。

それでは、いよいよ本題に入ります。

●定理1. 整数nに対して次が成り立つ。

n | Fn ⇔ nの任意の素因数pに対してρ(p) | n.

証明. (→) n | Fnのとき、
p | nならば、p | Fnであるから、
(6)よりρ(p) | n.

(←) nの任意の素巾因数pe (e≧1)に対して、
pe-1 | n, ρ(p) | nであるから、
pe-1ρ(p) | n.

よって、(7)よりρ(pe) | nであるから、
(6)よりpe | Fn.

したがって、n | Fn.


これより、n=2a3b5c
(a≧2,b≧1,c≧0)
およびn=5e (e≧0)は
n | Fnを満たすことが分かります。

ここで前者は12の倍数ですが、逆に次のことが成り立ちます。

○系1. nが偶数のとき、
n | Fnならば、12 | n.

証明. 2 | nであるから、
定理1よりρ(2)=3 | n.

このとき再び定理1より
ρ(3)=4 | n.

したがって、12 | n.


一方、後者は5の巾ですが、それ以外の奇数については次のことが成り立ちます。

○系2. nが5の巾でない奇数のとき、
n | Fnならば、nの5を除く最小の素因数pに対して、
あるe≧2が存在して、
ρ(p)=5e, 5e | n.

証明. p | nであるから、
定理1よりρ(p) | n.

一方、ρ(p) | ψ(p)=p±1であり、
ρ(p)は奇数であるから、ρ(p)<p.

よって、pの最小性より、
あるe≧0が存在してρ(p)=5e.

今e=0,1と仮定すると、それぞれρ(p)=1,5となり矛盾であるから、
e≧2.

またこのときρ(p)=5e | n.


さらに、次のような興味深い結果も得られます。

○系3. 整数nに対して、n | Fnならば、
Fn | FFn.

証明.
n | Fnならば、Fnの任意の素因数pに対して、
(6)よりρ(p) | nであるから、ρ(p) | Fn.

したがって、定理1よりFn | FFn.


では最後に、新たに発見された予想について考えてみましょう。
まず、整数nに対して次の等式が成り立つことに注意してください。

(8)

F5n=5Fn(Fn+14-Fn+13Fn-1+Fn+12Fn-12-Fn+1Fn-13+Fn-14).
これは、(1)を繰り返し適用することにより示されます。
これを用いれば、例の予想が解決します。

●命題1. nを整数とするとき、
Qn=F5n/5Fnの任意の素因数pに対して、
p≡1 (mod 5).

証明. p | Qnならば、有限体 Fpにおいて(以下同じ)、

(9)

Qn=Fn+14-Fn+13Fn-1+Fn+12Fn-12-Fn+1Fn-13+Fn-14=0.
今Fn-1=0と仮定すると、
(9)よりFn+1=0となり、(Fn+1,Fn-1)=1に反するから、
Fn-1≠0.

このとき

(10)
x=-Fn+1Fn-1-1

とおくと、(9)より

(11)
x4+x3+x2+x+1=0.

これよりx5=1となるから、
xの乗法群 Fp*における位数は5の約数。

今x=1と仮定すると、
(11)より5=0となるから、p=5.

このとき(10)より(F5において)
Fn+1+Fn-1=0となり矛盾。

したがって、xの Fp*における位数は5であるから、
5 | p-1、

すなわち、p≡1 (mod 5).


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

フィボナッチ数列を拡張した、
U(0)=0 U(1)=1 U(n+1)=x*U(n)-y*U(n-1)、と言う数列について考える。

便利のため、V(0)=2 , V(1)=x ,
V(n+1)=x*V(n)-y*U(n-1)と言う列を考える。
整数dをd=x2-4yと定義する。

使用した公式集(Paulo Riebenboim著 共立出版「素数の世界」)

pを素数とする。
s≧tのとき、U(s+t)=U(s)*V(t)-yt*U(s-t)

dがpで割り切れないとき、(d/p)=1のとき、U(p-1)≡0 (mod p)
(d/p)=-1のとき、U(p+1)≡0 (mod p)
dがpで割り切れるとき、U(p)≡0 (mod p)

U(m)がptで割り切れるとき、U(p*m)はpt+1で割り切れる。

p≧3または、t≧2のとき、
U(m)がptで割り切れて、pt+1で割り切れない
⇒U(m)がpt+1で割り切れ、pt+2で割り切れない。

U(n)≡0 (mod m)となる最小のnを、ρ(m)と書くことにする。

【命題1】

mがyと互いに素のとき、U(s)≡0 (mod m)ならば sはρ(m)で割り切れる。

【証明】

もし、ρ(m)がsを割り切らないと仮定する。
m=ρ(m)*q+r 、0<r<ρ(m)

qが奇数のとき、
U(m)
=U(ρ(m)* q+1
2
)*V(ρ(m)* q-1
2
+r)-y{ρ(m)*{(q-1)/2}+r}*U(ρ(m)-r)

U(m)とU(ρ(m)* q+1
2
)はmの倍数なので、
y{ρ(m)*{(q-1)/2}+r}*U(ρ(m)-r)がmで割り切れる。

yとmは互いに素なので、U(ρ(m)-r)がmで割り切れる。

ρ(m)-r<ρ(m)だから、ρ(m)の仮定に反する。

qが偶数のとき
U(m)
=U(ρ(m)*( q
2
+1))*V(ρ(m)*( q
2
-1)+r)-y{ρ(m)*{(q-1)/2}+r}*U(ρ(m)-r)

上と同様に、U(2ρ(m)-r)がmで割り切れる事が分かる。
よって、U(2ρ(m)-r)=U(ρ(m))*V(ρ(m)-r)-y(ρ(m)-r)*U(r)

上と同様に、U(r)がmで割り切れる事が分かる。
r<ρ(m)だから、ρ(m)の仮定に反する。

【命題2】

1.

mをyと互いに素な数とする。
m'をmの約数とするとき、ρ(m')もρ(m)の約数である。

【証明】

U(ρ(m))≡0 (mod m')だから命題1より導かれた。

2.

a,bをyと互いに素な自然数とする。
aとbが互いに素ならば、ρ(a*b)=ρ(a)とρ(b)の最小公倍数

【証明】

1.より、ρ(a*b)はρ(a)とρ(b)で割り切れる。
よって、ρ(a*b)はρ(a)とρ(b)の最小公倍数で割り切れる。

ρ(a)とρ(b)の最小公倍数をlとすると、
U(l)≡0 (mod a) U(l)≡0 (mod b)だから、U(l)≡0 (mod a*b)

よって、命題1より、ρ(a*b)は、lを割り切る。
よって、ρ(a*b)=ρ(a)とρ(b)の最小公倍数が示された。

m=Π(pi)(ei)と書くと、

U(n)≡0 (mod m) ⇔ すべてのiで、U(n)≡0 (mod (pi)(ei))と書けること

を利用して解く。

mが素数の冪の場合に帰着できた。
m=peと置ける。

【命題3】

yがpで割り切れるとき ρ(pe)≦e2+e

【証明】

xがpで割り切れないとき、

U(n)
≡x*U(n-1)-y*U(n-2)
≡x*U(n-1)
≡x2*U(n-2)
≡・・・
≡xn-1 (mod p)だから、U(n)はpで割り切れない

xがpで割り切れるとき
e=1 のとき、V(1)≡0
e≧2のとき V(e)≡x*V(e-1)-y*V(e-2)≡0-0≡0 (mod p)

n≧e2+eなる任意のwで

U(n)
=U(n-e)*V(e)-ye*U(n-2e)
≡U(n-e)*V(e)
≡U(n-2*e)*{V(e)}2
≡・・・
≡U(n-e*e)*{V(e)}e
≡0 (mod pe)

ρ(pe)≦e2+eとなる。

pが奇数のとき、

【命題4】

yがpで割り切れないとき、
dがpで割り切れないとき、
(d/p)=1のとき、U(p-1)≡0 (mod p)
(d/p)=-1のとき、U(p+1)≡0 (mod p)

dがpで割り切れるとき、U(p)≡0 (mod p)

よって、(d/p)=1のとき、ρ(p)はp-1の約数
(d/p)=-1のとき、ρ(p)はp+1の約数

dがpで割り切れるとき、ρ(p)=p

【命題5】

yがpで割り切れないとき、
ρ(pe)=pe-e'*ρ(p)
ただしe'は、ρ(pe')=ρ(p) となる、最大の整数

【証明】

U(ρ(pe))がpeで割り切れるならば、
U(p*ρ(pe))はpe+1で割り切れる。

命題1より、p*ρ(pe)はρ(pe+1)で割り切れる。
また命題2より、ρ(pe+1)はρ(pe)で割り切れる。

よって、ρ(pe+1)=p*ρ(pe)または、ρ(pe)である。

ρ(pe+1)≠ρ(pe)と仮定する。
U(ρ(pe))がpeで割り切れて、pe+1で割り切れないとき
U(p*ρ(pe))はpe+1で割り切れて、pe+2で割り切れない。
よって、U(ρ(pe+1))pe+1で割り切れて、pe+2で割り切れない。

ρ(pe+2)≠ρ(pe+1)
よって、e'を、ρ(pe')=ρ(p) となる、最大の整数と仮定して、
ρ(pe)=pe-e'*ρ(p)

p=2のとき、このときyは奇数
xが偶数のとき、ρ(2)=2
xが奇数のとき、ρ(2)=3である。

【命題6】

ρ(4)=ρ(2)のとき、ρ(2e)=2e-e'*ρ(2)
ただしe'は、ρ(2e')=ρ(2) となる、最大の整数

ρ(4)≠ρ(2)のとき、
xが偶数のとき、ρ(2e)=2e
xが奇数のとき、ρ(2e)=2e-e"+1*3
ただし、e"はρ(2e")=ρ(4)となる最大の整数とする。

【証明】

ρ(4)=ρ(2)のとき、e≧2として考えていいので、命題5と同様に考えて、
ρ(2e)=2e-e'*ρ(2) となる。

ρ(4)≠ρ(2)のとき、ρ(4)=2*ρ(2)

xが偶数のとき、V(2)=x2-2y≡2 (mod 4)より、
U(4)=U(2)*V(2)より、U(4)は4で割り切れるが、8で割り切れない。

e≧2のときは、命題5と同様に考えて、
ρ(2e+1)=2*ρ(2e)だから、
ρ(2e)=2e が言えた。

xが奇数のとき、V(3)=x3-3*y≡1-3≡0 (mod 2)よりV(3)は偶数

U(6)=U(3)*V(3)≡0 (mod 4)

e≧2のときは、命題5と同様に考えて、
ρ(2e+1)=2*ρ(2e)だから、
e"はρ(2e")=ρ(4)となる最大の整数として、
ρ(2e)=2e-e"*ρ(4)=2e-e"+1*3

ρ(4)=ρ(2)⇔U(ρ(2))≡0 (mod 4)

xが偶数のとき、x≡0 (mod 4)
xが奇数のとき、x2-y≡0
x2≡1 (mod 4) より y≡1 (mod 4)

まとめると、pをmの任意の素因数、eはその指数とする。

pがyの約数のとき、
xがpで割り切れないとき、ρ(p)は存在しない。

xがpで割り切れるとき、
e2+e以上の数は全部U(n)≡0 (mod pe)となる。

pがyの約数でないとき、
pが奇数のとき、
ρ(pe)=pe-e'*ρ(p)
ただしe'は、ρ(pe')=ρ(p) となる、最大の整数

(d/p)=1のとき、ρ(p)はp-1の約数
(d/p)=-1のとき、ρ(p)はp+1の約数
dがpで割り切れるとき、ρ(p)=p

yが奇数のとき
xが偶数のとき、x≡0 (mod 4)
xが奇数のとき、x2-y≡0 より y≡1 (mod 4)のとき、
ρ(2e)=2e-e'*ρ(2)
ただしe'は、ρ(2e')=ρ(2) となる、最大の整数

xが偶数のとき、x≡2 (mod 4)
xが奇数のとき、x2-y≡0 より y≡3 (mod 4)
xが偶数のとき、ρ(2e)=2e
xが奇数のとき、ρ(2e)=2e-e"+1*3
ただし、e"はρ(2e")=ρ(4)となる最大の整数とする。

【命題7】

U(n)がnで割り切れる

pをnの任意の素因数とすると、
yがpで割り切れないときはρ(p)がnの約数になっている事
yがpで割り切れるときは、xがpで割り切れる。

【証明】

pはU(n)の約数である。
yがpで割り切れないとき、命題1により、ρ(p)がnの約数になっている事がわかる。
yがpで割り切れるときは、xがpで割り切れる事が分かる。
もし割り切らなければ、
U(n)≡x*U(n-1)-y*U(n-2)≡x*U(n-1)≡・・・≡xn-1 (mod p)
U(n)がpを割り切らないことになり、不合理。

逆を示す

yがpで割り切れないとき、pが奇数のとき、
ρ(pe)=pe-e'ρ(p)

ρ(p)≠pのとき、ρ(p)はp±1の約数だから、ρ(p)はpと互いに素
U(N)はpe-e'で割り切れる、
仮定により、nはρ(p)で割り切れる。

U(N)は、pe-e'*ρ(p)=ρ(pe)で割り切れる。

ρ(p)=pのとき、ρ(pe)=pe-e'+1はU(n)の約数である。
pが偶数のとき、yは奇数となる。

ρ(2)=3のとき、
ρ(4)=ρ(2) のとき、U(N)は、2e-e'で割り切れる。

よって、U(N)はρ(2e)=2e-e'*3で割り切れる。

ρ(4)≠ρ(2)のときも同様に示せる。

ρ(2)=3のときは、
ρ(4)=ρ(2) のとき、U(N)は、2e-e'+1で割り切れる。
よって、U(N)はρ(2e)=2e-e'+1で割り切れる。

ρ(4)≠ρ(2)のときも同様に示せる。

yとxをpが割り切るとき、任意の自然数kをとると、
k2+k以上の数は全部U(n)≡0 (mod pk)となる。

明らかに、pk>k2+kだから、
U(pk)≡0 (mod pk)となる。

【実例その1】

d≠±1のとき、pがdの約数とすると、
p1、p2、・・・ph、をdの素因数とする。

f1、f2、f3、・・・、fhを任意の自然数とする

n=(p1)(f1)*(p2)(f2)*・・・*(ph)(fh)も題意を満たす。

p1がyを割り切らないとき、ρ(p1)=p1が、nの約数である。

p1がyを割り切るとき、x2=d+4yより、p1は、xを割り切る。

他の素数でも同様な事が言える。

よって、命題7より、nがU(n)の約数にならねばならない。

【実例その2】

yが6と互いに素のとき、n=2w*3c
wは2以上の自然数、cは自然数

ρ(3)=2または4 だから、ρ(3)はnの約数
ρ(2)=2または3だから、ρ(2)はnの約数、

よって、命題7より、U(n)はnで割り切れる。

元の問題では、実例1が5k 、実例2が、2k*3に対応しています。


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

 数学の部屋へもどる