4

[年号遊び] 2020 の倍数であるような Fibonacci 数

286
0
$$$$

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}$

投稿日:20201111

この記事を高評価した人

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

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

バッジはありません。

投稿者

ゆう
ゆう
143
11171
好きな整数は 0, 1, 1, φ, 2, 5, 6, 12, 89 など. || フィボナッチ数列 bot (@Aureus_N) 管理人. || hatena blog || indeterminate equations involving Fibonacci numbers || Disquisitiones Arithmeticae...

コメント

他の人のコメント

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