自由研究ノート(仮)

とかいう名前の備忘録

最大公約数と最小公倍数を求める ~1/3 割れるだけ割ってみる~


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

何となく読んでいた数学系の本で
最大公約数と最小公倍数という単語を見つけた。
たしかこれって習ったのは小学生のころだったはず…

ずっと使うことがなかったから アタリマエかもしれないけど、
どうやって求めればいいのか もう覚えていなかった。

なんだか悔しくなったので この際きっちり復習してみる。
完全に自分のための記事。

 


事前知識

 

倍数

ある数を2倍、3倍...のように
何倍かしてできる数を その数の倍数という

ある2つの数に共通する倍数を その2つの数の 公倍数 という
その挙げられる公倍数のうち 最も小さい数を 2つの数の 最小公倍数 という

約数

ある数が掛け算によって求められるとき、
その掛け算に使った "元の数" は約数と呼ばれる

ある2つの数に共通する約数を その2つの数の 公約数 という
その挙げられる公約数のうち 最も大きな数を 2つの数の 最大公約数 という

素数

自然数の中で、1 か自分自身の数でしか割ることができない数は素数と呼ばれる。

2 以上の数は、必ず素数1つ、もしくはいくつかの素数の掛け合わせによって表現できる。ここで この掛け合わせに使った "元の素数" は 素因数 と呼ばれる

1 は例外的に素数には含まれない。1 が素数に含まれてしまう場合、例えば素因数分解の結果にいくつでも ×1 を置けてしまう不都合が生じる
 ( 素因数分解については この次の記事で紹介 )

 


割れるだけ割ってみる

2つの数を共通して割れそうな数 (公約数) を見つけて、
その公約数で2つの数を割る

結果からまだ公約数が見つかるなら、
その公約数でまた2つの数を割る...のように割り算を繰り返す。

f:id:DarkCrowCorvus:20171213004258j:plain

2つの数の中に、"2" 以上の公約数を見つけられなくなるまで割り切ったところで、それまでに出た 公約数すべての積 を求めると、それが最大公約数になる

また、公約数すべての積に、"割り残った 2つの数" を掛けると、それが最小公倍数になる。

f:id:DarkCrowCorvus:20171213004333j:plain

小学校で習うはず…らしいのだけど、
もはやこれすら覚えていなかった

 

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

2つの数をある公約数で割った結果から、まだ公約数が見つかるのであれば、その見つかった 2つの公約数の積から、より大きな公約数を作れることがある

f:id:DarkCrowCorvus:20171128002248j:plain

しかし、前述の割り算の繰り返しの結果、割り残った 2つの数には、もう 1 しか公約数が残されていない

1 をそれまでに出た公約数の積に掛けても、もうそれ以上大きな公約数を作ることはできない。

したがって、2 以上の公約数がなくなるまで 2つの数に対する割り算を繰り返した末に、その中で見つけられた公約数すべての積 を求めるとそれが 最大公約数 になる。

 

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

見つけられた公約数すべての積 に、割り残った2つの数を掛けた結果が、元々の2つの数の最小公倍数になる。

"見つけられた公約数すべての積" のことを、ここでは G と呼ぶことにしてみる

なお、この最小公倍数を求めるときの "公約数すべての積" は、ちょうどそれが 最大公約数 にならない場面がある ため注意。これについての説明はまたあとで

① 割り残った 2つの数を a,b と表すならば、
上で述べた最小公倍数を求める掛け算は

aGb  のように表現できる
( a{\times}G{\times}b  ... "×"は省略できる)

②「元々の数」は、割り残った数 a,b に対して、見つけられた公約数すべての積 G を掛けることによって、それぞれ復元することができる

f:id:DarkCrowCorvus:20171129004347j:plain

② の「元々の数」2つをそれぞれ A,B と表し、
① の最小公倍数を求める掛け算を整理すると

{\hspace{6pt}}(aG)b=Ab つまりはそれが Ab
{\hspace{6pt}}a(Gb)=aB つまりはそれが Ba 倍 

よってこれは 元々の数 A の倍数であり、元々の数 B の倍数。
つまりこの掛け算によって求まる数は、元々の数 A,B の公倍数になることがわかる

f:id:DarkCrowCorvus:20171129002721j:plain

また、これがきちんと最小公倍数になる。
( 以下は 先の「素因数分解を利用する」の記事を見た後の方が理解がしやすいかもしれない) 

まず、2 以上の公約数が見つからなくなるまで 割り切られた後の 2つの数 a,b は、言い換えれば、お互いに共通する素因数がなくなるまで割り切られた 2つの数である。

先ほどの掛け算 aGb について、

aG=A である。ここでたとえば、aG 側をそのままに、b を 1ずつ減少させることによって、Aの倍数であることを維持しつつ、B の倍数にもなる より小さな公倍数

{\hspace{6pt}}aG(b-n)

を作れないかを考えてみる。

f:id:DarkCrowCorvus:20171130024249j:plain

Gb=B である。このことから、b を減少させた時に aG(b-n)B の倍数になるためには、少なくとも、その減少によって失われるであろう 「b を成すために必要な素因数」を a 側が持っていないといけない

しかし前述の通り、a,b はお互いに共通する素因数がなくなるまで割られた数である。そのため b を構成するために必要な素因数は a から一切得られない。

よって aGb において それが公倍数であるためには、今よりも b を小さくすることはできない。

f:id:DarkCrowCorvus:20171224104719j:plain

a を減少させる (a-n)Gb によって、より小さい公倍数を見つけようする試みも、同様に無効である。

結局 aGb よりも小さい数は、元々の2つの数 A,B のどちらか片方の倍数にはなりうるが、公倍数になることはできない。

見つけられた公約数すべての積 G に 割り残った 2つの数 a,b を掛けた結果が、たしかに 最小公倍数 ということになる。


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

f:id:DarkCrowCorvus:20171201001955j:plain

3つ以上の数の最大公約数を求める場合、その 3つ以上の数すべてを共通して割れる数 (公約数) を見つけて割り、また見つけて割りを繰り返す。

割り切ったそれらの数すべてに共通する 2 以上の公約数 を見つけられなくなったところで、それまでに出現した公約数すべての積を求めれば、それが その3つ以上の数に対する最大公約数になる

f:id:DarkCrowCorvus:20171201005900j:plain
一方、3つ以上の数の最小公倍数を求める場合、割り算の仕方は、最大公約数を求めるときと若干異なる。

3つ以上の数に対して 前述の割り算の繰り返し、それらすべてに共通する公約数を見つけられなくなっても、そのうちのどれか2つ以上の数の中に まだ公約数を見つけられるのであれば、それらの数に対して 見つけられた公約数による割り算を行う

この割り算を、どの数の組み合わせからも、2 以上の公約数を見つけられなくなるまで 繰り返す。その結果、出現した公約数すべてと、割り残った数すべてとの積を求めれば、それが 3つ以上の数に対する最小公倍数になる

このとおり、3つ以上の数の最小公倍数を求めるときの "見つけられた公約数すべての積" は、ちょうどそれが 最大公約数になるとは限らない。

 


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

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

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

3つ以上の数の公倍数・公約数|算数をしよう|ACTABA