自由研究ノート(仮)

とかいう名前の備忘録

最大公約数と最小公倍数を求める ~3/3 ユークリッドの互除法を利用する~


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

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

 


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

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

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

2. r \gt 0 ならば、AB の数を 、Br の数を入れて、再度割り算を行う。

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

f:id:DarkCrowCorvus:20171206010823j:plain

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

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

f:id:DarkCrowCorvus:20171206013321j:plain

 

関連する事実 

本題の前に ある事実を紹介

■ 事実..

A{\div}B のあまりを r とするとき、
AB の最大公約数は Br の最大公約数でもある。

 

■ 証明..

AB で割って求まる商を q
あまりを r とする時、この関係を以下の式で表す

{\hspace{6pt}}r=A-Bq\ {\cdots}

AB の公約数を d とするとき
① の A と B から d を引っ張り出して式を整理する

{\hspace{6pt}}r=A'd-B'dq
{\hspace{12pt}}=(A'-B'q)d

右辺は d の倍数。
よって、左辺 rd の倍数。
つまり、dr の約数である

dB の約数なので、
dBr の公約数になる

f:id:DarkCrowCorvus:20171212014111j:plain

次に ① を 「 A を左辺とする式」に書き換えてみる

{\hspace{6pt}}A=Bq+r\ {\cdots}

Br の公約数を d' とするとき、
② の Br から d' を引っ張り出して式を整理する

{\hspace{6pt}}A=(B'q+r')d'

右辺は d' の倍数。
よって、左辺 Ad' の倍数。
つまり、d'A の約数である

d'B の約数なので、
d'AB の公約数になる

以上のことから、
AB の公約数 d は、Br の公約数であり (d\ {\subseteqq}\ d')
Br の公約数 d' は、AB の公約数である (d\ {\supseteqq}\ d')

よって双方の公約数は、もれなく一致する。
"どちらか片方にだけある" という公約数は存在しない...その結果、AB の最大公約数は、ちょうど Br の最大公約数と一致する。

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

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

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

f:id:DarkCrowCorvus:20171212015213j:plain

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

B_i の最大の約数は B_i 自身である。 A_iB_i で割り切れるなら、B_iA_iB_i の最大公約数になる

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

f:id:DarkCrowCorvus:20171212015438j:plain

よって、A_iB_i の最大公約数は、そのまま 初めの AB の最大公約数になる

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

上で求まった最大公約数を使って 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つ以上の数の最大公約数は、まずその中のどれか 2つの数から ユークリッドの互除法によって 2つの数の最大公約数を求め、

その数と、また別の残っている数を使って ユークリッドの互除法によって3つの数の最大公約数を求め… を繰り返すことによって求まる。

3つ以上の数の最小公倍数を求めるために、ユークリッドの互除法を使うサンプルは、今回見つけることができなかった。

最小公倍数を求める対象が3つ以上になる場合は、「割れるだけ割ってみる」または「素因数分解を利用する」の記事で紹介した方法を使って解くのがよろしそう。 

 


 最大公約数と最小公倍数の求め方を、
自分の納得がいくまで調べてみたつもり。

ユークリッドの互除法は、この用途とは別に
1次不定方程式の解を求めるためにも利用できるらしい。

その辺の理屈を調べてみるのは、また今度気が向いた時にでも (やらない)


参考にした書籍/サイトさん

書籍
なっとくする群・環・体 (Amazon)

 
最小公倍数/最大公約数
最大公約数と最小公倍数