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

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$の時も成り立つ.

加法定理より
$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} $

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}(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}) $$