【整数#3】素因数分解

最小公倍数や最大公約数をしらみ潰しで調べたくない

〈素因数分解〉

ある整数を素数の積の形にすること

やり方はひたすら素数で割れるか調べる

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

問題

次の数を素因数分解せよ

36,60,90,126,256

〈素因数分解を使って約数を求める〉

12の約数

12=a×整数（aの倍数）

と表せたらaは約数

12=2²×3

2²と3は約数になることは明らか

12=2×(2×3)

2と6が約数

2つの2と1つの3のうちいくつかをかけてできる数は約数になる

2⁰×3⁰=1

2¹×3⁰=2

2²×3⁰=4

2⁰×3¹=3

2¹×3¹=6

2²×3=12

ここからさらに約数の個数もわかる

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=a,3=bとして

a⁰b⁰+a¹b⁰+a²b⁰+a⁰b¹+a¹b¹+a²b¹

これを因数分解すると

(a⁰+a¹+a²)(b⁰+b¹)

つまり

(1+2+4)(1+3)

=7×4=28

実際1+2+3+4+6+12=28となる

約数を足し算するといえば完全数

6の約数は1,2,3,6の4つで

そのうちの6以外を足すと6になる

つまり約数を全部足すと元の数の2倍になる

この性質を使ってこんなことが言える

2^p-1が素数なら2^(p-1)(2^p-1)は完全数

証明は各自でやってみて

2^(p-1)(2^p-1)はすでに素因数分解された形

約数の総和を考えると

(1+2¹+…+2^(p-1))(1+2^p-1)

=2×2^(p-1)(2^p-1)◽︎

問題

それぞれの数の約数の個数、約数の総和を求めよ

47,172,91,188,119

前回

次回