最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~
2018/08/07 微編集
最大公約数と最小公倍数を求める ~1/3 割れるだけ割ってみる~
最大公約数と最小公倍数を求める ~2/3 素因数分解を利用する~
最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~ ←この記事
最後に ユークリッドの互除法 という手法を利用して、
最大公約数と、最小公倍数を求める方法について勉強してみる
ユークリッドの互除法を利用する
2つの数のうち、大きい方を 、小さい方を と表すことにする。
1. を で割ってあまり を求める。
ここで であれば が2つの数 の最大公約数になる。
2. ならば、 に の数を 、 に の数を入れて、再度割り算を行う。
あまりが 0 になるまで、この「2.」の手順を繰り返し、あまりが 0 になったとき、その割り算に使った"割った数" の方が、2つの数 の 最大公約数 になる。
これによる最大公約数の求め方をユークリッドの互除法と呼ぶ。
また、求まった最大公約数で のどちらか一方を割って、その結果を割っていない方に掛けた結果が、2つの数 の 最小公倍数 になる。
関連する事実
本題の前に ある事実を紹介
■ 事実..
のあまりを とするとき、
と の最大公約数は と の最大公約数でもある。
■ 証明..
を で割って求まる商を
あまりを とする時、この関係を以下の式で表す
①
と の公約数を とするとき
① の と から を引っ張り出して式を整理する
右辺は の倍数。
よって、左辺 も の倍数。
つまり、 は の約数である
は の約数なので、
は と の公約数になる
次に ① を 「 を左辺とする式」に書き換えてみる
②
と の公約数を とするとき、
② の と から を引っ張り出して式を整理する
右辺は の倍数。
よって、左辺 も の倍数。
つまり、 は の約数である
は の約数なので、
は と の公約数になる
以上のことから、
と の公約数 は、 と の公約数であり
と の公約数 は、 と の公約数である
よって双方の公約数は、もれなく一致する。
"どちらか片方にだけある" という公約数は存在しない...その結果、 と の最大公約数は、ちょうど と の最大公約数と一致する。
自分なりに解釈 (最大公約数)
を で割ってあまりが出る場合、 に の数を、 にあまり の数を入れて、割り算を繰り返す。
「あまりの数で割り、そのあまりの数で割り…」の繰り返しになるため、あまり はその度にだんだんと小さくなり、いずれ に行き着く
になったとき、つまりは繰り返しの中で を で割り切れるタイミングが来たとき、その の数が、 と にとっての最大公約数になる
の最大の約数は 自身である。 を で割り切れるなら、 が と の最大公約数になる
また、前述の事実に従って、繰り返しの中の と の最大公約数、並びに と の最大公約数は、どれも常に一致し、ずっと変わらない。
よって、 と の最大公約数は、そのまま 初めの と の最大公約数になる
自分なりに解釈 (最小公倍数)
上で求まった最大公約数を使って 2つの数のどちらか一方を割り、得られた商を "割っていない方" に掛けた結果が、2つの数の最小公倍数になる。
2つの数を 、最大公約数を
そのによって割られた 2つの数を
とするとき、最小公倍数 を求めるこの計算は
もしくは
である。
これより先は 「割れるだけ割ってみる」 の記事で説明したとおり。
3つ以上の数の最大公約数と最小公倍数
3つ以上の数の中で一番小さな数を使って、その他の数を割り、そのあまりの数で元の数を置きかえる。
新しくできたグループの中でまた一番小さな数 (0を除く) を探し、その数で他の数を割ってあまりの数で元の数を置きかえる...
これを繰り返し、最終的に「他の数」すべてのあまりの数が 0 になったとき、その割り算に使った"一番小さな数" が 3つ以上の数にとっての最大公約数 になる
もしくは、3つ以上の数の中のどれか 2つの数から 前述のユークリッドの互除法によって 2つの数の最大公約数を求め、
その数と、また別の残っている数を使って ユークリッドの互除法によって3つの数の最大公約数を求め… を繰り返すことによっても 、3つ以上の数の最大公約数を求めることができる。
3つ以上の数の最小公倍数を求めるために、ユークリッドの互除法を使うサンプルは、今回見つけることができなかった。
最小公倍数を求める対象が3つ以上になる場合は、「割れるだけ割ってみる」または「素因数分解を利用する」の記事で紹介した方法を使って解くのがよろしそう。
最大公約数と最小公倍数の求め方を、
自分の納得がいくまで調べてみたつもり。
ユークリッドの互除法は、この用途とは別に
1次不定方程式の解を求めるためにも利用できるらしい。
その辺の理屈を調べてみるのは、また今度気が向いた時にでも (やらない)
参考にした書籍/サイトさん
最小公倍数/最大公約数
最大公約数と最小公倍数