質問: フィボナッチ数列について。 フィボナッチ数列 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) であることを示してください。 よろしくお願いします。
回答: フィボナッチ数列 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)である n=4 の場合はf[4]=3=4-1=-1(mod3)である n≠4の場合 n は素数である。 n>5とする f(n)=(1/√5)[{(1+√5)/2}^n-{(1-√5)/2}^n] f(n)=(1/√5)[{σ_{k=0~n}(nck)5^(k/2)}/2^n-σ_{k=0~n}{(-1)^k}(nck){5^(k/2)}/2^n] f(n)=σ_{j=0~(n-1)/2}{nc(2j+1)}(5^j)/2^(n-1) f(n)=[σ_{j=0~(n-3)/2}{nc(2j+1)}(5^j)+5^{(n-1)/2}]/2^(n-1) j=0~(n-3)/2に対してnc(2j+1)はnの倍数だから j=0~(n-3)/2に対してnc(2j+1)=0(mod n) だから ς_{j=0~(n-3)/2}{nc(2j+1)}(5^j)=0(mod n) だから ς_{j=0~(n-3)/2}{nc(2j+1)}(5^j)+5^{(n-1)/2}=5^{(n-1)/2}(mod n) だから f(n)=[σ_{j=0~(n-3)/2}{nc(2j+1)}(5^j)+5^{(n-1)/2}]/2^(n-1)=5^{(n-1)/2}/2^(n-1)(mod n) だから f(n)=5^{(n-1)/2}/2^(n-1)(mod n) nは素数で 2