整数の中で、基本的で非常に重要な素数について紹介します。
研究の対象としてよく扱われていますが、未だに分かっていない事も多いです。
素数
自然数 \(p\) が素数(prime number)であるとは, \(p\) は \(2\) 以上であって, 正の約数が \(1\) と \(p\) のみであることをいう.
素数でない \(2\) 以上の整数を合成数(composite number)という.
例
素数を小さい順に並べると \[2,3,5,7,11,13,15,17,19,23,29,31,37,41,43,47,53,59,61,67,\ldots\] 合成数を小さい順に並べると \[4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,\ldots\] また, \(1\) は素数ではない.
ユークリッドの補題
\(a, b\) を自然数, \(p\) を素数とする.
\(p\) が積 \(ab\) を割り切るならば \(p\) は \(a\) または \(b\) の少なくとも一方を割り切る.
つまり, \(p\mid ab\) ならば \(p\mid a\) または \(p\mid b\).
証明
\(p\mid a\) ならば良い.
\(p\not\mid a\) とする. \(p\) は素数なので \(\mathrm{gcd}(p,a)=1\).
ベズーの等式より, 整数 \(x,y\) を用いて \(ax+py=1\) と書けるが,
両辺に \(b\) をかけると \(abx+pby=b\) となる.
\(p\mid ab\) かつ \(p\mid pb\) なので \(p\mid b\) が従う.
素数が無数に存在することを示しますが、
その中で素因数分解を使うので、知らない場合はこちらを参照してください。
素数が無数にあること
素数は無数に存在する.
証明
(ユークリッドによる証明)
素数が有限個しかないと仮定して, \(p_1,p_2,\ldots,p_n\) がその全てとする.
\(P=p_1p_2\cdots p_n\) とおくと, \(P+1\) は \(p_1,p_2,\ldots,p_n\) のどれでも割り切れない. よって \(P+1\) は素数であるが, これは仮定に矛盾する.
ゆえに素数は無数に存在する.
(Filip Saidakによる証明)
\(n\) を \(2\) 以上の自然数とする.
\(n\) と \(n+1\) は互いに素であるから, \(N_2=n(n+1)\) は少なくとも\(2\)つの異なる素因数を持つ.
また, \(N_2\) と \(N_2+1\) は互いに素であるから \(N_3=N_2(N_2+1)\) は少なくとも\(3\)つの異なる素因数を持つ.
この操作を続けることで、任意に多くの異なる素因子を持つ数を構成することができるので、素数は無数に存在する。
コメント