素数
素数とは何か
素数とは何か
素数
2以上の自然数で，正の約数が1とその数自体のみである数を，素数という．
例えば，次のような数はみな素数である．
\[2,3,5,7,11,13,17\]吹き出し無題
1は素数に含まれないので注意しよう．
合成数
2以上の自然数で素数でないものを，合成数という．
例えば，14や60は
\begin{align} 14&=2\cdot7\\ 60&=3\cdot4\cdot5 \end{align}なので，合成数である．
素数の性質
素数の性質
素数の性質
$a,b$ を整数， $p$ を素数とする時
$ab$ が $p$ で割り切れるならば， $a$ または $b$ が $p$ で割り切れる
暗記素数の性質
素数の性質を証明せよ．
$a$ と $p$ の最大公約数は $p$ の約数であるから， $1$ または $p$ である．
もし，最大公約数が $p$ ならば， $a$ は $p$ で割り切れる．
もし，最大公約数が $1$ ならば，互いに素な数の性質より， $b$ が $p$ で割り切れる．
よって， $a,b$ のうち、少なくとも1つは $p$ で割り切れる．
素因数分解
素因数分解
素数である因数を素因数といい，自然数を素数だけの積の形で表すことを素因数分解するという．
例えば，60は
\[60=2^2\cdot3\cdot5\]と因数分解できる．
素因数分解
次の数を素因数分解せよ．
なし
上の例題から経験的に次のことがわかる．
素因数分解の一意性
合成数の素因数分解は，積の順序を考えなければ１通りに定まる．
ある数の約数の個数については次のことが成り立つ．
約数の個数
自然数 $N$ の素因数分解が， $N=p^q\cdot q^b\cdot r^c\cdots$ であるとき， $N$ の正の約数の個数は
\[(a+1)(b+1)(c+1)\cdots\]となる．
素数の個数
素数の個数
素数は無数にあることを示すことができる．
暗記素数が無数にあることの証明
素数を小さい方から並べると
\[2,3,5,7,\cdots\]である．
- $2\cdot3+1,2\cdot3\cdot5+1,2\cdot3\cdot5\cdot7+1$ が素数であることを確認せよ．
- 素数が無数にあることを示せ．