n²がn番目のフィボナッチ数を割り切るn

フィボナッチ数

1014

お久しぶりです. 今回はタイトルの通り $n^{2}$ が $F_{n}$ ( $n$ 番目のフィボナッチ数)を割り切る正整数 $n$ を全て求めたいと思います. 前提知識は特にありませんが, 前回までの結果を使います.

使うかもしれない色々

前回の記事

フィボナッチ数列

数列 ${F_{n}}_{n = - \infty}^{\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_{n} F_{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}$ が成立する.

周期について

$p \neq 5$ は素数.
$p \equiv 1, 4 (\mod 5)$ のとき $p | F_{p - 1}$
$p \equiv 2, 3 (\mod 5)$ のとき $p | F_{p + 1}$

定理

$n^{2}$ が $F_{n}$ を割り切る正整数 $n$ は $1, 12$ のみである.

証明

前回の結果で $p \neq 5$ は $F_{p \pm 1}$ を割り切るというのがあったので添え字と $p$ の $1$ のずれをうまくマスターデーモンみたいに生かせそうです.

$n = 1$ はok, $n > 2$ とし, $p$ を $n$ の最小の素因数とする.

$p \equiv 1, 4 (\mod 5)$ のとき
$p | F_{n}$ かつ $p | F_{p - 1}$ より $p | F_{gcd (n, p - 1)}$ である(零点の周期性より). $p$ の最小性より $F_{gcd (n, p - 1)} = F_{1} = 1$ なので不適.
$p \equiv 2, 3 (\mod 5)$ のとき
$p | F_{n}$ かつ $p | F_{p + 1}$ より $p | F_{gcd (n, p + 1)}$ である. $p$ が奇素数のとき, その最小性より $gcd (n, p + 1)$ は $1$ である. $p = 2$ のとき, $gcd (n, p + 1)$ は $1$ か $3$ である. よって, $p = 2$ かつ $3 | n$ がわかる. この場合はあとで考える.

また, $p = 5$ のとき $p | F_{n}$ に留意する.

マスターデーモンの手法を踏襲すれば, 次は $F_{n}$ が $p$ で割り切れる回数を評価したいです.

LTEの類似

素数 $p$ のオーダーを $v_{p}$ で書く.
$v_{2} (F_{n}) = {\begin{cases} 2 + v_{2} (n) & n \equiv 0 (\mod 6) \\ 1 & n \equiv 3 (\mod 6) \\ 0 & otherwise \end{cases}$

$v_{3} (F_{n}) = {\begin{cases} 1 + v_{3} (n) & n \equiv 0 (\mod 4) \\ 0 & otherwise \end{cases}$

$v_{5} (F_{n}) = v_{5} (n)$
が成立する.

じゅんにーさんの記事がそのまま適用できます. が, 式をこねくり回してもできるので書き留めておきます.
方針としては, $F_{k n}$ をフィボナッチ数の公式で $F_{n}$ と $F_{n - 1}$ の式にするというものです.

$p = 2$
$n ≢ 0 (\mod 6)$ の場合は明らか. $F_{2 n} = F_{n} (F_{n + 1} + F_{n - 1})$ であり, $v_{2} (F_{n + 1} + F_{n - 1}) = {\begin{cases} 1 & n \equiv 0 (\mod 6) \\ 2 & n \equiv 3 (\mod 6) \end{cases}$ であることが $mod 8$ でわかるのでよい.
$p = 3$
$n ≢ 0 (\mod 4), n ≢ 0 (\mod 3)$ の場合は明らか. $n$ が偶数のとき, 以下が成立する.
$F_{3 n} F_{n} = F_{2 n}^{2} - F_{n}^{2} = F_{n}^{2} ((F_{n + 1} + F_{n - 1})^{2} - 1)$
$mod 9$ で頑張ると, $4 | n$ のとき $v_{3} ((F_{n + 1} + F_{n - 1})^{2} - 1) = 1$ なので示された.
$p = 5$
$F_{5 n} F_{n} = F_{3 n}^{2} - (- 1)^{n} F_{2 n}^{2} = (F_{2 n}^{2} - (- 1)^{n} F_{n}^{2})^{2} - (- 1)^{n} F_{2 n}^{2}$
$S_{n} := F_{n + 1} + F_{n - 1} = \frac{F_{2 n}}{F_{n}} = F_{n} + 2 F_{n - 1}$ とおくと,
$\begin{aligned} F_{5 n} F_{n} \\ = & (F_{2 n}^{2} - (- 1)^{n} F_{n}^{2})^{2} - (- 1)^{n} F_{2 n}^{2} \\ = & (F_{n}^{2} S_{n}^{2} - (- 1)^{n} F_{n}^{2})^{2} - (- 1)^{n} F_{n}^{2} S_{n}^{2} \\ = & F_{n}^{2} ((S_{n}^{2} - (- 1)^{n})^{2} - (- 1)^{n} S_{n}^{2}) \\ = & F_{n}^{2} (S_{n}^{4} - 3 (- 1)^{n} S_{n}^{2} + 1) \end{aligned}$
であり, $S_{n} = 5 n + k$ のように置いて頑張ると $S_{n}^{4} - 3 (- 1)^{n} S_{n}^{2} + 1 \equiv 5 (\mod 25)$ なので示された.

正直かなり結果論的な手法なのでじゅんにーさんの記事を参照することをお勧めします.

先ほどの $2$ パターンをつぶしていきます.

$p = 5$ の場合

$v_{5} (n) = v_{5} (F_{n}) \geq 2 v_{5} (n)$ より $v_{5} (n) = 0$ ,これは不適.

$p = 2$ の場合

$2 | F_{n}$ なので $3 | n$ であり, このとき $3 | F_{n}$ より $4 | n$ である. すなわち $12 | F_{n}$ である. $v_{2} (F_{n})$ を考えよう.
補題より
$2 + v_{2} (n) = v_{2} (F_{n}) \geq 2 v_{2} (n)$ より $v_{2} (n) \leq 2$ なので, $v_{2} (n) = 2$
$1 + v_{3} (n) = v_{3} (F_{n}) \geq 2 v_{3} (n)$ より $v_{3} (n) \leq 1$ なので, $v_{3} (n) = 1$
ここで, $5 | n$ の場合は上と同じ議論で不適であるので, $7$ 以上の素数で $n$ を割り切るものが存在したとし, 最小のものを $p$ とおく. このとき, $p | F_{gcd (n, p \pm 1)}$ である. $p$ の最小性より $gcd (n, p \pm 1)$ は高々 $12$ であるが, このとき $p | 144$ となり $p \geq 7$ に矛盾.
$n = 12$ は条件を満たす.