【整数#4】素因数分解と最小公倍数・最大公約数

〈素因数分解で最大公約数を求める〉

前回約数の話をしたのでこっちからの方がわかりやすい

6と8の最大公約数を求める

6=2×3

8=2³

こうしてみると一目瞭然

2つとも割り切る最大の数はもちろん2

90と105の最大公約数

90=2×3²×5

105=3×5×7

2つとも割り切る最大の数は3×5=15

それぞれの素因数で指数が小さい方をかけ算すると最大公約数が求められる

6=2×3

8=2³×3⁰

と捉えてやると

2の指数が小さい方は2

3の指数が小さい方は3⁰

2×3⁰=2

が最大公約数

問題

次の2つの数の最大公約数を求めよ

46と85

15と48

63と96

57と73

29と78

〈素因数分解で最小公倍数を求める〉

6と8の最小公倍数を求める

答えは24とわかっているがその導出方法を変える

6の倍数は整数nを使って6n

6と8をそれぞれ素因数分解すると

6=2×3

8=2³

6の倍数は

2×3×n

これが8の倍数になるためには

nが2²の倍数になっていればいい

つまりn=2²m=4mとして

2×3×2²×m=24m

これが6と8の公倍数

そのうち最小の数はもちろんm=1の時で24

（8の倍数が6の倍数になる場合を考えても同じ）

結果だけ見ると2³×3=24と出た

6=2×3

8=2³

それぞれの素因数で指数が大きい方をかけ算した

2と2³の比較で2³

3と3⁰の比較で3

2³×3=24

そうすれば必ずどちらの倍数にもなる

まとめると

aとbの最小公倍数は

aとbのそれぞれの素因数の指数が大きい方を掛け算することで求められる

90と105の最小公倍数

90=2×3²×5

105=3×5×7

それぞれの素因数で指数が大きい方は

2,3²,5,7

2×3²×5×7=630

問題

次の2つの数の最小公倍数を求めよ

46と85

15と48

63と96

57と73

29と78

これまで最小公倍数と最大公約数を求める問題で互いに素な2つの数であれば最小公倍数はそれぞれのかけ算になっていた

2と3は互いに素で最小公倍数は6

7と10は互いに素で最小公倍数は70

今回はそれを定式化する

ここでは6と8を例にする

最小公倍数は24

最大公約数は2

6=2×3

8=2³

の大きい方を取ってきたのが24

小さい方を取ってきたのが2

2つをかけると6と8の素因数全てをかけることになる

2×24=6×8=48

これを一般化すると

aとbの最小公倍数をL、最大公約数をGとすると

ab=GL

ここでaとbが互いに素ならG=1なので

ab=L

最小公倍数がそれぞれの積になる

前回

次回