素数

素数は「約数が $2$ つしかない正の整数」と言うこともできます。

具体例

$3$ は $1$ と $3$ でしかわりきれないので素数。
$11$ は $1$ と $11$ でしかわりきれないので素数。

$6$ は $1$ と $6$ 以外に、$2$ や $3$ でわりきれるので素数ではない。

素数を小さい順に並べると、
$2,3,5,7,11,13,17,23,29,31,37,\cdots$

素数かどうか判定する

一番簡単な素数の見分け方は、小さい素数から順番に、わりきれるか試していくという方法です。

問題

$31$ が素数かどうか判定せよ。

答え

$31$ は $2$ でわりきれない。$3$ でもわりきれない。同様に、$5$ でもわりきれない。よって $31$ は素数である

（$31$ が $7$ 以上の素数でわれるかどうかを調べる必要はありません。$7$ より大きい2つの数の積は $31$ を越えてしまうので、絶対にそのようには分解できないからです）

関連する他の用語

・$2$ 以上の「素数でない」整数を合成数と言います。合成数を小さい順に並べると、
$4,6,8,9,10,12,14,15,16,\cdots$ です。
正の整数は、「$1$」「素数」「合成数」の三種類に分類することができます。

・与えられた正の整数を、素数の積で表すことを素因数分解と言います。
例えば、$60$ を素因数分解すると、$2\times 2\times 3\times 5$ です。

・大きい数の素因数分解は難しいです。（例えば $206726803$ を素因数分解してみてください！）この難しさが、一部の暗号技術を支えています。

次回は 各桁の和が３の倍数なら３の倍数、の証明 を解説します。