【数学を学び直す】〈整数#2〉素因数分解
前回は最小公倍数、最大公約数について話した
今回はそれらを簡単に調べるための方法を探る
素因数分解
倍数・約数はともにかけ算（わり算）に関するもの
それなら整数をかけ算の形にすることで求めやすくなりそう
ある整数を素数の積の形にすることを
素因数分解という
やり方はひたすら素数で割れるか調べる
12を素因数分解する
①
12は2で割れて12=2×6
6は2で割れて6=2×3
それ以上は割れない
12=2×2×3
=2²×3
基本はこのしらみつぶし
②
12=3×4
=3×2×2
=2²×3
ぱっと見て何掛ける何かがわかればこれでも良い
素因数分解で登場する数を素因数という
12の素因数は2と3
問題1
次の数を素因数分解せよ
36,60,90,126,256
素因数分解で約数を求める
素因数分解を使って、まずは約数を求めてみる
12の約数とは
12=a×整数
と表せるaである
12=2²×3であるので
12=2×(2×3)
や
12=4×3
とすれば2,6,4,3がそれぞれ約数となることがわかる
そうなるような数は、2を2個以下、3を1個以下かけたものである
具体的には
2⁰×3⁰=1
2¹×3⁰=2
2²×3⁰=4
2⁰×3¹=3
2¹×3¹=6
2²×3¹=12
の6つ
ここからさらに約数の個数もわかる
2の指数は0個、1個、2個の3通り
3の指数は0個、1個の2通り
合計3×2=6個の約数がある
さらに約数を全部足してみると
2⁰×3⁰+2¹×3⁰+2²×3⁰
+2⁰×3¹+2¹×3¹+2²×3¹
=(2⁰+2¹+2²)(3⁰+3¹)
=7×4=28
実際1+2+3+4+6+12=28となる
これは他の整数に関しても同じことが言える
整数aが
$${a=p_1^{i_1}×p_2^{i_2}×…×p_n^{i_n}}$$
と素因数分解できるとき
aの約数の個数は
$${(i_1+1)×(i_2+1)×…(i_n+1)}$$
aの約数を全部足すと
$${(p_1^0+…+p_1^{i_1})×…×(p_n^0+…+p_n^{i_n})}$$
約数を足すといえば完全数
完全数とは、自分自身以外の約数を足すと自分自身になる数のこと
例えば、6の約数は1,2,3,6の4つで
そのうちの6以外を足すと6になる
つまり約数を全部足すと元の数の2倍になる
完全数を表す1つの式がある
興味がある方は証明してみてほしい
（因数分解、等比数列の和の知識が必要）
$${2^p-1}$$が素数なら$${2^{p-1}(2^p-1)}$$は完全数
問題2
それぞれの数の約数の個数、約数の総和を求めよ
47,172,91,188,119
素因数分解で最大公約数を求める
約数の話をしたので、最大公約数から話をしていく
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
が最大公約数
90と105なら
90=2×3²×5×7⁰
105=2⁰×3×5×7
2⁰×3×5×7⁰=15
が最大公約数
問題2
次の2つの数の最大公約数を求めよ
46と84
15と48
63と91
57と73
28と78
素因数分解で最小公倍数を求める
次に最小公倍数を求める
6と8の最小公倍数は
6の倍数の中で8の倍数である数
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
そうすることで必ずどちらの倍数にもなる
つまり、最小公倍数は
それぞれの素因数の指数が大きい方をかけることで求められる
90と105の最小公倍数
90=2×3²×5
105=3×5×7
それぞれの素因数で指数が大きい方は
2,3²,5,7
2×3²×5×7=630
問題2
次の2つの数の最小公倍数を求めよ
46と84
15と48
63と91
57と73
28と78
最小公倍数と最大公約数の関係
最小公倍数と最大公約数を求めているうちに
なんとなく法則性に気づいた人もいると思う
互いに素な2つの数であれば
最小公倍数はそれぞれのかけ算
互いに素でないなら
それぞれかけ算して最大公約数で割ると
最小公倍数になる
2と3は互いに素で、最小公倍数は6
6と8は最大公約数は2で、最小公倍数は24
これからそれを定式化する
ここでは6と8を例にする
最小公倍数は24
最大公約数は2
6=2×3
8=2³
指数の大きい方を取ってきたのが24
指数の小さい方を取ってきたのが2
2つをかけると6と8の素因数全てをかけることになる
24×2=6×8=48
これを一般化すると
aとbの最小公倍数をL、最大公約数をGとすると
ab=GL
ここでaとbが互いに素ならG=1なので
L=ab
また
L=ab/G
オンラインで数学を教えてます
解答
問題1
47素数
172=2²×43
91=7×13
188=2²×47
119=7×17
問題2,3
46=2×23
84=2²×3×7
最大公約数は2
最小公倍数は1932
15=3×5
48=2⁴×3
最大公約数は3
最小公倍数は240
63=3²×7
91=7×13
最大公約数は7
最小公倍数は819
57=3×19
73は素数
最大公約数は1
最小公倍数は4161
28=2²×7
78=2×3×13
最大公約数は2
最小公倍数は1092
この記事が気に入ったらサポートをしてみませんか？