作問の備忘録

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

一般化へ

互除法

なぜ、 $F_n=3\cdot2^n-(-1)^n$ ではうまく畳数を固定できたのか考えてみる。

まず、 $F_{2k}=F_{2k-1}+F_{2k-1}-3$ について、

$F_{2k}に対し、F_{2k-1}=\frac{F_{2k}+p}{2}(pは自然数)$ という形になっているので、必ず次の式では $F_{2k-1}=(F_{2k-1}-p)+p$ となり、pが余ることになる。

(かといって、これをそのまま解いて $F_n=(F_1-p)\cdot2^{n-1}+p$ としても条件が足りなくてうまくいかない。)

あとはこのpに対し、 $F_{2k-1}-p=pm+1(mは整数)$ の形をしていればよい。

では逆回しをしてみよう。

(1) pで割ると常に1余る式を考える。

(2) (1)にpを足して $F_{2k-1}$ とする。

(3) (2)を2倍してpを引き、 $F_{2k}$ とする。

今、フィボナッチ数列に似た漸化式をもとにしているので、

一般項は $F_n=ar^n+bs^n$ という形の式になる。

(1)を満たすためには、 $F_n=ar^n+1$ としてしまうのが手っ取り早い。

しかし、もう一つ条件がある。

$F_{2k}とF_{2k+1}$ について、

$F_{2k+1}=2F_{2k}+q(F_{2k} ＞ qとして余りをqにする)$

次の式は $F_{2k}をq$ で割ることになるが、

$F_{2k}=ar^{2k}+bs^{2k}$ の形のとき、

$bs^{2k}をaで割った余りが固定されるようにする。$

$(s^2)^kをaで割った余りが固定される、つまりs^2 \equiv 1 (\bmod a)$ であればよい。

そのうえで、q=aとする。

しかし、 $F_n=ar^n+1$ とするとここで問題が起こってしまう。

２行目の式ですでに1に到達してしまうのだ。

これを防ぐには $b\neq1$ とすればよい。

~つづく~