自由研究ノート(仮)

とかいう名前の備忘録

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

2018/08/07 微編集
最大公約数と最小公倍数を求める ~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 の最大公約数でもある。

f:id:DarkCrowCorvus:20180805200510p:plain

■ 証明..

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:20180805210427p: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:20180731062839g: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つ以上の数の中で一番小さな数を使って、その他の数を割り、そのあまりの数で元の数を置きかえる。

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

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

f:id:DarkCrowCorvus:20180807020158g:plain


もしくは、3つ以上の数の中のどれか 2つの数から 前述のユークリッドの互除法によって 2つの数の最大公約数を求め、

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

f:id:DarkCrowCorvus:20180805183330g:plain


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

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

 


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

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

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


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

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

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

最大公約数と最小公倍数を求める ~2/3 素因数分解を利用する~


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

 

ここでは 素因数分解 を使って
最大公約数と、最小公倍数を求める方法を勉強する

 


素因数分解を利用する

前の記事の事前知識で述べた通り、2 以上の数は素数1つ、またはいくつかの素数の掛け合わせによって表現できる

ここで、2 以上のある数を X
それから抽出できる素因数を p としたとき
それらの関係を

{\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\times}p_4{\cdots}

のような 掛け算の式で表現することを 素因数分解 と呼ぶ

f:id:DarkCrowCorvus:20171202081223j:plain

この素因数分解を使って2つの値の最大公約数と最小公倍数を求める。

■求め方..
2つの値を素因数分解する。

見つかった素因数のうち、同じ素因数を 指数 を使ってまとめる。
2つの数の素因数分解の結果は、どちらも次の通りに表現できるようになるはず

{\hspace{6pt}}X=(p_1)^{r1}{\times}(p_2)^{r2}{\times}(p_3)^{r3}{\times}(p_4)^{r4}{\cdots}

f:id:DarkCrowCorvus:20171202205657j:plain

その後、2つの式を縦に並べて、同じ素因数の「指数が小さい方」を片側に、「指数が大きい方」をもう片側に寄せる。

f:id:DarkCrowCorvus:20171202222530j:plain
なおここでは、片方にあって、もう片方にはない素因数が存在する場合、
ない方の式でその素因数を (p_i)^{0} のように表現する

そうしてできた指数の小さい方を集めた式の答えが 2つの数の 最大公約数
指数の大きい方を集めた式の答えが 2つの数の 最小公倍数 になる

f:id:DarkCrowCorvus:20171202222557j:plain

 

素因数分解の一意性

これの理解のために、
先に「素因数分解の一意性」について知っておきたい

 

素因数分解の一意性とは...

ある数を素因数分解するとき、素因数の並び順を考慮しないとするならば、それを表す式はただ一通りしか存在しない..という定理

またこの「素因数分解の一意性」の理解のために、先に「ユークリッド補題」について知っておきたい

 

ユークリッド補題とは...

ある2つの数の積 ab を、
ある数 p で割り切ることができるならば、

pab
少なくともどちらか一方を割り切ることができる…という定理


この定理は一見アタリマエのように見える。数学ではこれを 自明である というらしいのだけど、実際のところこれは自明ではないらしい。

この証明のために、先に「ベズーの補題」という定理を知る必要があるらしい...が、これ以上細かく見ていくと、本題から離れすぎて何の記事だかよくわからなくなりそう。
今回は単に 「そういった定理があるから ユークリッド補題は成り立つ」とだけ覚えておいて、先に進みたい。

 

■ 証明 (素因数分解の一意性)

ある数を素因数分解した結果が、2通りになる可能性があるとする

f:id:DarkCrowCorvus:20171203152058j:plain

{\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n
\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}

ここで、片方の素因数分解p_1{\times}p_2{\cdots}」の中に含まれる、
素因数 p_1 に着目してみる。

左辺の Xp_1 を素因数にもつ。
よって p_1 の倍数であるため、
Xp_1 によって、割りきることができる \cdots

もう片方の素因数分解q_1{\times}q_2{\cdots}」は、
同じ X を成す掛け算の式である。

さきほどの「ユークリッド補題」の定理に従うならば、①によって そのもう片方の素因数分解の中に、p_1 で割り切れる素因数が存在するはずである。

f:id:DarkCrowCorvus:20171203152128j:plain

ここで、p_1 によって割り切れる素因数 q_1 が見つかったとする。

 q_1 は素因数。つまり 1 か自身と同じ数でしか割り切ることができない。そして 事前知識で述べたとおり、1 は素数に含まれないため、素因数分解の中に 1 が現れることはない

よってこの要件を満たす q_1 は「q_1=p_1」ということになる。
p_2,p_3{\cdots}」についても、同じくそれらと一致する「q_2,q_3{\cdots}」を見つけられるはず

f:id:DarkCrowCorvus:20171203152212j:plain

次に p_1{\cdots}p_n すべてに一致する  q_1{\cdots}q_n を見つけられた後、まだ片方の素因数分解の中に q_{n+1}{\cdots}q_m が残る場合があるかを考えてみる

{\hspace{6pt}}X=p_1{\times}p_2{\times}p_3{\cdots}{\times}p_n
\hspace{16pt}=q_1{\times}q_2{\times}q_3{\cdots}{\times}q_m \hspace{15pt}_{(n \leq m)}

この式を満たすためには、片方の式に余分に存在する素因数 q_{n+1}{\cdots}q_m は全て 1 でなければならない。しかし前述のとおり、1 が素因数分解の中に含まれるのは不適である。

f:id:DarkCrowCorvus:20171203152234j:plain

よって双方の素因数の数は一致する (n=m)
どちらか一方が多かったり、少なかったりする場面は存在しない

これらを踏まえて、上記 2つの素因数分解の式は一致する。
素因数分解の結果は、その並び順を考慮しないならば一意になる。

 

関連する事実

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

■ 事実..

ある数 m と、その数の約数 n をそれぞれ素因数分解して

{\hspace{6pt}}m=(p_1)^{r_1}{\times}(p_2)^{r_2}{\times}(p_3)^{r_3}{\times}(p_4)^{r_4}{\cdots}
{\hspace{6pt}}n=(p_1)^{s_1}{\times}(p_2)^{s_2}{\times}(p_3)^{s_3}{\times}(p_4)^{s_4}{\cdots}

のように整列させた結果、
約数  n 側に出現する素因数の指数 s_i は、 m 側に出現する同じ素因数の指数 r_i と比べて、どれも小さいか または等しくなる (r_i {\geq} s_i)

■ 証明..

ある数 m と、その約数 n との関係を以下の式で示す

{\hspace{6pt}}m=nx\ {\cdots}

ある素因数 p を ① の各変数から引っ張り出して、
以下の通りに式を整理する。

{\hspace{6pt}}m'p^r=n'p^sa'p^t\ {\cdots}

f:id:DarkCrowCorvus:20171203212855j:plain
なお、変数に素因数 p が含まれていなくても
それを p^0 と表現して、強引に式を成せるものとする。

前述した 素因数分解の一意性 の定理によって、「=」で結ばれた 左辺と右辺の素因数分解の結果は一致する。故に左辺と右辺にそれぞれ含まれる素因数の種類と個数は等しくなければならない。

それを踏まえて、
② より素因数の指数 r,s,t を抜き出し、関係を以下の式で示す

{\hspace{6pt}}r=s+t\ {\cdots}

f:id:DarkCrowCorvus:20171203223135j:plain

ここに現れる数はすべて正の整数である。③ の式を満たすためには、n 側の素因数の指数 「s」が、m 側の素因数の指数「r」よりも小さいか、または等しくならなければならない。

これは m,n に含まれるすべての素因数 p_i に対して言える。
結果、約数 n に含まれる素因数の指数はすべて小さいか、または等しい。

逆に、ある数 m と、それよりも素因数の指数がどれも小さいか、または等しい数 n が、本当に約数 (倍数) の関係になりうるかを考える。

n は、それに「m と比べて足りていない素因数」を掛けてやることで m になれる。

この「足りない素因数」を

{\hspace{6pt}}x=(p_1)^{r_1-s_1}{\times}(p_2)^{r_2-s_2}{\times}(p_3)^{r_3-s_3}{\times}(p_4)^{r_4-s_4}\ {\cdots}

とすれば、この mn の関係を表す式はちょうど ① と一致する。

f:id:DarkCrowCorvus:20171203233306j:plain

結果、mn に約数 (倍数) の関係が成立する。

 

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

2つの数の素因数分解の結果、素因数の指数が小さい (または等しい) ほうを集めた式から、最大公約数が求められる。

その式に含まれる素因数は、元の2つの数と比べてどれも指数が小さい、または等しくなるため、前述の 事実 に従って、その式から成る数は、2つの数にとっての約数 (公約数) になる

またその式から成る数が、2つの数の公約数であるためには、式中のどの素因数の指数もそれ以上大きくすることができない。

たとえば、今よりも大きな公約数を作ろうとする時、その数の少なくとも1つ以上の素因数の指数は、もとの公約数の同じ素因数の指数よりも大きくなる

しかし、どの素因数の指数が今より大きくなっても、もとの2つの数のうち、少なくともどちらか一方の同じ素因数の指数よりも大きくなってしまう

f:id:DarkCrowCorvus:20171205010943j:plain

前述の事実「約数なら素因数の指数がどれも小さいか等しい」を満たさなくなるため
 その一方、あるいは両方の約数になることができず、結果 公約数ではなくなる

素因数の指数が小さい (または等しい) ほうを集めた式から成る数について、結局それより大きな公約数を作ることはできないため、それが 2つの数にとっての最大公約数になる

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

2つの数の素因数分解の結果、素因数の指数が大きい (または等しい) ほうを集めた式から、最小公倍数が求められる

その式に含まれる素因数は、もとの2つの数と比べてどれも指数が大きいか、または等しい。一つ上の項で解説した 事実 に従い、もとの2つの数は その式から成る数の約数、よってその式から成る数はもとの2つの数の倍数 (公倍数) になる

またその式から成る数が、2つの数の公倍数であるためには、式中のどの素因数の指数も今より小さくすることができない。

理屈は上の項で説明したのと大体同じ。
今よりも小さな公倍数を作れないため、結果 それが 最小公倍数 になる


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

どちらも考え方は 2つの数に対して求めた時とあまり変わらない。

3つ以上の数をそれぞれ素因数分解して、その中から各素因数の指数が一番小さいものを寄せた式から、最大公約数 を求められる

また、各素因数の指数が一番大きなものを寄せた式から、最小公倍数 を求められる

f:id:DarkCrowCorvus:20171205090754j:plain

 


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

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

 
素因数分解の一意性

素因数分解の一意性とその証明について | 高校数学の美しい物語

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

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

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