7
競技数学解説
文献あり

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

796
0
$$\newcommand{Z}[0]{\mathbb{Z}} $$

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

使うかもしれない色々

前回の記事

フィボナッチ数列

数列$\{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$が成立する.

周期について

$p\neq5$は素数.
$p\equiv1, 4\pmod5$のとき$p|F_{p-1}$
$p\equiv2, 3\pmod5$のとき$p|F_{p+1}$

定理

$n^2$$F_n$を割り切る正整数$n$$1, 12$のみである.

証明

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

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

  • $p\equiv1, 4\pmod5$のとき
    $p|F_n$かつ$p|F_{p-1}$より$p|F_{\gcd(n, p-1)}$である(零点の周期性より). $p$の最小性より$F_{\gcd(n, p-1)}=F_1=1$なので不適.

  • $p\equiv2, 3\pmod5$のとき
    $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)= \left\{ \begin{array}{ll} 2+v_2(n) & n\equiv0\pmod6\\ 1 & n\equiv3\pmod6 \\ 0 & \text{otherwise} \end{array} \right.$

$v_3(F_n)= \left\{ \begin{array}{ll} 1+v_3(n) & n\equiv0\pmod4 \\ 0 & \text{otherwise} \end{array} \right.$

$v_5(F_n)=v_5(n)$
が成立する.

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

  • $p=2$
    $n\not\equiv0\pmod6$の場合は明らか. $F_{2n}=F_{n}(F_{n+1}+F_{n-1})$であり, $v_2(F_{n+1}+F_{n-1})= \left\{ \begin{array}{ll} 1 & n\equiv0\pmod6\\ 2 & n\equiv3\pmod6 \\ \end{array} \right.$であることが$\bmod8$でわかるのでよい.

  • $p=3$
    $n\not\equiv0\pmod4, n\not\equiv0\pmod3$の場合は明らか. $n$が偶数のとき, 以下が成立する.
    $F_{3n}F_{n}=F_{2n}^2-F_{n}^2=F_{n}^2((F_{n+1}+F_{n-1})^2-1)$
    $\bmod9$で頑張ると, $4|n$のとき$v_3((F_{n+1}+F_{n-1})^2-1)=1$なので示された.

  • $p=5$
    $F_{5n}F_n=F_{3n}^2-(-1)^nF_{2n}^2=(F_{2n}^2-(-1)^nF_{n}^2)^2-(-1)^nF_{2n}^2$
    $S_n:=F_{n+1}+F_{n-1}=\dfrac{F_{2n}}{F_n}=F_n+2F_{n-1}$とおくと,
    $\begin{align*} &F_{5n}F_n\\ =&(F_{2n}^2-(-1)^nF_{n}^2)^2-(-1)^nF_{2n}^2\\ =&(F_n^2S_n^2-(-1)^nF_n^2)^2-(-1)^nF_n^2S_n^2\\ =&F_n^2((S_n^2-(-1)^n)^2-(-1)^nS_n^2)\\ =&F_n^2(S_n^4-3(-1)^nS_n^2+1) \end{align*} $
    であり, $S_n=5n+k$のように置いて頑張ると$S_n^4-3(-1)^nS_n^2+1\equiv5\pmod{25}$なので示された.

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

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

$p=5$の場合

$v_5(n)=v_5(F_n)\ge2v_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)\ge2v_2(n)$より$v_2(n)\le2$なので, $v_2(n)=2$
$1+v_3(n)=v_3(F_n)\ge2v_3(n)$より$v_3(n)\le1$なので, $v_3(n)=1$
ここで, $5|n$の場合は上と同じ議論で不適であるので, $7$以上の素数で$n$を割り切るものが存在したとし, 最小のものを$p$とおく. このとき, $p|F_{\gcd(n, p\pm1)}$である. $p$の最小性より$\gcd(n, p\pm1)$は高々$12$であるが, このとき$p|144$となり$p\ge7$に矛盾.
$n=12$は条件を満たす.

以上より, 求めるべき$n$$1, 12$

感想

冪の差なので$2^n-1$とかと似た振る舞いをしてマスターデーモンとほとんど同じように解けるということです. 多分.

参考文献

投稿日:2023325

この記事を高評価した人

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

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

バッジはありません。

投稿者

りぼーす
りぼーす
133
23637

コメント

他の人のコメント

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