7

フィボナッチ数列の研究まとめ 3

796
1
$$\newcommand{fib}[0]{\mathbb{F}} \newcommand{Fib}[0]{\mathbb{\overline{F}}} \newcommand{leg}[2]{\left(\dfrac{#1}{#2}\right)} \newcommand{P}[0]{\mathbb{P}} \newcommand{pre}[0]{\mathrm{pre}} \newcommand{Pre}[0]{\mathrm{Pre}} \newcommand{suc}[0]{\mathrm{suc}} \newcommand{Suc}[0]{\mathrm{Suc}} \newcommand{Z}[0]{\mathbb{Z}} $$

前回の記事では$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]の値 $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]$での議論などをすればもっと簡単に示せるかもしれないですが, 初等整数論でもここまでできます. 次回は指数を含む不定方程式とフィボナッチ数列の関係か, 群論と合わせたもっと踏み込んだ話かどちらかを書く気がします. それではまた次回!

投稿日:2022112
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

りぼーす
りぼーす
139
26783

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中