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

質問

ユーグリッド互除法を使って

a0 = 497, a1 = 284 とすると

497 = 284 + a2

284 = 213 + a3

213 = 71 * 3 + a4

ここでa4　== 0 となるので計算終了.

こういった手順ですが、

497 = 284 + a2

497 = 213 + a3

497 = 71 + 3 + a4

ここでa4 == 0となるので計算終了.

この手順でも答えがでてしまい以下のような結論がでました.

つまり,　

a0 = a1 * q1 + a2

a1 = a2 * q2 + a3

....................................

とa0 → a1 を更新しなくても答えが上記のようにでてるのでa0 → a1のような手順を行わなくてもいいのではないか？ということです.

ですが、いろいろサイトを見てもa0 → a1のように各プロセスで更新を行っていて混乱しています.

ご教授ねがいます.

回答No.4

noname#47894 · ベストアンサー

No.1です。
No.3さん、間違いを指摘してくださってありがとうございます。

No.3で反例が示されてますから、やっぱりダメってことですね。
確かに
52＝11 × 4　＋　8
52＝ 8 × 6　＋　4
52＝13 × 4
で？　みたいな感じですね。

きちんと考えると、
a0 = a1 * q1 + a2　で　a0とa1の最大公約数rについて
b0*r＝b1*r*q1+a2　と書けるので(b0,b1は互いに素)、a2=(b0-b1*q1)*r
ここで、a0＝b0*r、a2(b0-b1*q1)*r　なので、
a0とa2について最大公約数を考えると、b0と(b0-b1*q1)が　互いに素であれば、r　で問題ないのですが、b0とq1に公約数があると、互いに素でなくなって、もっと大きな公約数がでてきてしまうところが問題ですね。

通常の互除法は、
a1とa2について最大公約数を考えるのですが、b0,b1は互いに素なので、b1と、b0-b1*q1　も互いに素で問題なし　というわけだったんですね。

回答No.3

hugen

30 = 8*3+6
30 = 6*5+0

回答No.2

zk43

理屈は合っているようですが、a1よりもa0の方がものすごく大きい数の
場合は、やはりa2,a3,・・・と置き換えて数字を小さくしていった方が計算が楽だと思います。

回答No.1

noname#47894

497 = 284 + a2
　497 = 213 + a3
　497 = 71 + 3 + a4

　つまり,　
　a0 = a1 * q1 + a2
　a1 = a2 * q2 + a3

ですが、
497 = 284 + a2
497 = 213×2 + a3
497 = 71×7 + a4

つまり
a0 = a1 * q1 + a2
a0 = a2 * q2 + a3

本当は、こう書きたかった　ということでいいですか？

おおざっぱにやると
a0 = a1 * q1 + a2　で　a0とa1の公約数rについて
b0*r＝b1*r*q1+a2　と書けるので、a2=(b0-b1*q1)*r　なので、
rは、a2の約数でもあります。

(a0 ，a1)　の公約数は、(a1 ， a2)の公約数である
(a1 ，a2)　の公約数は、(a2 ， a3)の公約数である
を繰り返すのが、互除法ですが、ご質問の方法は、
(a0 ，a1)　の公約数は、(a0 ， a2)の公約数である
(a0 ，a2)　の公約数は、(a0 ， a3)の公約数である
をやっているわけで、実質的には同じことをやっているので、これでも問題はないと思います。

実用上は、数字が小さい方が計算がしやすいので、従来法のほうが好ましいかもしれません。