0

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

104
0
$$$$

この記事で示すこと

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

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

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

道具立て1(過去記事で示したもの)

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

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

$$ 自然数m,nについて m|nならばU_m|U_n $$

その他いくつかの補題

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

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

U_nとV_nの関係式

$$V_n=PU_n-2QU_{n-1} (n\geq1)$$

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

道具立て2(本記事で示すもの)

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

一般リュカ数の加法定理

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

一般リュカ数の減法定理

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

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

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

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

道具立て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}=PU_{m+1}-QU_{m} $$
$U_2=P,U_1=1$より成り立つ。
$m=k-1,k$で成り立つと仮定する。
$$ U_{n+k-1}=U_{k-1}U_{n+1}-QU_{k-2}U_{n} \cdots(1) $$$$ U_{n+k}=U_{k}U_{n+1}-QU_{k-1}U_{n}   \cdots(2) $$
$P*(2)-Q*(1)$を計算すると,左辺は$U_{n+k+1}$,
右辺は
$$  (PU_{k}-QU_{k-1})U_{n+1}-Q(PU_{k-1}-QU_{k-2})U_{n} $$
$$ =U_{k+1}U_{n+1}-QU_{k}U_{n} $$
となり
$$ U_{n+k+1}=U_{k+1}U_{n+1}-QU_{k}U_{n} $$
$m=k+1$の時も成り立つ.

減法定理の証明

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

減法定理

加法定理より
$U_{n+m}=U_{m}U_{n+1}-QU_{m-1}U_{n}$
補題3より
$U_{n+m}-V_mU_{n}+Q^{m}U_{n-m}=0$
$U_{n+m}=-V_mU_{n}-Q^{m}U_{n-m}$
よって
$ -V_mU_{n}-Q^{m}U_{n-m}=U_{m}U_{n+1}-QU_{m-1}U_{n} $
これを整理すると
$ -Q^{m}U_{n-m}=U_{m}U_{n+1}-(V_m+QU_{m-1})U_{n} $
補題4より
$ V_m=PU_m-2QU_{m-1} $
$ V_m+QU_{m-1}=PU_m-QU_{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$$\operatorname{GCD}(U_{k},Q)=1$が成り立つと仮定する.
$n=k+1$のとき
$U_{k+1}=PU_{k}-QU_{k-1}$より
$\operatorname{GCD}(U_{k+1},Q)=\operatorname{GCD}(PU_{k},Q)$
$\operatorname{GCD}(P,Q)=1,\operatorname{GCD}(U_{k},Q)=1$なので
$\operatorname{GCD}(PU_{k},Q)=1$
よって
$\operatorname{GCD}(U_{k+1},Q)=1$

$ \operatorname{GCD}(U_m,U_n)=U_{\operatorname{GCD}(m,n)} $の証明

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

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

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

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

最後に

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

投稿日:2023726

この記事を高評価した人

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

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

バッジはありません。

投稿者

TKSS
TKSS
30
3766

コメント

他の人のコメント

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