互除法の式の個数について再考

教材化できないか考えている。

例えば、自然数の組{3,4}について、最大公約数は1である。

また、4=3×1+1で、最大公約数にたどり着くまでの式の個数は1

この式の個数をDep({3,4})=1と表してみる。

{3+4,4}と{3,3+4}はそれぞれ{3,4}と同じ最大公約数を持つ。

自然数の組{a,b}について、

H({a,b})={a+b,max(a,b)}

L({a,b})={a+b,min(a,b)}

とする。

Dep(H({a,b})=Dep({a,b})+1

Dep(L({a,b})=Dep({a,b})

Depが増えるかどうかはH,Lどっちの足し算を選ぶかによる。

Depを3にするには

最短でHH

あとはLを何回どこに挟むかだけ。

L…LHL…LH 

つまり、L…n個…LHL…m個…LHのとき

{a(n(m+1)+1)+b(m+1),a(n(m+2)+1)+b(m+2)}

よく考えたら当たり前の話か。