素因数分解（連除法・はしご算）と最大公約数・最小公倍数

例えば12と18の、最大公約数と最小公倍数を求める方法として、連除法（はしご算）と呼ばれる方法があります（単に素因数分解ということもあります）。

12と18を一番小さい素数の2でわり（普通のわり算と違って横棒を数字の下に書きます）、わった答えの6と9を、12と18の下に書きます。

さらに、6と9を素数の3でわり、わり算の答え2と3を、6と9の下に書きます。

2と3をわれる数は1以外にないので（1は素数ではありませんし、残った2と3が素数なので）これで終わりです。

このとき、左の列の2と3をかけた2×3=6が12と18の最大公約数です。

また、左の列の2と3と、下に残った2と3をかけた、(2×3)×(2×3)=6×6=36が、12と18の最小公倍数です。

★なぜ、この方法で最大公約数と最小公倍数が求められるのか？

12と18の両方が2×3の6でわり切れて、12=6×2、18=6×3とわかったので、12と18のどちらもわれる6が最大公約数です（6以上の大きい公約数は考えられません）。

また、最大公約数の6に、最後に残った2と3をかけた6×2×3は、12(=6×2)と18(=6×3)の両方の倍数になっているので最小公倍数です（6×2×3より小さい公倍数は考えられません）。

また、例えば24と36だと、

となり、最大公約数は2×2×3=12であり、最小公倍数は(2×2×3)×(2×3)=12×6=72です。

以上のような、2つ以上の数を、どちらもわれる数でわっていく方法のことを、
2つ以上の数（連）を、わり算（除法）するので、連除法
また、はしごのように横棒がつながっているので、はしご算
と呼びます。
（素数の約数でわって分解するので、素因数分解ともいいます。）

★最大公約数と最小公倍数で重要なこと

24と36の場合、どちらの数も2×2×3=12でわることができました。
24=12×2、36=12×3でした。

共通部分の12が最大公約数で、共通部分に2と3をかけた12×2×3が最小公倍数です。

つまり、
A=a×b
B=a×c
のとき、
最大公約数はa
最小公倍数はa×b×c
です。

このとき、bとcの両方をわることができる1以外の数はもうありません。

1以外の公約数がないこと（1以外の、同じ数ではわれないこと）を、bとcは「互いに素（たがいにそ）である」といいます。

★よく出題される応用問題

例題：ある数と、30の、最大公約数が6で、最小公倍数が90でした。ある数はいくらですか。

（解き方）
2つの数がa×bとa×cのとき、最大公約数はa、最小公倍数はa×b×cです。

この問題だと、最大公約数が6ということから、ある数と30の共通部分は6だということがわかります。

ある数=6×□
30=6×5

最小公倍数の90は、6×□×5となるはずです。

最小公倍数の90=6×□×5
90を6×5=30でわると90÷30=3だから、□=3だとわかります。

以上より、ある数は、6×3=18です。