[年号遊び] 2020 の倍数であるような Fibonacci 数
2020 の倍数であるような Fibonacci 数
前提知識 : Fibonacci 数列, 三項間漸化式の解法, Fermat の小定理
Fibonacci 数列 :
https://mathlog.info/articles/191
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
前置き
任意の正整数$m,n$に対して, $F_{m+n}=F_{m}F_{n+1}+F_{m-1}F_n$が成りたつ.
$m$を固定し, $n$に関する再帰性を用いる. $n\in\{1,2\}$のときは正しい. ある$n+1,n$について等式が成りたつならば, それらを辺々足しあわせることで$n+2$の場合が得られるので, 再帰的に命題は示された. $\quad\Box$
任意の正整数$n,k$に対して, $F_n\mid F_{kn}$が成りたつ.
上記の加法定理において$m=n$を代入すると
$$
\begin{align}
F_{2n}=F_{n}F_{n+1}+F_{n-1}F_n
\end{align}
$$と成るため, $F_{2n}$は$F_n$の倍数である. 続いて$m=2n$とすれば
$$
\begin{align}
F_{3n}=F_{2n}F_{n+1}+F_{2n-1}F_n
\end{align}
$$を得るから, $F_{3n}$が$F_n$の倍数であることも判り, その他についても同様に進めることができる.
$k=1$のときは正しく, 一般に, ある正なる$k$において$F_n\mid F_{kn}$なることを仮定すれば
$$
\begin{align}
F_{(k+1)n}=F_{kn+n}=F_{kn}F_{n+1}+F_{kn-1}F_n
\end{align}
$$によって, 右辺の$F_{kn},F_n$の$F_n$による整除性は左辺にも移り$F_n\mid F_{(k+1)n}$が導かれる. よって, 再帰的に命題は示された. $\quad\Box$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
証明
先の命題から, 若し$a\mid F_m$かつ$b\mid F_n$が成りたつのならば, $(a,b)$の最小公倍数を$\ell$として
$$
\begin{align}
ab\mid F_{\ell}
\end{align}
$$も真と成ることが判り, $2020$の倍数であるような Fibonacci 数を考えるには
$$
\begin{align}
2020=4\cdot5\cdot101
\end{align}
$$と素数冪に分解して, 各々の倍数であるような Fibonacci 数を一つ構成すれば良い.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$4$の倍数
値の小さい範囲で$4\mid F_6=8$などが見つかる.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$5$の倍数
値の小さい範囲で$5\mid F_5=5$などが見つかる.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$101$の倍数
一般に, $p\equiv1,4\ \ ({\rm mod}\ 5)$なる素数$p$に対して$F_{p-1}$は$p$で割りきれ,
$$
\begin{align}
101\mid F_{100}
\end{align}
$$も成立する. 以下では, $p=101$なる特別な場合においてこれを証明する.
$r=45$ならば, $r^2\equiv5\ \ ({\rm mod}\ 101)$が成りたつ.
この命題から, 整数$45$は${\rm mod}\ 101$において$5$の平方根の代わりを為す数と見ることができよう.
$r^2=2025$から自明. $\quad\Box$
任意の正整数$n$に対して,
$$
\begin{align}
f_n=\frac{\displaystyle\left(\frac{1+r}{2}\right)^n-\left(\frac{1-r}{2}\right)^n}{r}=\frac{23^n-(-22)^n}{45}
\end{align}
$$なる$f_n$は整数であり, $F_n\equiv f_n\ \ ({\rm mod}\ 101)$が成りたつ.
$f_n$が整数であることは
$$
\begin{align}
23^n-(-22)^n\equiv23^n-23^n\equiv0\ \ ({\rm mod}\ 45)
\end{align}
$$から直ちに従う.
$101$を法として
$$
\begin{align}
&23+(-22)\equiv1,\ \\
&23\cdot(-22)\equiv-1
\end{align}
$$が成りたつので, 漸化式$F_{n+2}=F_{n+1}+F_n$は
$$
\begin{align}
&F_{n+2}-23F_{n+1}\equiv-22(F_{n+1}-23F_n)
\end{align}
$$あるいは
$$
\begin{align}
&F_{n+2}+22F_{n+1}\equiv23(F_{n+1}+22F_n)
\end{align}
$$と変形することができ, これを繰りかえして適用すれば
$$
\begin{align}
&F_{n+1}-23F_n\equiv(-22)^n(F_1-23F_0)\equiv(-22)^n,\\
&F_{n+1}+22F_n\equiv23^n(F_1+22F_0)\equiv23^n
\end{align}
$$なる二式を得, 第二式から第一式を引けば$F_n\equiv f_n$と成る. $\quad\Box$
$101\mid F_{100}$が成りたつ.
補題と Fermat の小定理によれば, $101$を法として
$$
\begin{align}
45F_{100}\equiv22^{100}-(-23)^{100}\equiv1-1\equiv0
\end{align}
$$が成りたち, 法$101$が$45$と互いに素であることから$101\mid F_{100}$である. $\quad\Box$
尚, $p\equiv2,3\ \ ({\rm mod}\ 5)$なる素数$p$に対しては$p\mid F_{p+1}$が成りたつ.
参考 : ブログ記事 (
https://yu200489144.hatenablog.com/entry/2020/05/16/211327
)
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$2020$の倍数
以上にて見つけた番号の組$(6,5,100)$の最小公倍数は$300$であるから, 次の関係が得られる.
$2020\mid F_{300}$が成りたつ.
因みに, 正整数$i$で$2020\mid F_i$を満足するものの内, 最小であるのは$i=150$である.
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
この記事を高評価した人
この記事に送られたバッジ
投稿者
