素数の性質
1.素数の性質と合成数
素数の性質
ある自然数をn、ある素数をpとする。
- 1とp以外の整数で割り切れない。
- \(nが\sqrt{n}\)を超えない最大の整数以下の全ての素数で割り切れなければ、\(n\)は素数となる。
これを利用して素数を見つける方法が「エラストテレスの篩」 - 無限に存在する。
合成数とは
1より大きい整数で素数でない数。
合成数は、ただ1通りの方法で素数の積の形の表すことが出来る。（素因数分解）
2.約数と素数
約数と素数
\(自然数Nを素因数分解したものを、N=p^a q^b \dots \dots r^c\)とする。
Nの全ての約数は、多項式
\(\begin{align} & (1+p+p^2 + \dots +p^a)(1+q+q^2 + \dots + q^b) \\ & \dots (1+r+r^2 + \dots +r^c) \end{align}\)を展開した時の各項である。
例題1
450の正の約数の個数及び約数全部の和を求めよ。
回答).\(450 = 2 \times 3^2 \times 5^2 \)
450の約数は、
\((1+2)\cdot (1+ 3+ 3^2) \cdot (1 + 5 + 5^2)\)を展開した時の各項であるから、約数の個数は
\(2\times 3 \times 3 = 18 個\)約数の和は
\(\begin{align}(1+2)\cdot (1+ 3+ 3^2) \cdot (1 + 5 + 5^2) &= 3\cdot 13 \cdot 31 \\ &= 1209 \end{align}\)
3.完全数
完全数
自然数a以外の約数(1を含む)の和がaに等しい時、自然数aを完全数という。
例).28について
28を因数分解すると、
\(28 = 2^2 \times 7\)ゆえに28の28以外の全ての約数の和は
\((1+2+2^2)(1+7) -28 = 28\)よって28は完全数である。
