実践演習 整数系

素数の階乗【ウィルソンの定理】【素数砂漠】

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

素数の階乗を用いた興味深い性質について見ていきます。

問題のオチは素数が無限に存在するということの証明で、この事実の証明自体は

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

例題はこちら(画像をクリックするとPDFファイルで開きます。) 素数が無限に存在することは紀元前から分かっていたことです。 ユークリッドの有名な数学書である原論での証明が有名で、歴史的内容を含む問題で ...

続きを見る

で扱っていますが、アプローチは素数の階乗を用いたものです。

上の記事は素数の積を用いたアプローチですが、本問は \(p!\) を用いたものです。

まぁ、\(p!\) の因数の中には \(p\) 以下の素数が全て入っていますから、基本的に全く別のことをやっているというわけではないでしょう。

(以下ネタバレ注意)

 

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

(1) について

\(p!\) は

\(p \cdot (p-1) \cdot (p-2) \cdot \cdots \cdot 3 \cdot 2 \cdot 1\)

であり、\(p\) 以下の全ての素数で割り切れます。

よって、\(1\) を加えた \(p!+1\) は

\(p\) 以下の素数で割った余りが \(1\)

ということになり、\(p!+1\) は \(p\) 以下の素数で割り切れないということになります。

(2) について

無限に要素が存在することを直接示すことは困難です。

そこで、方針としては背理法を思いつきたいところです。

素数全体の集合を \(P\) として、\(P\) が有限集合であると仮定します。

与えられた

「自然数を要素にもつ有限集合には最大の要素が存在する」

という命題を用いると、この集合 \(P\) には最大の要素が存在することになります。

その最大の要素を \(p\) として、\(n=p!+1\) という自然数について考えてみます。

\(n\) が素数であるならば

\(n\) が素数だとすると、\(n \gt p\) ですから、\(n\) は \(p\) より大きい素数ということになり、\(p\) の最大性に矛盾します。

\(n\) が合成数ならば

\(n\) が合成数だと、\(n\) には少なくとも 1 つ素因数が存在します。

ただ、(1) の結果から、\(n\) は \(p\) 以下の素数では割り切れません。

よって、\(n\) を割り切る素因数は \(p\) より大きいものということになり、これは \(p\) より大きな素数の存在を意味します。

したがって、これも \(p\) の最大性に矛盾します。

\(n\) が素数であっても合成数であっても矛盾するため、最初に仮定した \(P\) が有限集合であるという仮定が誤りであり、\(P\) は無限集合ということになります。

本問にまつわる事実

本問で扱った素数の階乗に関する有名な2つの事実について紹介します。

ウィルソンの定理

本問において、\(p!+1\) は \(p\) で割り切れませんでした。

しかし、

  • \((p-1)!+1\) は \(p\) で割り切れる

ということが言えます。

さらに、

ウィルソンの定理

\(p\) が素数であることと、\((p-1)!+1\) が \(p\) で割り切れることは同値である。

という同値性も言えます。

素数砂漠

今回の \(p!+1\) というような数の作り方に倣って

\((n+1)!+2 \ , \ (n+1)!+3 \ , \ \cdots \ , \ (n+1)!+n+1\)

という \(n\) 個の連続した自然数を考えます。

\(k=2 \ , \ 3 \ , \ \cdots \ , \ n+1\) に対して、\((n+1)!+k\) は全て \(k\) で括れるため、\(k\) で割り切れる合成数です。

つまり、これは

  • 任意の長さの連続合成数区間を作ることができる。

ということを意味します。

全然合成数が現れない区間ということで、この区間をよく素数砂漠と表現したりします。

解答はコチラ

-実践演習, 整数系
-

© 2022 MathClinic