■記事リスト / ▼下のスレッド
/ ▲上のスレッド
■50674 / 親記事) |
フィボナッチ数列について。
|
□投稿者/ メラゾーム 一般人(1回)-(2021/03/19(Fri) 03:07:39)
| フィボナッチ数列 F[1]=1, F[2]=1, F[n+2]=F[n+1]+F[n] (n≧1) について、 F[n] (n≠5) が素数 ならば F[n] ≡ ±1 (mod n) であることを示してください。 よろしくお願いします。
|
|
|
▽[全レス3件(ResNo.1-3 表示)]
■50884 / ResNo.1) |
Re[1]: フィボナッチ数列について。
|
□投稿者/ WIZ 一般人(8回)-(2021/07/05(Mon) 19:33:43)
| Wikipediaの「フィボナッチ数」や「フィボナッチ素数」を見ると以下の記述があります。 # 若干表現は変更しています。 L(a/p) はルジャンドルの記号とします。
(1) n = 4 の場合を除いて、F[n] がフィボナッチ素数となる n は素数である。 しかし、n が素数でも F[n] が素数になるとは限らない。
(2) p が 2 でも 5 でもない素数のとき、F[p-L(5/p)] は p で割り切れる。
(3) F[n−1]F[n+1]−F[n]^2 = (-1)^n
以下、F[3] = 2 と F[4] = 3 と F[5] = 5 以外のフィボナッチ素数について考察します。
(1)により、自然数 p に対して F[p] が素数ならば p も素数です。 L(5/p) = 1 または L(5/p) = -1 なので、(2)より、F[p-1] または F[p+1] が p で割り切れます。 つまり、F[p-1]F[p+1] は p で割り切れます。よって(3)と p が奇数であることより、 F[p−1]F[p+1]−F[p]^2 = (-1)^p = -1 ⇒ F[p]^2 ≡ 1 (mod p) ⇒ F[p] ≡ ±1 (mod p) となり、題意は肯定的に示されます。 (F[3] = 2 と F[4] = 3 は別途示す必要がありますが、これは目視でわかりますよね。)
スレ主さん(もう見てないと思うけど)も上記程度は分かった上での質問なのかもしれません。 つまり、(1)(2)(3)の証明が分からないということかもしれません。 まあ、(3)は F[n] の一般項の式から容易に導けるのではないかと思います。(確認してないけど) (2)は2次体 Q(√5) の整数環の性質から導けるかも? (希望的観測) (1)は F[n] の一般項の式から導けるかもしれない。(願望)
|
|
|
■50888 / ResNo.2) |
Re[1]: フィボナッチ数列について。
|
□投稿者/ WIZ 一般人(9回)-(2021/07/06(Tue) 21:06:24)
| F[n-1]F[n+1]-F[n]^2 = (-1)^n の証明
n を 2 以上の自然数として G[n] = F[n-1]F[n+1]−F[n]^2 とします。 G[2] = F[1]F[3]−F[2]^2 = 1*2-1^2 = 1 = (-1)^2
k を 2 以上の自然数として G[k] = (-1)^k と仮定します。 G[k+1] = F[k]F[k+2]-F[k+1]^2 = (F[k+1]-F[k-1])(F[k]+F[k+1])-F[k+1]^2 = F[k+1]F[k]+F[k+1]^2-F[k-1]F[k]-F[k-1]F[k+1]-F[k+1]^2 = (F[k+1]-F[k-1])F[k]-F[k-1]F[k+1] = F[k]^2-F[k-1]F[k+1] = -G[k] = (-1)^(k+1)
以上から数学的帰納法により 2 以上の自然数 n に対して G[n] = F[n-1]F[n+1]-F[n]^2 = (-1)^n が成立する。
|
|
|
■50889 / ResNo.3) |
Re[1]: フィボナッチ数列について。
|
□投稿者/ WIZ 一般人(11回)-(2021/07/06(Tue) 23:29:21)
| (A) フィボナッチ数の加法定理 F[m+n] = F[m]F[n+1]+F[m-1]F[n] の証明
m, n は自然数で、m ≧ 2 とする。
m = 2 の場合、F[1] = F[2] = 1 なので、 F[2+n] = F[n+1]+F[n] = F[2]F[n+1]+F[2-1]F[n] となり加法定理は成立する。
m = 3 の場合、F[2] = 1, F[3] = 2 なので、 F[3+n] = F[n+2]+F[n+1] = (F[n+1]+F[n])+F[n+1] = 2F[n+1]+F[n] = F[3]F[n+1]+F[3-1]F[n] となり加法定理は成立する。
k を 3 以上の自然数として、m = k と m = k-1 で加法定理の成立を仮定すると、 F[(k+1)+n] = F[k+n]+F[(k-1)+n] = (F[k]F[n+1]+F[k-1]F[n])+(F[k-1]F[n+1]+F[k-2]F[n]) = (F[k]+F[k-1])F[n+1]+(F[k-1]+F[k-2])F[n] = F[k+1]F[n+1]+F[k]F[n] となり、m = k+1 でも成立する。
以上から、数学的帰納法により 2 以上の自然数 m と 任意の自然数 n に対して、 F[m+n] = F[m]F[n+1]+F[m-1]F[n] が成立する。
(B) フィボナッチ数の整除定理 m | n ならば F[m] | F[n] の証明
n を 2 以上の自然数とすると、加法定理より、 F[n+n] = F[n]F[n+1]+F[n-1]F[n] = F[n](F[n+1]+F[n-1]) つまり、F[n] | F[2n] が成立する。
k を 2 以上の自然数、u を自然数として、F[kn] = u*F[n] を仮定すると、 F[(k+1)n] = F[n]F[kn+1]+F[n-1]F[kn] = F[n]F[kn+1]+F[n-1]*u*F[n] = F[n](F[kn+1]+F[n-1]*u) となり、F[n] | F[(k+1)n] が成立する。
以上から、数学的帰納法により v と n を 2 以上の自然数とするとき F[n] | F[vn] が成立する。 # n = 1 や v = 1 でも上記は成立しますが。
(C) F[p] が素数ならば、p は奇素数であるか 4 であることの証明
3 以上の自然数 a と 2 以上の自然数 b が存在して p = ab ならば、 a < p であり、1 < F[a] < F[p] かつ整除定理より F[a] | F[p] となり F[p] は素数ではありえない。
従って、F[p] が素数となるためには p は真の約数を持たないか、 真の約数の値が 2 以下の場合である。
真の約数を持たないということは、p は素数であるということてある。 但し、F[2] = 1 は素数ではないので、p は奇素数である。 真の約数の値が 2 以下ということは p は 2 の冪であることが必要だが、 2^3 = 8 は 4 という真の約数を持つため、可能性は p = 2^2 のみとなるが、 F[4] = 3 は素数である。
以上から、F[p] が素数ならば、p は奇素数か 4 であるといえる。
|
|
|
■記事リスト /
レス記事表示 →
[親記事-3]
|