フィボナッチ数列の研究まとめ 3
前回の記事では$L(n)/l(n)$が$1,2,4$のいずれかになるということを示しました. 今回は, $n$が素数の場合$1,2,4$のどれになるかということが$\bmod{20}$でほとんどの場合決定できることを示します.
- 数2Bまでの知識
- 集合, 写像についての記法, 用語が一通りわかる
- 群論について基本的なことがわかる(わからなくても一部証明以外は読めます)
- 平方剰余の議論に慣れていると楽に読める(基本的な内容には触れます)
また, 前回の記事 を先に読むことを推奨します.
前回までのまとめ
数列$\{F_n\}^\infty_{n=-\infty}$を$F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$$(n\in\Z)$で定め, フィボナッチ数列と呼ぶ. この集合に登場する整数をフィボナッチ数と呼ぶ.
任意の$n,m\in\Z$に対し$F_{n+m+1}=F_nF_m+F_{n+1}F_{m+1}$が成立する.
任意の$n,m\in\Z$に対し$F_{n+m}F_{n-m}=F_n^2-(-1)^{n+m}F_m^2$が成立する.
正整数$n$に対して関数$l, L:\Z_{>0}\rightarrow\Z_{>0}$を以下のように定める:
$$l(n)=\min\{k\in\Z_{>0}\mid F_k\equiv0\pmod n\}$$
$$L(n)=\min\{k\in\Z_{>0}\mid F_k\equiv0\pmod n\land F_{k+1}\equiv1\pmod n\}$$
これらはそれぞれ, フィボナッチ数を$n$で割った余りを考えたときに何個周期で$0$が出てくるか, 何個周期で余りが循環するか, ということを表しています( 前回の記事 参照).
任意の正整数$n$に対して$L(n)/l(n)$の値は$1,2,4$のいずれかになる.
今回の話の準備
主定理の主張
まず, 今回示したいのは以下の主張です.
$2$と$5$を除く任意の素数$p$に対して$L(p)/l(p)$の値は以下の表のようになる. ここで, $\bmod{20}$で$1$と$9$の場合は$\bmod20$の情報のみでは特定できない.
![!FORMULA[29][-498813063][0]の値](https://firebasestorage.googleapis.com/v0/b/mathlog-361213.appspot.com/o/uploads%2Fmathdown%2F20221102132522.jpg?alt=media)
$L(p)/l(p)$の値
$\bmod{20}$で$1$と$9$の場合はほかの$\bmod$で特定できるのかと思ったのですが, $\bmod40$で少し情報を得られるのみでした. この内容を初等整数論の内容のみで示していきます.
平方剰余について
奇素数$p$, $p$と互いに素な整数$a$に対してルジャンドル記号$\leg{a}{p}$を以下のように定める:
- $n^2\equiv a \pmod{p}$となる整数$n$が存在するとき$\leg{a}{p}=1$
- $n^2\equiv a \pmod{p}$となる整数$n$が存在しないとき$\leg{a}{p}=-1$
このとき, 有名事実として以下を認めます.
$p, q$を相異なる奇素数, $a, b$を$p$と互いに素な整数とする. このとき, 以下が成立する.
- $\leg{ab}{p}=\leg{a}{p}\leg{b}{p}$(ここでは積の法則と呼ぶ)
- $p\equiv1\pmod4$のとき$\leg{-1}4=1$, $p\equiv3\pmod4$のとき$\leg{-1}4=-1$(第一補充則)
- $\leg pq\leg qp=(-1)^{\frac{p-1}2\frac{q-1}2}$(相互法則)
補題の証明
主定理を示すために, $4$つの補題を示していきます. 以下, $p$は$5$でない奇素数とします.
$\leg{-1}p=-1$のとき$l(p)$は偶数.
$F_{2k+1}\equiv0\pmod p$とする. このとき, 乗法定理で$(n,m)=(2k,1)$とすることで$F_n^2\equiv-1$となり, 矛盾.
$L(p)/l(p)=1,2\Leftrightarrow l(p)$が偶数 が成立.
$\Rightarrow)$$l(p)$が奇数であるとき, 乗法定理で$(n,m)=(l(p)+1,1)$とすれば, $F_{l(p)}\equiv0\pmod p$から$F_{l(p)+1}^2\equiv -1$である. 前回の議論より$F_{l(p)+1}$は$G_{Fi}(p)$の生成元なので$G_{Fi}(p)\cong C_4$である. 前回の主定理より対偶を取れば示された.
$\Leftarrow)$$l(p)$が偶数のとき上と同様に$F_{l(p)+1}^2\equiv 1$であるので, $G_{Fi}(p)\cong E, C_2$であり示された.
$\leg5p=-1$かつ$l(p)$が偶数のとき$L(p)/l(p)\neq1$
以下合同式の法は$p$とする. $2k=l(p)$とおけば加法定理より
$$F_{2k}=F_{k}F_{k-1}+F_{k}F_{k+1}=F_k(F_{k-1}+F_{k+1})$$
今, $F_{2k}\equiv0$であり, $l(p)$は$F_n\equiv0$なる最小の正整数$n$なので$F_k\not\equiv0$. すなわち, $F_{k-1}+F_{k+1}\equiv0, F_{k-1}\equiv-F_{k+1}$
再び加法定理より
$$F_{2k+1}=F_k^2+F_{k+1}^2=(F_{k+1}-F_{k-1})^2+F_{k+1}^2$$
$F_{k-1}\equiv-F_{k+1}$を代入することで$F_{2k+1}\equiv5F_{k+1}^2$となる.
ここで, 平方剰余の積の法則より
$$\leg{F_{2k+1}}{p}=\leg5p\leg{F_{k+1}^2}{p}=\leg5p=-1$$
従って, $F_{2k+1}\neq1$. 従って, $G_{Fi}(p)$の生成元$F_{2k+1}$は単位元でないので, $L(p)/l(p)\neq1$である.
$\leg{-5}p=-1$かつ$l(p)$が偶数のとき$L(p)/l(p)\neq2$
先の補題と同様に文字を置けば$F_{2k+1}\equiv5F_{k+1}^2$となる.
ここで, 平方剰余の積の法則より
$$\leg{-F_{2k+1}}{p}=\leg{-5}p\leg{F_{k+1}^2}{p}=\leg{-5}p=-1$$
従って, $F_{2k+1}\neq-1$. 従って, $G_{Fi}(p)$の生成元$F_{2k+1}$は$-1$でないので, $L(p)/l(p)\neq2$である.
主定理の証明
$p\equiv3\pmod4, p\equiv1,4\pmod5$の場合
積の法則, 相互法則, 第一補充則より$\leg{-1}p=-1, \leg5p=1, \leg{-5}p=-1$に気を付けると, 補題6, 7($\Leftarrow$), 9より$L(p)/l(p)=1$である.
$p\equiv3\pmod4, p\equiv2,3\pmod5$の場合
相互法則, 第一補充則より$\leg{-1}p=-1, \leg5p=-1$に気を付けると, 補題6, 7($\Leftarrow$), 8より$L(p)/l(p)=2$である.
$p\equiv1\pmod4, p\equiv2,3\pmod5$の場合
積の法則, 相互法則, 第一補充則より$\leg{-1}p=1, \leg5p=-1, \leg{-5}p=-1$に気を付けると, 補題7($\Rightarrow$の対偶)より$l(p)$が奇数のとき$L(p)/l(p)=4$であり, 補題8, 9より$l(p)$が偶数のときも$L(p)/l(p)=4$である. なお, 実際は補題7($\Leftarrow$の対偶)より$l(p)$は奇数である.
以上で, 主定理の証明ができました. お疲れ様でした.
おまけ
主定理の主張を書いたときに?部分について$\bmod40$で少しわかるという話をしたので, それについて書きます.
$p\equiv5\pmod8, p\equiv1,4\pmod5$のとき$L(p)/l(p)$は$2$になり得ない.
以下合同式の法は$p$とする.
$\leg5p=1$であるので, $\alpha^2\equiv5$なる$\alpha$を取ることができる. また, $\phi\equiv\dfrac{1+\alpha}2$とおけば, フィボナッチ数の一般項について$F_n\equiv\dfrac1\alpha(\phi^n-(-1)^n\phi^{-n})$が成立する.
さて, $L(p)/l(p)=2$と仮定すると補題7($\Rightarrow$)より$l(n)=2M$なる正の整数$M$を取ることができる. ここで, フェルマーの小定理より$L(n)|p-1$であることに気を付ければ$4M|p-1$である. 従って, $M$が偶数であることを示して矛盾を導けばよい.
$$0\equiv F_{2M}\equiv\dfrac1\alpha(\phi^{2M}-\phi^{-2M})$$
より$\phi^{2M}-\phi^{-2M}\equiv0, \phi^{4M}=1, \phi^{2M}=\pm1$である.
ここで, $\phi^{2M}=1$であると仮定すると, $F_{2M+1}\equiv-1$について
$$-1\equiv F_{2M+1}\equiv\dfrac1\alpha(\phi^{2M+1}+\phi^{-2M-1})
=\dfrac1\alpha(\phi+\phi^{-1})=1$$
であるので矛盾. よって, $\phi^{2M}=-1$, すなわち$\phi^{M}=-\phi^{-M}$である. 今, $F_M$について
$$F_M\equiv\dfrac1\alpha(\phi^M-(-1)^M\phi^{-M})=\dfrac1\alpha(1+(-1)^M)\phi^M$$
が成立する. $l(p)$の最小性よりこれは$0$ではないので$M$は偶数になる. よって, $4M|p-1$とあわせ$8|p-1$となるが, これは仮定に矛盾.
おわりに
最後まで読んでいただきありがとうございます. $\Z[\phi]$での議論などをすればもっと簡単に示せるかもしれないですが, 初等整数論でもここまでできます. 次回は指数を含む不定方程式とフィボナッチ数列の関係か, 群論と合わせたもっと踏み込んだ話かどちらかを書く気がします. それではまた次回！
この記事を高評価した人
この記事に送られたバッジ
投稿者
