最小公倍数ってどうなってるの？すだれ算とブロックで仕組みを解説

はじめに

この記事は以下の目的で作りました。

• 算数の学び直し記事を修正していく中で、特に分かりにくい部分があったので別でまとめる
  • 変則すだれ算の最小公倍数の求め方を解説

宣伝

数学の学び直しに興味があればこちらの記事もおすすめです。

• 中学1年の数学で学ぶアルゴリズムの基礎：シリーズ第2弾

まず知っておきたい：最大公約数を求めるとは？

• 最大公約数：2つ以上の整数に共通する約数の中で最大値

ある2つの数の最大公約数を求めるには
2つの数を横と縦が1×1のブロックの集まりであると見立てる

例えば、ある数が15と3なら$15×3$のブロックとする

ブロックの横と縦の大きさを維持したまま小さいブロックを探す
縦を1としたとき横も同じだけ小さくする
3を1にするのだから$\frac 1 3$なので15は5である
すなわち$15×3$のブロックは$5×1$のブロックを横に3個と縦に3個並べたものである
＊横を1とすると$\frac 1 {15}$なので3は$\frac 1 5$になり「1×1のブロックの集まりである」という設定から外れる

大小のブロックで「縦を1としたとき横も同じだけ小さくする」ときに、どれだけ小さくしたか？
逆に言えば、横か縦について、大は小の何倍になっているか？
それが最大公約数で、この場合なら3である

つぎに大事な：最小公倍数を求めるとは？

• 最小公倍数：2つ以上の整数に共通する倍数の中で最小値

最大公約数を求めるときに使ったブロックを正方形に並べる
この正方形の1辺の大きさが最小公倍数である

$5×1$の小さいブロックが正方形になるように並べると
縦に5個並べることになる
正方形の1辺は5であると分かる
この数が最小公倍数である

$15×3$の大きいブロックが正方形になるように並べると
縦に5個並べることになる
正方形の1辺は15であると分かる
この数が最小公倍数である

大きいブロックは小さいブロックの集まりで、何倍の大きさかを示すのが最大公約数
15と3の最大公約数は3だから、最小公倍数15は最大公約数3の倍数であると分かる

この記事の本題：ある3つの数について最小公倍数を求めるには？

3つの数の公約数以外に2つの数の公約数が生じるため変則すだれ算をつかう

ある3つの数の変則すだれ算
$2\; \rparen \underline{\; 12 \quad 15 \quad 40}$
$2\; \rparen \underline{\;\;\: 6 \quad 15 \quad 20}$
$3\; \rparen \underline{\;\;\: 3 \quad 15 \quad 10}$
$5\; \rparen \underline{\;\;\: 1 \quad\;\: 5 \quad 10}$
$\;\:\; \, \;\:\;\: 1 \quad \;\: 1 \quad \;\: 2$

この例で、3つの数の公約数は1だけ。すなわち、3つの数の最大公約数は1。

3つの数で変則すだれ算を使うときは、まず小さい素数から順に、「この素数でどの数が割れるか？」を調べていく。

このとき、3つすべてが割れる場合は、その素数は段の公約数であり、3つの数の公約数である。

しかし、すべての素数で3つの数が割れるとは限らない。
2つの数しか割れない場合でも、変則すだれ算では「割れる数だけ」を割って処理を進めていく。

こうして、割れる数がなくなるまで処理を続けると、すだれは完成する。

ここでポイントなのは、「ある段に参加していない数（＝割れなかった数）」がいたとしても、その段で割られた他の数と一緒に最小公倍数を構成する際に、最終的にはその数の倍数も含まれるようになるということ。

なぜなら、下の段から「段ごとの部分最小公倍数」を計算していくと、それまでの部分最小公倍数（下の段で積み重ねてきたもの）に「段ごとの2つの数の公約数」を掛けていく構造になっている。

例えば上記の例で1段目を抜き出すと
$5\; \rparen \underline{\;\;\: 1 \quad\;\: 5 \quad 10}$
$\;\:\; \, \;\:\;\: 1 \quad \;\: 1 \quad \;\: 2$

この3つの数の最小公倍数は$5×1×1×2=10$である。
この段だけに限定すれば（2つの数の）公約数は5である。
すなわち、最大？公約数の倍数が最小公倍数である。
1辺の長さが10の正方形が完成。

「最大公約数の何倍か」という意味ではなかったのか？という疑問

2段目を追加すると
$3\; \rparen \underline{\;\;\: 3 \quad 15 \quad 10}$
$5\; \rparen \underline{\;\;\: 1 \quad\;\: 5 \quad 10}$
$\;\:\; \, \;\:\;\: 1 \quad \;\: 1 \quad \;\: 2$

1段目の最小公倍数は$5×1×1×2=10$であり、すでに公約数3で割った数であるため、この3つの数の最小公倍数は$3×5×2=30$である。
1段目の公約数は3、2段目の公約数は5であり、乗算すると公約数は15であるが「変則すだれ算の2つの数における公約数である」ことに注意が必要。
すなわち、（2つの数の）公約数の倍数が最小公倍数である。
1辺の長さが30の正方形が完成。
小さい$10×10$の正方形で大きい$30×30$の正方形を作るイメージ。

さきほどの正方形を横に3個、縦に3個並べるという意味。
この計算をすべての段が完了するまで繰り返す。

これで、「段ごとの部分最小公倍数」に「段ごとの公約数」を掛ければ「上段の部分最小公倍数」を求めることができる。

この「段ごとの公約数」を掛けるという操作によって、無視された数も、その時点での部分最小公倍数の倍数になっていると確認できる。
つまり、途中で一時的に無視していても、最終的にはすべての数の倍数になるように構成されている。

だからこのやり方で、3つの数の最小公倍数が求まる。
各段での処理が「部分最小公倍数」を積み上げる形になっているため、全体の最小公倍数を構築できることが論理的に保証されている。

さらに説明すると

少し複雑な説明にはなるが重要なこと

変則すだれ算でやっていることは
各段で2つの数の公約数を見つけていく作業である

段が終わるまで作業を繰り返したあとで何をしているのか
改めて最下段から見直してみる

$2\; \rparen \underline{\; 12 \quad 15 \quad 40}$
$2\; \rparen \underline{\;\;\: 6 \quad 15 \quad 20}$
$3\; \rparen \underline{\;\;\: 3 \quad 15 \quad 10}$
$5\; \rparen \underline{\;\;\: 1 \quad\;\: 5 \quad 10}$
$\;\:\; \, \;\:\;\: 1 \quad \;\: 1 \quad \;\: 2$

例の場合であれば3つの数の最大公約数は1だけ
それとは別に、段別に2つの数の公約数と最小公倍数を設定していくと仮定すると
まず最下段（見た目上は最下段は最後の除数なので飛ばす）の5と10の2公約数が5で最小公倍数が10である
5と10以外に3つ目の数として1が含まれるが、あらゆる倍数に対応できるので最小公倍数は変わらず10である

2段目追加で難しくなるが順を追って説明する

2段目では3と15の2公約数が3で最小公倍数が15である
ここまでの手順は最下段と同じ
3と15以外に3つ目の数として10が含まれるが、これは最下段の最小公倍数と紐付いている
そのため、実際には再帰処理が行われている
ある段の「2つの数の最小公倍数と、その下段以降の最小公倍数」の最小公倍数を求める形である
例の2段目であれば15と10にあたる

仕組み自体は正方形と同じなのだが、概念としては上記のように複雑になる

じゃあ、なぜ段ごとの公約数を乗算するだけで最小公倍数が求まっていくのか？
結論から言えば、3つの数しかないので、必ず1つは2公約数の影響を受けるからである
例えば2段目であれば2公約数は3であり、最下段の最小公倍数に乗算すれば、2段目の2つの数を網羅することに等しい
逆説的になるが、なぜなら2公約数の3で除算したものを最下段で取り扱っているから

変則すだれ算で注意すべきことは3つに集約される

1. 最大公約数や最小公倍数を求める仕組み自体は2つの数で求める場合と同じ
2. ①の用法として段別に2つの数の公約数や部分的な最小公倍数を探す形であり、全体的な最大公約数や最小公倍数とは別物であると捉える
3. ①②を踏まえたうえで、数字としては正方形的理解が可能だが、概念としては一連の流れをおさえておく必要がある

おわりに

最後まで読んでいただきありがとうございました。
また何処かでこのPublication［アルゴリズム×数学の学び直し
］を見かけたら、興味の近さがあるかもです。
Publicationのメンバー申請は遠慮なくしてみてください。
定期的に活動されている方であれば、特に縛りはありません。
申請する場合は、自己紹介とこれまでの活動内容だけTwitterでDMしてください。