フィボナッチ数列について。

Question

フィボナッチ数列 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) であることを示してください。 よろしくお願いします。

mtrajcp · Accepted Answer

フィボナッチ数列
F[1]=1
F[2]=1
F[n+2]=F[n+1]+F[n]
(n≧1)
(n≠5)
 について、
F[n]
を素数とすると
n=3 の場合はF[3]=2=-1(mod3)である
F[3]=2は素数でF[n]=-1(mod n)が成立している
n=4 の場合はF[4]=3=4-1=-1(mod4)である
F[4]=3は素数でF[n]=-1(mod n)が成立している
n≠4の場合
F[n]が素数となる n は素数である。
n>5とする

この続きは画像の方を参照願います

mtrajcp · Answer

2nC(n-2)√5^(n-2) +2nCn√5^n
↓nは素数で奇数だからn=2j+1となる整数jがある
=2nC(n-2)√5^(2j+1-2)+2nCn√5^(2j+1)
=2nC(n-2)√5^(2j-2+1)+2nCn√5^(2j+1)
=2nC(n-2)√5^{2(j-1)+1}+2nCn√5^(2j+1)
=2nC(n-2)(√5^{2(j-1)})√5+2nCn{√5^(2j)}√5
=2nC(n-2){5^(j-1)}√5+2nCn(5^j)√5

n=2j+1
n-1=2j
(n-1)/2=j
だから

=2nC(n-2)5^{(n-1)/2-1}(√5)+2nCn{5^(n-1)/2}√5
=2nC(n-2)5^{(n-1)/2-2/2}√5+2nCn{5^(n-1)/2}√5
=2nC(n-2)5^{(n-3)/2}(√5)  +2nCn{5^(n-1)/2}√5
=2(√5)nC(n-2)5^{(n-3)/2}+2(√5)nCn{5^(n-1)/2}
-----------------------------------
フィボナッチ数列
F[1]=1
F[2]=1
F[n+2]=F[n+1]+F[n]
(n≧1)
(n≠5)
 について、
F[n]
を素数とすると
n=3 の場合はF[3]=2=-1(mod3)である
F[3]=2は素数でF[n]=-1(mod n)が成立している
n=4 の場合はF[4]=3=4-1=-1(mod4)である
F[4]=3は素数でF[n]=-1(mod n)が成立している
n≠4の場合
F[n]が素数となる n は素数である。
n>5とする

F(n)=(1/√5)[{(1+√5)/2}^n-{(1-√5)/2}^n]
とすると

F(1)=(1/√5)[{(1+√5)/2}^1-{(1-√5)/2}^1]=1
F(2)=(1/√5)[{(1+√5)/2}^2-{(1-√5)/2}^2]=1

F(n)+F(n+1)
=(1/√5)[{(1+√5)/2}^n-{(1-√5)/2}^n]+(1/√5)[{(1+√5)/2}^(n+1)-{(1-√5)/2}^(n+1)]
=(1/√5)[{(1+√5)/2}^n{(3+√5)/2}-{(1-√5)/2}^n{(3-√5)/2}]
=(1/√5)[{(1+√5)/2}^(n+2)-{(1-√5)/2}^(n+2)]
=F(n+2)
が成り立つから
F(n)=(1/√5)[{(1+√5)/2}^n-{(1-√5)/2}^n]
はフィボナッチ数列の一般項を表す

F(n)=(1/√5)[{(1+√5)/2}^n-{(1-√5)/2}^n]
F(n)={(1+√5)^n-(1-√5)^n}/{(√5)(2^n)}

(1+√5)^nを2項展開すると
(1+√5)^n=Σ_{k=0～n}(nCk)√5^k
(1+√5)^n=nC0+nC1√5+nC2√5^2+nC3√5^3+…+nC(n-2)√5^(n-2)+nC(n-1)√5^(n-1)+nCn√5^n
(1-√5)^nを2項展開すると(nは素数で奇数だから(-1)^n=-1だから)
(1-√5)^n=Σ_{k=0～n}(-1)^k(nCk)√5^k
(1-√5)^n=nC0-nC1√5+nC2√5^2-nC3√5^3+…-nC(n-2)√5^(n-2)+nC(n-1)√5^(n-1)-nCn√5^n

↓これを(1+√5)^nから引くと

(1+√5)^n-(1-√5)^n
=
+nC0     　　　　-nC0　
+nC1√5  　　　　+nC1√5
+nC2√5^2　　　　-nC2√5^2
+nC3√5^3　　　　+nC3√5^3
+nC4√5^4　　　　-nC4√5^4
+nC5√5^5　　　　+nC5√5^5
+nC6√5^6　　　　-nC6√5^6
+nC7√5^7　　　　+nC7√5^7
…
+nC(n-2)√5^(n-2)+nC(n-2)√5^(n-2)
+nC(n-1)√5^(n-1)-nC(n-1)√5^(n-1)
+nCn√5^n        +nCn√5^n

=
+2nC1√5
+2nC3√5^3
+2nC5√5^5
+2nC7√5^7
…
+2nC(n-2)√5^(n-2)
+2nCn√5^n

=
+2nC1√5
+2nC3√5^(1+2)
+2nC5√5^(1+4)
+2nC7√5^(1+6)
…
+2nC(n-2)√5^(1+n-3)
+2(nCn)√5^(1+n-1)

=
+2nC1√5
+2nC3√5√5^2
+2nC5√5√5^4
+2nC7√5√5^6
…
+2nC(n-2)√5√5^(n-3)
+2(nCn)√5√5^(n-1)

=
+2nC1(√5)
+2nC3(√5){5^(1/2)}^2
+2nC5(√5){5^(1/2)}^4
+2nC7(√5){5^(1/2)}^6
…
+2nC(n-2)(√5){5^(1/2)}^(n-3)
+2(nCn)(√5){5^(1/2)}^(n-1)

=
+2nC1(√5)
+2nC3(√5)*5^(2/2)
+2nC5(√5)*5^(4/2)
+2nC7(√5)*5^(6/2)
…
+2nC(n-2)(√5)*5^{(n-3)/2}
+2(nCn)(√5)*5^{(n-1)/2}

=
+(2√5)(nC1)
+(2√5)(nC3)*5
+(2√5)(nC5)*5^2
+(2√5)(nC7)*5^3
…
+(2√5){nC(n-2)}*5^{(n-3)/2}
+(2√5)(nCn)*5^{(n-1)/2}

(1+√5)^n-(1-√5)^n
=
+(2√5)(nC1)
+(2√5)(nC3)*5
+(2√5)(nC5)*5^2
+(2√5)(nC7)*5^3
…
+(2√5){nC(n-2)}*5^{(n-3)/2}
+(2√5)(nCn)*5^{(n-1)/2}

↓両辺を(2^n)√5で割ると

{(1+√5)^n-(1-√5)^n}/{(2^n)√5}
=
[
+(nC1)
+(nC3)*5
+(nC5)*5^2
+(nC7)*5^3
…
+{nC(n-2)}*5^{(n-3)/2}
+(nCn)*5^{(n-1)/2}
]
/2^(n-1)

↓F(n)={(1+√5)^n-(1-√5)^n}/{(2^n)√5}だから

F(n)=[nC1+nC3*5+nC5*5^2+nC7*5^3+…+nC(n-2)5^{(n-3)/2}+nCn5^{(n-1)/2}]/2^(n-1)
↓両辺に2^(n-1)をかけると
2^(n-1)F(n)=nC1+nC3*5+nC5*5^2+nC7*5^3+…+nC(n-2)5^{(n-3)/2}+nCn5^{(n-1)/2}

1≦k≦n-2 となる自然数kに対して
k≦n-2<n

1≦k
n-k≦n-1<n

nCk=n!/{k!(n-k)!}

nは素数で
nより小さいnの正の倍数は存在しないから
k<nだからk!の素因数にはnは無い
n-k<nだから(n-k)!の素因数にはnは無い
k!(n-k)!の素因数にはnは無い
だから
nはk!(n-k)!で約分できないから

1≦k≦n-2 となる自然数kに対して
nCkはnの倍数となるから

nC1,nC3,nC5,nC7,…,nC(n-2)はnの倍数だから

nC1=nC3=nC5=nC7=…=nC(n-2)=0(mod n)
だから
nC1+nC3*5+nC5*5^2+nC7*5^3+…+nC(n-2)5^{(n-3)/2}=0(mod n)
だから
nC1+nC3*5+nC5*5^2+nC7*5^3+…+nC(n-2)5^{(n-3)/2}+5^{(n-1)/2}=5^{(n-1)/2}(mod n)
だから
2^(n-1)F(n)=nC1+nC3*5+nC5*5^2+nC7*5^3+…+nC(n-2)5^{(n-3)/2}+5^{(n-1)/2}=5^{(n-1)/2}(mod n)
だから
2^(n-1)F(n)=5^{(n-1)/2}(mod n)

nは素数で
2<nと2は互いに素だから
フェルマーの小定理から
2^(n-1)=1(mod n)
だから
2^(n-1)-1=0(mod n)
だから
{2^(n-1)-1}F(n)=0(mod n)
2^(n-1)F(n)-F(n)=0(mod n)
2^(n-1)F(n)=F(n)(mod n)

↓2^(n-1)F(n)=5^{(n-1)/2}(mod n)だから

F(n)=5^{(n-1)/2}(mod n)

nは素数で
5<nと5は互いに素で
フェルマーの小定理から
5^(n-1)=1(mod n)
だから
(5^{(n-1)/2})^2=5^(n-1)=1(mod n)
(5^{(n-1)/2})^2=1(mod n)
(5^{(n-1)/2})^2-1=0(mod n)
(5^{(n-1)/2}+1)(5^{(n-1)/2}-1)=0(mod n)
↓nは素数だから
5^{(n-1)/2}+1=0(mod n).or.5^{(n-1)/2}-1=0(mod n)
だから
5^{(n-1)/2}=±1(mod n)
だから
F(n)=5^{(n-1)/2}(mod n)=±1(mod n)
∴
F(n)=±1(mod n)

mtrajcp · Answer