作問の備忘録

テスト問題を作るときの、大した計算ではないけれども、やろうと思うとめんどくさいことどもを記録。

互除法の作問(フィボナッチもどきの利用)

互除法

互除法で余りが1になるまでの式の行数をコントロールしたかった。

作問の関係上、なるべく何の変哲もない数で、無限に生成できて、途中式の難易度もコントロールできるとなおよい。

$F_0=1,F_1=1,F_{n+2}=kF_n+F_{n+1}$ というフィボナッチもどきの数列を考えることにする。

k=1のときはフィボナッチ数列そのもので、これは隣り合う2項の畳数がどんどん増えていくのだった。

k=2のとき、きちんと証明はしていないが、どうも互除法の計算式がループし、畳数がループするようだった。初期値の与え方によってループの長さは変化する。

で、いくつか数を変えて試してみたところ、

どうも、 $F_0=2,F_1=7,F_{n+2}=2F_n+F_{n+1}$ で生成される数列の隣り合う2項 $F_n,F_{n+1}$ は、 $n\geqq1$ のとき、常に畳数３になるようだ。

一般項は $F_n=3\cdot2^n-(-1)^n (n\geqq0)$ である。

互いに素であることは簡単に示せる。

$ある k\geqq1$ とする。 $F_k,F_{k+1}$ に、共通因数 $d\neq1$ が存在すると仮定すると、

$F_k=da,F_{k+1}=db$ と表せる。

$db=2F_{k-1}+da$

$d(b-a)=2F_{k-1}$

ここで， $F_0=2,F_1=7,F_{n+2}=2F_n+F_{n+1}$ から、各 $F_n (n=1,2,3…)$ は奇数、 $F_k ＜ F_{k+1}$ なので、

$d,a,b$ は奇数、 $b-a=2N(Nは自然数)$ と表せる。

$2dN=2F_{k-1}$

$F_{k-1}=dN$

$F_{k-1}$ も $d$ の倍数である。

これを繰り返すと、 $k$ 以下の項はすべて $d$ の倍数となるが、

これは $F_1=7,F_2=11$ に矛盾。

よって、 $F_n,F_{n+1} (n\geqq0)$ は互いに素である。

さて、 $n \geqq 1$ で $F_n,F_{n+1}$ の畳数が３であることを示そう。

$F_{2k-1},F_{2k}(k\geqq 1)$ について、

$F_{2k-1}=3\cdot2^{2k-1}-(-1)^{2k-1}=3\cdot2^{2k-1}+1$

$F_{2k}=3\cdot2^{2k}-(-1)^{2k}=3\cdot2^{2k}-1$

$F_{2k}-F_{2k-1}=3\cdot(2^{2k}-2^{2k-1})-2$

$F_{2k}-F_{2k-1}=3\cdot2^{2k-1}-2$

$F_{2k}-F_{2k-1}=F_{2k-1}-3$

$F_{2k}=F_{2k-1}+(F_{2k-1}-3)$

また、

$F_{2k-1}-3=3\cdot2^{2k-1}-2\equiv1(\bmod3)$

よって、

$F_{2k}=F_{2k-1}+(F_{2k-1}-3)$

$F_{2k-1}=(F_{2k-1}-3)+3$

$F_{2k-1}-3=3m+1(mは整数)$

畳数は常に３である。

$F_{2k},F_{2k+1}(k\geqq1)$ について、

$F_{2k+1}=3\cdot2^{2k+1}-(-1)^{2k+1}=3\cdot2^{2k+1}+1$

$F_{2k}=3\cdot2^{2k}-(-1)^{2k}=3\cdot2^{2k}-1$

$2F_{2k}=3\cdot2^{2k+1}-2$

$F_{2k+1}=2F_{2k}+3$

また、 $F_{2k}=3\cdot2^{2k}-1\equiv2(\bmod3)$

よって、

$F_{2k+1}=2F_{2k}+3 \hspace{.5em}(k\geqq1なのでF_{2k} ＞ 3)$

$F_{2k}=3(2^{2k}-1)+2$

$3=2\cdot1+1$

畳数は常に３である。

ゆえに、 $F_0=2,F_1=7,F_{n+2}=2F_n+F_{n+1}$ の隣り合う２項 $F_n,F_{n+1}(n\geqq1)$ は畳数３である。