NAHA

記録帳

ユークリッドの互除法

 1.4.1で扱われているユークリッドの互除法の計算回数について調べた。
ラメの定理 a,b∈自然数(0を含む), a>b, mをbの桁数, nをユークリッドの互除法で余りを求めた回数とする。このとき 5m >= n となる。
 証明には1.4.2で扱われているフィボナッチ数が重用な役割を演ずる。具体的に言うと、b >= f_(n+1)となることを使う。その証明はf_i = f_(i-1) + f_(i-2)とr_i = q_(n-i+1)*r_(n-i+1) + r_(n-i+2)を見比べれば分かる。(q_(n-i+1) >= 1に注意)i=n-1とすれば良い。
 ユークリッドの互除法とラメの定理については
プログラミングの背景:数論
のPDFが参考になった。
 完全に自分用のメモなので無定義語あります。