ユークリッドの互除法

ユークリッドの互除法を知らないあなたも、まずは実際にどんな解き方をするのか見てみましょう。
実際に3355と2379の最大公約数を求めてみます。

このように
小さい数で大きい数を割る
あまりで割る数を割る
さらにあまりで割る数を割る…
と割り切れるまで続けます。そして最後の割る数が最大公約数となるのです。

ユークリッドの「互除法」とは「割り切れるまであまりで互いに割り（除法）続ける」という意味なんですね。

ユークリッドの互除法の証明

ADVERTISEMENT

 

どうしてユークリッドの互除法で最大公約数が求まるのでしょうか。
直感的に理解するのはなかなか難しい計算方法なので、正確に証明してみます。

ユークリッドの互除法を証明する前に、

ということを証明します。

ということがわかりました。
今証明したのは、
「割られる数と割る数の最大公約数と割る数とあまりの最大公約数は一致する」
ということです。
言い換えると
「ユークリッドの互除法の操作を何回行っても、割られる数と割る数は一致する」
ということになります。
割り切れたときには、割る数が最大公約数なのは自明です。
よって、「割り切れるまでユークリッドの互除法を続けたときの最後の割る数が最大公約数である」ということが言えるのです。