実践演習 整数系

素数が無限に存在することの証明【1973年度 大阪歯科大学ほか】

例題はこちら(画像をクリックするとPDFファイルで開きます。)

素数が無限に存在することは紀元前から分かっていたことです。

ユークリッドの有名な数学書である原論での証明が有名で、歴史的内容を含む問題であり、思考力を試すというよりは、教養的側面の強い話題です。

現在、様々な証明法が知れ渡っていますが、ここではユークリッドの考えを基にした背理法による証明と、2006年に発表されたフィリップ・サイダック氏による証明を紹介します。

(以下ネタバレ注意)

+ クリック(タップ)して続きを読む

背理法による証明

以下の証明は厳密にはユークリッドの示した方法とは異なるようですが、骨格は同様です。

証明1

\(n\) を正の整数とし、素数が \(n\) 個しかないと仮定する。

その \(n\) 個の素数を小さい方から

\(p_{1}\) ,  \(p_{2}\) ,  \(\cdots\) ,  \(p_{n}\)

とする。

このとき

\(P=p_{1}p_{2}\cdots p_{n}+1\)

という数 \(P\) を考える。

\(P\) は \(p_{1}\) ,  \(p_{2}\) ,  \(\cdots\) ,  \(p_{n}\) のどれとも異なる。

素数は \(p_{1}\) ,  \(p_{2}\) ,  \(\cdots\) ,  \(p_{n}\) しかないと仮定していたことから、\(P\) は合成数ということになる。

合成数ということは \(P\) は \(p_{1}\) ,  \(p_{2}\) ,  \(\cdots\) ,  \(p_{n}\) のどれかで割り切れることになる。

しかし、\(P=p_{1}p_{2}\cdots p_{n}+1\) という \(P\) の定め方から \(P\) は

  • \(p_{1}\) ,  \(p_{2}\) ,  \(\cdots\) ,  \(p_{n}\) のどれで割っても \(1\) 余る

ということになり、矛盾する。

よって、仮定は誤りで、素数は無数に多く存在する。

フィリップ・サイダック氏による証明

2006年にフィリップ・サイダック氏が非常に簡潔な証明を発表しました。

  • \(n\) ,  \(n+1\) という連続 \(2\) 整数が互いに素

という大学入試でもよく決め手となる基本事項を用いた証明です。

証明2

\(n\) を \(2\) 以上の整数とする。

\(N_{1}=n(n+1)\)

と定めると、\(n\) ,  \(n+1\) は互いに素であるため、

  • \(N_{1}\) は少なくとも 2 種類の素因数 \(p_{1}\) ,  \(p_{2}\) をもつ。

次に

\(N_{2}=N_{1}(N_{1}+1)\)

と定めると、

  • \(N_{1}\)が素因数\(p_{1}\) ,  \(p_{2}\) をもつ

\(N_{1}\) ,  \(N_{1}+1\) は互いに素であるため、

  • \(N_{1}+1\)は \(p_{1}\) ,  \(p_{2}\) 以外の素因数 \(p_{3}\) をもつ

これより

\(N_{2}\) は少なくとも 3 種類の素因数 \(p_{1}\) ,  \(p_{2}\) ,  \(p_{3}\) をもつ。

以後、同様の操作を繰り返すことにより、任意に多くの素因数をもつ数が得られることになり、素数が無数に存在する。

類題について

類題はこちら(画像をクリックするとPDFファイルで開きます。)

\(6n-1\) という形の素数が無数に存在するということを示す問題です。

例題の知識的側面を基に、誘導を活用する力も必要です。

例題の解答はコチラ

類題の解答はコチラ

-実践演習, 整数系
-,

© 2022 MathClinic