https://darkcrowcorvus.hatenablog.jp/entry/2017/12/12/025933

2018/08/07 微編集
最大公約数と最小公倍数を求める～1/3 割れるだけ割ってみる～
最大公約数と最小公倍数を求める～2/3 素因数分解を利用する～
最大公約数と最小公倍数を求める～3/3 ユークリッドの互除法を利用する～ ←この記事

最後に ユークリッドの互除法 という手法を利用して、
最大公約数と、最小公倍数を求める方法について勉強してみる

ユークリッドの互除法を利用する

2つの数のうち、大きい方を $A$ 、小さい方を $B$ と表すことにする。

１. $A$ を $B$ で割ってあまり $r$ を求める。
ここで $r=0$ であれば $B$ が2つの数 $A,B$ の最大公約数になる。

２. $r \gt 0$ ならば、 $A$ に $B$ の数を、 $B$ に $r$ の数を入れて、再度割り算を行う。

あまりが 0 になるまで、この「２.」の手順を繰り返し、あまりが 0 になったとき、その割り算に使った"割った数" の方が、2つの数 $A,B$ の 最大公約数 になる。

f:id:DarkCrowCorvus:20171206010823j:plain

これによる最大公約数の求め方をユークリッドの互除法と呼ぶ。

また、求まった最大公約数で $A,B$ のどちらか一方を割って、その結果を割っていない方に掛けた結果が、2つの数 $A,B$ の 最小公倍数 になる。

f:id:DarkCrowCorvus:20171206013321j:plain

自分なりに解釈 (最大公約数)

$A$ を $B$ で割ってあまりが出る場合、 $A$ に $B$ の数を、 $B$ にあまり $r$ の数を入れて、割り算を繰り返す。

「あまりの数で割り、そのあまりの数で割り…」の繰り返しになるため、あまり $r$ はその度にだんだんと小さくなり、いずれ $r=0$ に行き着く

f:id:DarkCrowCorvus:20171212015213j:plain

$r=0$ になったとき、つまりは繰り返しの中で $A_i$ を $B_i$ で割り切れるタイミングが来たとき、その $B_i$ の数が、 $A_i$ と $B_i$ にとっての最大公約数になる

$B_i$ の最大の約数は $B_i$ 自身である。 $A_i$ を $B_i$ で割り切れるなら、 $B_i$ が $A_i$ と $B_i$ の最大公約数になる

また、前述の事実に従って、繰り返しの中の $A$ と $B$ の最大公約数、並びに $B$ と $r$ の最大公約数は、どれも常に一致し、ずっと変わらない。

f:id:DarkCrowCorvus:20180731062839g:plain

よって、 $A_i$ と $B_i$ の最大公約数は、そのまま初めの $A$ と $B$ の最大公約数になる

自分なりに解釈 (最小公倍数)

上で求まった最大公約数を使って 2つの数のどちらか一方を割り、得られた商を "割っていない方" に掛けた結果が、2つの数の最小公倍数になる。

2つの数を $A,B$ 、最大公約数を $G$
その $G$ によって割られた 2つの数を $a,b$
とするとき、最小公倍数 $L$ を求めるこの計算は

${\hspace{6pt}}L=aB{\hspace{8pt}}$ もしくは ${\hspace{8pt}}L=Ab$

${\hspace{6pt}}{\therefore}{\hspace{6pt}}L=aGb{\hspace{8pt}}$ である。

これより先は「割れるだけ割ってみる」の記事で説明したとおり。

3つ以上の数の最大公約数と最小公倍数

3つ以上の数の中で一番小さな数を使って、その他の数を割り、そのあまりの数で元の数を置きかえる。

新しくできたグループの中でまた一番小さな数 (0を除く) を探し、その数で他の数を割ってあまりの数で元の数を置きかえる...

これを繰り返し、最終的に「他の数」すべてのあまりの数が 0 になったとき、その割り算に使った"一番小さな数" が 3つ以上の数にとっての最大公約数になる

f:id:DarkCrowCorvus:20180807020158g:plain