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

フィボナッチ数,FibonacciNumber,2020年

286

2020 の倍数であるような Fibonacci 数
前提知識 : Fibonacci 数列, 三項間漸化式の解法, Fermat の小定理
Fibonacci 数列 : https://mathlog.info/articles/191
$.$
$.$
$.$
$.$
$.$
$.$

前置き

加法定理

任意の正整数 $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$ の場合が得られるので, 再帰的に命題は示された. $◻$

任意の正整数 $n, k$ に対して, $F_{n} ∣ F_{k n}$ が成りたつ.

上記の加法定理において $m = n$ を代入すると
$\begin{array}{r} F_{2 n} = F_{n} F_{n + 1} + F_{n - 1} F_{n} \end{array}$ と成るため, $F_{2 n}$ は $F_{n}$ の倍数である. 続いて $m = 2 n$ とすれば
$\begin{array}{r} F_{3 n} = F_{2 n} F_{n + 1} + F_{2 n - 1} F_{n} \end{array}$ を得るから, $F_{3 n}$ が $F_{n}$ の倍数であることも判り, その他についても同様に進めることができる.

$k = 1$ のときは正しく, 一般に, ある正なる $k$ において $F_{n} ∣ F_{k n}$ なることを仮定すれば
$\begin{array}{r} F_{(k + 1) n} = F_{k n + n} = F_{k n} F_{n + 1} + F_{k n - 1} F_{n} \end{array}$ によって, 右辺の $F_{k n}, F_{n}$ の $F_{n}$ による整除性は左辺にも移り $F_{n} ∣ F_{(k + 1) n}$ が導かれる. よって, 再帰的に命題は示された. $◻$

$.$
$.$
$.$
$.$
$.$
$.$

証明

先の命題から, 若し $a ∣ F_{m}$ かつ $b ∣ F_{n}$ が成りたつのならば, $(a, b)$ の最小公倍数を $ℓ$ として
$\begin{array}{r} a b ∣ F_{ℓ} \end{array}$ も真と成ることが判り, $2020$ の倍数であるような Fibonacci 数を考えるには
$\begin{array}{r} 2020 = 4 \cdot 5 \cdot 101 \end{array}$ と素数冪に分解して, 各々の倍数であるような Fibonacci 数を一つ構成すれば良い.
$.$
$.$
$.$

$4$ の倍数

値の小さい範囲で $4 ∣ F_{6} = 8$ などが見つかる.
$.$
$.$
$.$

$5$ の倍数

値の小さい範囲で $5 ∣ F_{5} = 5$ などが見つかる.
$.$
$.$
$.$

$101$ の倍数

一般に, $p \equiv 1, 4 (m o d 5)$ なる素数 $p$ に対して $F_{p - 1}$ は $p$ で割りきれ,
$\begin{array}{r} 101 ∣ F_{100} \end{array}$ も成立する. 以下では, $p = 101$ なる特別な場合においてこれを証明する.

$r = 45$ ならば, $r^{2} \equiv 5 (m o d 101)$ が成りたつ.

この命題から, 整数 $45$ は $m o d 101$ において $5$ の平方根の代わりを為す数と見ることができよう.

$r^{2} = 2025$ から自明. $◻$

任意の正整数 $n$ に対して,
$\begin{array}{r} f_{n} = \frac{{(\frac{1 + r}{2})}^{n} - {(\frac{1 - r}{2})}^{n}}{r} = \frac{23^{n} - (- 22)^{n}}{45} \end{array}$ なる $f_{n}$ は整数であり, $F_{n} \equiv f_{n} (m o d 101)$ が成りたつ.

$f_{n}$ が整数であることは
$\begin{array}{r} 23^{n} - (- 22)^{n} \equiv 23^{n} - 23^{n} \equiv 0 (m o d 45) \end{array}$ から直ちに従う.

$101$ を法として
$\begin{aligned} 23 + (- 22) \equiv 1, \\ 23 \cdot (- 22) \equiv - 1 \end{aligned}$ が成りたつので, 漸化式 $F_{n + 2} = F_{n + 1} + F_{n}$ は
$\begin{aligned} F_{n + 2} - 23 F_{n + 1} \equiv - 22 (F_{n + 1} - 23 F_{n}) \end{aligned}$ あるいは
$\begin{aligned} F_{n + 2} + 22 F_{n + 1} \equiv 23 (F_{n + 1} + 22 F_{n}) \end{aligned}$ と変形することができ, これを繰りかえして適用すれば
$\begin{aligned} F_{n + 1} - 23 F_{n} \equiv (- 22)^{n} (F_{1} - 23 F_{0}) \equiv (- 22)^{n}, \\ F_{n + 1} + 22 F_{n} \equiv 23^{n} (F_{1} + 22 F_{0}) \equiv 23^{n} \end{aligned}$ なる二式を得, 第二式から第一式を引けば $F_{n} \equiv f_{n}$ と成る. $◻$

$101 ∣ F_{100}$ が成りたつ.

補題と Fermat の小定理によれば, $101$ を法として
$\begin{array}{r} 45 F_{100} \equiv 22^{100} - (- 23)^{100} \equiv 1 - 1 \equiv 0 \end{array}$ が成りたち, 法 $101$ が $45$ と互いに素であることから $101 ∣ F_{100}$ である. $◻$

尚, $p \equiv 2, 3 (m o d 5)$ なる素数 $p$ に対しては $p ∣ F_{p + 1}$ が成りたつ.

参考 : ブログ記事 ( https://yu200489144.hatenablog.com/entry/2020/05/16/211327 )
$.$
$.$
$.$

$2020$ の倍数

以上にて見つけた番号の組 $(6, 5, 100)$ の最小公倍数は $300$ であるから, 次の関係が得られる.

$2020 ∣ F_{300}$ が成りたつ.

因みに, 正整数 $i$ で $2020 ∣ F_{i}$ を満足するものの内, 最小であるのは $i = 150$ である.
$.$
$.$
$.$
$.$
$.$
$.$

投稿日：2020年11月11日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

150

13522

好きな整数は 0, 1, 1, φ, 2, 5, 6, 12, 89 など. || フィボナッチ数列 bot (@Aureus_N) 管理人. || hatena blog

他の人のコメント

コメントはありません。

読み込み中

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

前置き
証明
$4$ の倍数
$5$ の倍数
$101$ の倍数
$2020$ の倍数

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

前置き

証明

4の倍数

5の倍数

101の倍数

2020の倍数

この記事を高評価した人

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

投稿者

コメント

他の人のコメント

$4$ の倍数

$5$ の倍数

$101$ の倍数

$2020$ の倍数