自由研究ノート(仮)

とかいう名前の備忘録

最大公約数と最小公倍数を求める ~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:20180710004933p:plain

小学校で習うらしいのだけど、まったく記憶に残っていない。


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

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

f:id:DarkCrowCorvus:20171128002248j:plain

2 以上の公約数が見つけられなくなるまで、この「公約数を見つけては割る」を繰り返すと、割り残った2つの数には 1 しか公約数が残されない

1 を取ってそれまでに見つけられた公約数 (の積) に掛けても、もうそれよりも大きな公約数を作ることはできない

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

 

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

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

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

f:id:DarkCrowCorvus:20180716201227p:plain
※  "最大公約数" とは呼ばないことにする。というのも最小公倍数を求めるときの "公約数すべての積" は 場合によって 最大公約数と一致しないことがある

① 割り残りの数 2つを a,b と表すならば、上で述べた最小公倍数を求める掛け算は aGb  のように表現できる
( a{\times}G{\times}b  ... "×"は省略できる)

②「元々の数」は、G (公約数すべての積) を、a,b (割り残りの数) にそれぞれ掛けることで 各々復元することができる

f:id:DarkCrowCorvus:20180716210304p:plain

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

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

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

f:id:DarkCrowCorvus:20180716211728p:plain

また、これがきちんと最小公倍数になる。

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

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

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

{\hspace{6pt}}aG(b-n){\hspace{10pt}} ただし b \gt  (b-n) \gt  0

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

f:id:DarkCrowCorvus:20180718090610p:plain

Gb=B である。このことから、aG(b-n)B の倍数になるためには、Gを除いた a(b-n)b の倍数になる必要がある。

そのためには (b-n) によって失われるであろう「b を成すために必要な素因数」を a 側が持っていないといけない
※「素因数分解の一意性」という定理によって この理屈に至る。詳しくは 次の記事で紹介

しかし前述の通り、a,b はお互いに共通する素因数がなくなるまで割られた後の数である。したがって b を構成するために必要な素因数は a 側から一切得られず、aG(b-n) は B の倍数にはなれない

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

f:id:DarkCrowCorvus:20180723001036p:plain

f:id:DarkCrowCorvus:20180723001053p: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つ以上の数に対する最小公倍数になる

 


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

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

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

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