4n+1と4n-1で表される素数の無限性
(1)$\ \ $素数の無限性
$素数が無数あることは、ユークリッドの原論に証明があるが、背理法を用いた証明方法がすてきです。$
$(証明)$
$素数は有限個とすると、最大の素数があるからそれをp_nとし、素数のすべてを順にp_1,p_2, \cdots , p_n とする。$
$\qquad P=p_1 \times p_2 \times \cdots \times p_n +1 $
$は、p_nより大きく、Pをp_1で割っても、p_2で割っても、\cdots 、p_nで割っても1余る。$
$すなわち、Pは1とPでしか割り切れない数だから素数である。$
$Pは、p_nより大きい素数だから、p_nが最大の素数に矛盾する。$
$したがって、素数は無限にある。$
$私事で恐縮ですが、この証明を初めて学んだのは中学1年のときでした。$
$わずか数行のこの証明が教科書に載っていたかどうかは記憶にありませんが、先生がその証明を$
$説明したときはよく理解できませんでした。$
$でも、50年以上経った今でも鶴岡先生のお名前とそのときの教室の空気が鮮明に残っています。$
$すべての自然数は、nを自然数として、4n,\ 4n+1,\ 4n+2,\ 4n+3\ \ と表されますが、$
$4n\ と\ 4n+2\ は素数ではありませんので、素数は\ 4n+1\ か\ 4n+3\ になります。$
$(1)の証明は、4n+1 \ で表される素数の集合 \ P \ と \ 4n+3 \ で表される素数の集合 \ Q \ の和集合 \ P \cup Q \ の要素が$
$無数あることを証明したものであるから、集合 \ P \ と集合 \ Q \ の要素がそれぞれ無数あるとはいえません。$
(2)$\ \ $4n+1で表される素数の無限性
$このタイプの素数は、5,\ 13,\ 17,\ 29,\ 37,\ 41,\cdots \ がありますが、有限個でしょうか、無限個あるのでしょうか。$
$そこで、有限個とすると矛盾がおこることを示します。$
$有限個とすると最大の素数が存在するからそれを \ \alpha とし、次のような数Aを考えます。$
\begin{eqnarray*} A &=&(2\times 5 \times 13 \times 17 \times \cdots \times \alpha)^2+1\\ &=&4(5 \times 13 \times 17 \times \cdots \times \alpha)^2+1\\ \end{eqnarray*} $Aは明らかに \ 4n+1 \ で表される数です。$
(i)$\ \ Aが素数ならば、\alphaより大きな素数が存在することになり矛盾します。$
(ii)$\ \ Aが素数でない(合成数といいます)ならば、Aは奇数だから奇数の素因数pをもちます。$
$\hspace{3em} x=2\times 5 \times 13 \times 17 \times \cdots \times \alpha \ \ \ とおくと$
$\hspace{3em} A=x^2+1 \ \ で、これがpの倍数となるから$
$\hspace{3em} x^2+1 \equiv 0 \quad (mod \ \ p)$
$\qquad 平方剰余相互法則の第1補充法則$$(相互法則を参照)$
$\hspace{5em} \big(\cfrac{-1}{p}\big) \equiv (-1)^{\tfrac{p-1}{2}}$
$\qquad は、\cfrac{p-1}{2}=2n\ \ のとき すなわち p=4n+1 \ \ のとき \big(\cfrac{-1}{p}\big) \equiv 1 \ \ となってxは解をもちます。$
$すなわち Aは奇素数 \ p=4n+1 \ を素因数にもつことになります。$
$pは \ \ 5,\ 13,\ 17,\ \cdots , \ \alpha \quad のいずれかです。$
$一方、A=(2\times 5 \times 13 \times 17 \times \cdots \times \alpha)^2+1 \ \ をpで割ると余りが1になるから、Aはpで割り切れませんので矛盾します。$
(i),(ii)$より、4n+1で表される素数は無限にある。$
(3)$\ \ $4n-1で表される素数の無限性
$自然数 \ 4n+3 \ は \ 4n-1 \ といっても同じです。$
$このタイプの素数が有限個とした場合、やはり矛盾することを導きます。$
$有限個ならば最大の素数があるので、それを\beta とし、\beta 以下のすべての素数をつかって$
$\qquad B=2^2 \times 3 \times 5 \times \cdots \times \beta -1$
$を考える。これは \ 4n-1 \ タイプの数です。$
(i)$Bが素数ならば、\beta \ \ より大きな素数が存在することになり、\beta \ が最大素数であることに矛盾します。$
(ii)$Bが素数でなく、合成数のとき$
$\quad 4n+1 \ と \ 4n-1 \ のタイプの数の積は$
$\qquad (ア)\ \ (4n_1+1)(4n_2+1)=4n+1 $
$\qquad (イ)\ \ (4n_1-1)(4n_2+1)=4n-1$
$\qquad (ウ)\ \ (4n_1-1)(4n_2-1)=4n+1$
$\quad の3通りがある。$
$したがって、4n-1\ タイプの合成数Bは \ B_1=4n-1 \ と \ B_2=4n+1 \ タイプの数の積になります。$
$\quad B_1 \ はまた \ B_3=4n-1 \ と \ B_4=4n+1 \ タイプの数の積になり、$
$\quad B_2 \ はまた \ B_5=4n+1 \ と \ B_6=4n+1 \ タイプの数の積か、$
$\hspace{2em}\ \ または \ B_7=4n-1 \ と \ B_8=4n-1 \ タイプの数の積になります。$
$\hspace{5em}\vdots $
$これを繰り返して、Bを素因数分解したとき、奇数個の \ 4n-1 \ タイプの素因数が得られます。$
$そこで、この \ 4n-1 \ タイプの素因数の一つをqとします。$
$Bは\ \ 2,\ \ 3,\ \cdots ,\ \beta \ \ のいずれでも割り切れないので、Bの素因数であるqも \ 2,\ 3,\ \cdots ,\ \beta\ のいずれでも割り切れません。$
$すなわち、qは\beta より大きい \ 4n-1 \ タイプの素数になります。$
$これは、\beta \ が最大の素数であることに矛盾します。$
(i)(ii)$より、4n-1 \ タイプの素数は無限にある。$
メインメニュー に戻る