作問の備忘録

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

互除法の作問

 ax+by=1 の整数解(x,y)を求めよ」のような問題は、 a,bに互いに素である整数を選べばいくらでも作れる。

しかし問題作成者の立場で考えると、それが「何行の計算で終わるのか」が重要になってくる。

互いに素である整数 a,bについて、互除法をしたときに1に到達するまでの式の行数をここでは畳数と呼び、 f(a,b)と書くことにする。

例えば、3と2の場合、 3=2\times 1+1で、 f(3,2)=1

 f(5,2)=1,f(5,3)=2である。

 

a,bに求める条件は、

1.3桁以下の整数である。

2.畳数が3以下である。

 

最も簡単に作るには、1からスタートして単純に足し算を繰り返せばよい。

要はフィボナッチ数列を考えればよいのだ。

フィボナッチ数列 F_{n+2}=F_{n}+F_{n+1},F_0=1,F_1=1の隣り合う2つの項 F_n,F_{n+1}(n \geqq 2)は、必ず互いに素、畳数 (n-1)になる。

つまり、8と5にすればよい。

 

畳数3程度ならば、excelなどでごり押してもよいと思うが、

畳数が常に3になるような2つの式を作ることが理想である。

フィボナッチ数列の2項は式で表せるのだから、できないことはないと思う。