ユークリッドの互除法について

質問

この問題がわかりません！どなたか解答お願いします！(ˉ ˘ ˉ; )

この投稿のマルチメディアは削除されているためご覧いただけません。

回答No.2

tmppassenger · ベストアンサー

先程と同様の記号で、Z[N] = X[N] + Y[N] とおく。(N+1)回目の操作を考える。
（念の為書いておくが、Euclidの互助法を繰り返した時の大きい方をX[N], 小さい方をY[N]とおいているので、X[N] > Y[N] である）

X[N]をY[N]で割った時の商をq, 余りをr とおく。即ち
X[N] = q * Y[N] + r とおく。この時、q≧1, 0≦r≦Y[N] - 1 が成り立つ。
又、X[N+1] = Y[N], Y[N+1] = r となる。

この時、Y[N] > 0なら、
Z[N] / Z[N + 1] = ((q+1)Y[N] + r) / (Y[N] + r) ≧ (2Y[N] + r) / (Y[N] + r) = (3/2) + (1/2) (Y[N] - r) / (Y[N] + r) > 3/2
従って、0<Z[N+1] / Z[N] < 1/1.5。つまり帰納法から、Z[N] < (A+B) / {(1.5)^N} である。

Z[L]は正整数、従って1以上であるから、1 ≦Z[L] < (A+B) / {1.5}^L、従って L< log(A+B) / log(1.5)である。

回答No.1

tmppassenger

この評価式なら易しいですね。あからさまに成り立つ評価式を使えるので、何か問題が間違っている（か、出題の意図と問題があってない）のではないか、と疑ってしまいますが...

始めのA, Bのうち、大きい方をX[0], 小さい方をY[0]とする。
Euclidの互除法をN回行った後の、大きい方の数をX[N]、小さい方の数をY[N]とする

N+1回目を考えると、「大きい方の数を、『大きい方の数を小さい方の数』で割ったあまりに置き換える」という操作を行う。
ここで、X[N]をY[N]で割ったあまりはY[N]未満、つまりY[N]-1以下なので、

〇 X[N+1] = Y[N], Y[N+1] ≦ Y[N] - 1

が必ず成立する。帰納法から、Y[N]≦ Y[0] - N。
従って、L≦ min { A, B } （LはAとBの内小さい方以下）であるゆえ、

L ≦ min {A, B} ≦ B ≦ log(A) / log(1.5) + B (qed)

補足

問題ミスってましたね、
問い: L <= log[1.5](A+B)を示せ
の場合どうなりますか？
これでも簡単な気もしますが、、、