フィボナッチ数列などの一般リュカ数列の整除性（3）項の最大公約数

140

この記事で示すこと

本記事ではフィボナッチ数をはじめとする一般リュカ数列が持つ項間の最大公約数が持つ有名な性質に以下の性質について示す.
よく知られた事実であるので,ここではあるこだわりを持って
次の方針で示す.それは「互除法的な手法を用いない」である.

一般リュカ数列の最大公約数の性質

$U_{n} = U_{n} (P, Q) について GCD (P, Q) = 1 のとき$
$GCD (U_{m}, U_{n}) = U_{GCD (m, n)}$

道具立て1（過去記事で示したもの）

一般リュカ数の項間の整除性

U_nの項番についての整除性

$自然数 m, n について m | n ならば U_{m} | U_{n}$

その他いくつかの補題

k項飛ばしリュカ数列の満たす漸化式

$U_{n + 1} - P U_{n} + Q U_{n - 1} = 0$
を満たす数列U_nについて、この数列をk個毎に取った数列は
$U_{n + k} - V_{k} U_{n} + Q^{k} U_{n - k} = 0$
を満たす。

U_nとV_nの関係式

$V_{n} = P U_{n} - 2 Q U_{n - 1} (n \geq 1)$

証明については過去記事のフィボナッチ数列などの一般リュカ数列の整除性
およびフィボナッチ数列などの一般リュカ数列の整除性（2）リュカ数の二乗で割り切れるリュカ数

道具立て2（本記事で示すもの）

一般リュカ数の加法定理とそのアレンジ

一般リュカ数の加法定理

$m, n について U_{n + m} = U_{m} U_{n + 1} - Q U_{m - 1} U_{n}$

一般リュカ数の減法定理

$n > m なる m, n について - Q^{m} U_{n - m} = U_{m} U_{n + 1} - U_{m + 1} U_{n}$

一般リュカ数列とその定義にあるP,Qとの関係

P,Qが互いに素なとき任意のn>0について $Q と U_{n} (P, Q)$ は互いに素

なお,加法定理は減法定理の証明に用いること,２つは本質的に同じものであることから
定理として記載しているが,本題の証明に用いるのは減法のほうのみである.

道具立て2の証明

まず加法定理について示す.

加法定理の証明

一般リュカ数の加法定理

mについての数学的帰納法で示す
$m = 1$ のとき, $U_{0} = 0, U_{1} = 1$ より
$U_{n + 1} = 1 * U_{n + 1} - Q * 0 * U_{n + 1}$
で成り立つ。
$m = 2$ のとき,一般リュカ数の満たす漸化式から
$U_{m + 2} = P U_{m + 1} - Q U_{m}$
$U_{2} = P, U_{1} = 1$ より成り立つ。
$m = k - 1, k$ で成り立つと仮定する。
$U_{n + k - 1} = U_{k - 1} U_{n + 1} - Q U_{k - 2} U_{n} \dots (1)$ $U_{n + k} = U_{k} U_{n + 1} - Q U_{k - 1} U_{n} \dots (2)$
$P * (2) - Q * (1)$ を計算すると,左辺は $U_{n + k + 1}$ ,
右辺は
$(P U_{k} - Q U_{k - 1}) U_{n + 1} - Q (P U_{k - 1} - Q U_{k - 2}) U_{n}$
$= U_{k + 1} U_{n + 1} - Q U_{k} U_{n}$
となり
$U_{n + k + 1} = U_{k + 1} U_{n + 1} - Q U_{k} U_{n}$
$m = k + 1$ の時も成り立つ.

減法定理の証明

ついで減法定理を示す.加法定理と補題3を組み合わせると示せる.

減法定理

加法定理より
$U_{n + m} = U_{m} U_{n + 1} - Q U_{m - 1} U_{n}$
補題3より
$U_{n + m} - V_{m} U_{n} + Q^{m} U_{n - m} = 0$
$U_{n + m} = - V_{m} U_{n} - Q^{m} U_{n - m}$
よって
$- V_{m} U_{n} - Q^{m} U_{n - m} = U_{m} U_{n + 1} - Q U_{m - 1} U_{n}$
これを整理すると
$- Q^{m} U_{n - m} = U_{m} U_{n + 1} - (V_{m} + Q U_{m - 1}) U_{n}$
補題4より
$V_{m} = P U_{m} - 2 Q U_{m - 1}$
$V_{m} + Q U_{m - 1} = P U_{m} - Q U_{m - 1} = U_{m + 1}$
よって
$- Q^{m} U_{n - m} = U_{m} U_{n + 1} - U_{m + 1} U_{n}$

$Q と U_{n} (P, Q)$ は互いに素 $(n > 0)$

nについての数学的帰納法で示す.
$n = 1$ のとき $U_{1} = 1$ なので自明に成り立つ.
$n = k$ で $GCD (U_{k}, Q) = 1$ が成り立つと仮定する.
$n = k + 1$ のとき
$U_{k + 1} = P U_{k} - Q U_{k - 1}$ より
$GCD (U_{k + 1}, Q) = GCD (P U_{k}, Q)$
$GCD (P, Q) = 1, GCD (U_{k}, Q) = 1$ なので
$GCD (P U_{k}, Q) = 1$
よって
$GCD (U_{k + 1}, Q) = 1$

$GCD (U_{m}, U_{n}) = U_{GCD (m, n)}$ の証明

実のところ減法定理の式自体でだいたい証明は終わっている.
以下の通り示される.

$GCD (m, n)$ について,整数についてのベズーの定理(ベズーの等式)より
$GCD (m, n) = m x + n y$ となる整数 $x, y$ が存在する.
$0 < GCD (m, n) \leq m, n$ であるので
$x, y$ は一方が正でもう一方が負か0
適当に $m, n$ を入れ替えることで
$GCD (m, n) = m x - n y, x, y \geq 0$
としてよい.
減法定理より
$- Q^{- n y} U_{m x - n y} = U_{m x} U_{n y + 1} - U_{m x + 1} U_{n y}$
$GCD (m, n) = m x - n y$ なので
$- Q^{n y} U_{GCD (m, n)} = U_{m x} U_{n y + 1} - U_{m x + 1} U_{n y}$
一般リュカ数の整除性から
$U_{m} | U_{m x}, U_{n} | U_{n y}$ であるので $U_{m x} = M U_{m}, U_{n y} = N U_{n} （ M, N は自然数）$
と書くことができる.
$- Q^{n y} U_{GCD (m, n)} = M U_{n y + 1} U_{m} - N U_{m x + 1} U_{n}$
この式と,ベズーの等式より
$GCD (U_{m}, U_{n}) ｜ Q^{n y} U_{GCD (m, n)}$
$m, n > 0$ のとき $Q と U_{m} および U_{n}$ は互いに素であったので
$Q と GCD (U_{m}, U_{n})$ も互いに素.
よって $GCD (U_{m}, U_{n}) ｜ U_{GCD (m, n)}$

一方, $GCD (m, n) | m, GCD (m, n) | n$ であるので
一般リュカ数の整除性から
$U_{GCD (m, n)} | U_{m}, U_{GCD (m, n)} | U_{n}$
であるので
$U_{GCD (m, n)} | GCD (U_{m}, U_{n})$

$GCD (U_{m}, U_{n}) ｜ U_{GCD (m, n)}$ かつ $U_{GCD (m, n)} | GCD (U_{m}, U_{n})$ であるので
$U_{GCD (m, n)} = GCD (U_{m}, U_{n})$

最後に

加法定理から互除法的に示したらいいじゃないか,とか
$Q と U_{n} (P 、 Q)$ の互いに素を示してるところは互除法じゃないのか,
という話はある

投稿日：2023年7月26日

この記事を高評価した人

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

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

バッジはありません。

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

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

投稿者

TKSS

5112

他の人のコメント

コメントはありません。

読み込み中

TKSS

フィボナッチ数列などの一般リュカ数列の整除性（3）項の最大公約数

この記事で示すこと
道具立て1（過去記事で示したもの）
道具立て2（本記事で示すもの）
道具立て2の証明
$ \operatorname{GCD}(U_m,U_n)=U_{\operatorname{GCD}(m,n)} $の証明
最後に

フィボナッチ数列などの一般リュカ数列の整除性（3）項の最大公約数

この記事で示すこと

道具立て1（過去記事で示したもの）

道具立て2（本記事で示すもの）

道具立て2の証明

加法定理の証明

減法定理の証明

とQとUn(P,Q)は互いに素(n>0)

GCD⁡(Um,Un)=UGCD⁡(m,n)の証明

最後に

この記事を高評価した人

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

投稿者

コメント

他の人のコメント

$Q と U_{n} (P, Q)$ は互いに素 $(n > 0)$

$GCD (U_{m}, U_{n}) = U_{GCD (m, n)}$ の証明