フィボナッチ数列同士の最大公約数

by nomura · 2024年12月10日

フィボナッチ数列同士の最大公約数
$m,n\in\mathbb{Z}$とする。
2つのフィボナッチ数列の最大公約数について次が成り立つ。

(1)

\[ \gcd\left(F_{m},F_{m+1}\right)=1 \]

(2)

\[ \gcd\left(F_{m},F_{n}\right)=F_{\gcd\left(m,n\right)} \]

-

$F_{n}$はフィボナッチ数列

$F_{8}=21,F_{12}=144$で$\gcd\left(21,144\right)=3$である。
\begin{align*} \gcd\left(F_{8},F_{12}\right) & =F_{\gcd\left(8,12\right)}\\ & =F_{4}\\ & =3 \end{align*} となり一致する。

(1)

$0<m$のとき

\begin{align*} \gcd\left(F_{m},F_{m+1}\right) & =\gcd\left(F_{m},F_{m}+F_{m-1}\right)\\ & =\gcd\left(F_{m},F_{m-1}\right)\\ & =\gcd\left(F_{m-1},F_{m}\right)\\ & =\LHS\left(m\rightarrow m-1\right)\\ & =\gcd\left(F_{1},F_{2}\right)\\ & =1 \end{align*} なので成り立つ。

$m=0$のとき

\begin{align*} \gcd\left(F_{0},F_{1}\right) & =\gcd\left(0,1\right)\\ & =1 \end{align*} なので成り立つ。

$m<0$のとき

$0<m$のときの結果を使うと、
\begin{align*} \gcd\left(F_{m},F_{m+1}\right) & =\gcd\left(\left(-1\right)^{m+1}F_{-m},\left(-1\right)^{m+2}F_{-\left(m+1\right)}\right)\\ & =\gcd\left(F_{-m},F_{-\left(m+1\right)}\right)\\ & =1 \end{align*} なので成り立つ。

-

これらより、任意の$m\in\mathbb{Z}$について成り立つので与式は成り立つ。

(2)

$F_{1}$と$F_{m}$の最大公約数は
\begin{align*} \gcd\left(F_{1},F_{m}\right) & =\gcd\left(1,F_{m}\right)\\ & =F_{m} \end{align*} となる。
フィボナッチ数列の加法定理
\[ F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} \] より、
\begin{align*} \gcd\left(F_{m},F_{n}\right) & =\gcd\left(F_{m},F_{m+\left(n-m\right)}\right)\\ & =\gcd\left(F_{m},F_{m-1}F_{n-m}+F_{m}F_{n-m+1}\right)\\ & =\gcd\left(F_{m},F_{m-1}F_{n-m}\right)\\ & =\gcd\left(F_{m},F_{n-m}\right){\because\gcd\left(F_{m},F_{m+1}\right)=1}\\ & =\gcd\left(F_{\gcd\left(m,n\right)},F_{\gcd\left(m,n\right)}\right)\cmt{\because\gcd\left(F_{1},F_{m}\right)=F_{m},\gcd\left(F_{m},F_{n}\right)=\gcd\left(F_{m},F_{n-m}\right)}\\ & =F_{\gcd\left(m,n\right)} \end{align*} となるので与式は成り立つ。