n の素因数について、
以下までの数で割り切れるかどうかを調べれば、その過程で全ての素因数が分かる。ある自然数 n の約数の個数が 2 個のとき、その n を素数という。
また別の言い方をすると、 1 より大きい自然数で 1 とその数以外に約数を持たない数を素数という。
1 の約数は 1 だけであり、1 の約数の個数は 1 個であるから、 1 は素数ではない。
2 の約数は 1 と 2 だけであり、2 の約数の個数は 2 個であるから、 2 は素数である。
最小の素数は、 2 である。
素数の例 : 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , …
ある自然数 n の約数の個数が 3 個以上のとき、その n を合成数という。 1 は合成数ではない。4 の約数は 1, 2, 4 だけであり、約数の個数は 3 だから、 4 は合成数である。
最小の合成数は、 4 である。
素数は無限にある。この証明は次のように、背理法(間接証明法, 帰謬法, reductive absurdum)によって可能である。
もし素数の個数が有限だと仮定して(背理法の仮定)、素数を
{ n1 , n2 , … , ni }とする。最大の素数は i 番目の ni と表現するわけである。
その積 n1n2 … ni に 1
足した数 m
m = n1n2 … ni+1
は、n1 , n2 , … , ni のどの素数で割っても 1 余る。
gcd(m , n1n2 … ni) = gcd(n1n2 … ni , 1) = 1
mはそれらの素数とは互いに素だから、素数である。
このことは、最初に素数が有限だと仮定したことと矛盾するから、素数は無限にある。
奇素数とは、奇数の素数のこと。1 は素数ではない。偶数の素数は 2 だけである。だから奇素数は、 3 , 5 , 7 , 11 , 13 , 17 , 19 , …
2 以上のある自然数が与えられたとき、素数の積の形にすることを、素因数分解(factorization in prime factors)という。
n の素因数分解によって得た積の中の素数を、n の素因数という。
n の素因数について、以下までの数で割り切れるかどうかを調べれば、その過程で全ての素因数が分かる。
|
では、素因数分解を計算してみましょう。 |
ここでは、字が小さくなりすぎて見にくいということがないように、便宜上 pn を p[n] と表記することにする。
a を 2 以上のある自然数とする。 a を素因数分解し、同じ素数が掛け合わされている部分は累乗することにして、a = p[1]e[1]p[2]e[2] … p[n]e[n] となったとする。
すると、a の約数の全ては次のように表現できる。
a = p[1]f[1]p[2]f[2] … p[n]f[n]
, 0 ≦ f[i] ≦ e[i]
, 1 ≦ i ≦ n
p が素数ならば、 ( p - 1 ) ! ≡ -1 (mod p) である。
また、( p - 1 ) ! ≡ -1 (mod p) ならば、p は素数である。
p が素数ならば、 ( p - 2 ) ! ≡ 1 (mod p) である。
|
n! を m で割った余りを計算してみましょう。 |