はアルファベットの文字数である。
相互リンクサイト『素数に恋する女』の最新記事
p.1yen.jp
に登場する有名な素数公式
の証明を紹介します(上記サイトでは値を実際に計算できるExcelファイルをダウンロードできます。そして、負の数ばっかりに出会うことができるでしょう(笑))。
任意の非負整数点で素数を返すような定数でない複素係数多項式が存在しないことが証明されていますが、上記定理のように「正の値のときのみを考える」という制限をつけることによって素数を表現するような多項式が存在することを証明できます(これはHilbertの第10問題を解決したMatijasevicが本質的に示しています*1 )。
そのような具体的な素数表現多項式としてどのようなものがあるか?、変数および次数はどのようなものが取れるか?ということが気になりますが、
J. P. Jones, D. Sato, H. Wada, D. Wiens, Diophantine representation of the set of prime numbers, Amer. Math. Monthly, 83 (1976) 449-464.
で発表された多項式(上述の定理のもの)が最も有名なものだと思われます*2。
変数なので、多項式がアルファベット全てを用いて表されていることについては「そすこい」を見て始めて気づきました。
この論文で証明しているのはこの定理だけではないですが、とりあえずこの定理の証明を紹介しましょう(原論文ではDavisの論文を引用して証明を省略している部分があるので(命題1)、その点についてはこの記事をまとめた価値があると思います)。
Pell方程式に関する補題群から始めます。Pell方程式の一般論(補題1)だけこの記事では証明をつけていません。例えば高木貞治『初等整数論講義』で勉強できる気がします(難しくないですが二次体論や連分数論が関係します)。
証明. が最小非自明解であることは容易に確認できるので、Pell方程式の一般論
mathtrain.jp
の定理2よりわかる。 Q.E.D.
証明. 一般項より容易に確認出来る。 Q.E.D.
以下幾つかの補題においてを含めても「自明」とか「便宜的」に扱えば良いですが、気持ち悪い場合は
として読んでください(
は勿論整数。
についても
で上手くいくものと上手くいかないものがある)。
証明. 単調増加であることは、補題2より
が成り立つことよりわかる。後半はの漸化式を
証明. Pell方程式の形からすぐわかる。 Q.E.D.
証明. 補題2より
証明. 補題5よりはOK。
を示すために、
は
の倍数であるが、
は
で割り切れないと仮定する。このとき、
を満たすような非負整数
が存在する。すると、補題2より
が成り立つ。補題5よりは
を割り切るので、
。補題4、5より
と
は互いに素なので、
を得る。これは
が
について狭義単調増加であることに反する。Q.E.D.
証明. 一般項の公式を用いることにより
と計算できる。よって、の係数を比較することにより
を得る(この式には整数しか現れない)。の項は全て
の倍数なので所望の結果が得られる。 Q.E.D.
証明. まず補題6よりは
の倍数であることが従う。そこで、
とおこう(
は正の整数)。すると、補題7より
が言える。すなわち、。 よって、補題4より
。
は
を割り切るので主張が言えた。 Q.E.D.
証明. 漸化式よりなので数学的帰納法で示せる。 Q.E.D.
誠に遺憾ではありますが、この記事では原論文に従っては素数を表す記号としては用いません(怒)。
証明. 合同式は数学的帰納法で示せる。のときを考える。
のときは左辺と右辺は一致するので、
とする。一般項の公式から、
が成り立つので、
と評価できる。ここで、二番目の不等号は
からわかる。 Q.E.D.
証明. 補題2を用いて次のように計算できる:
証明. 補題14より
証明. が奇数のとき:
とおく。すると、
はの完全代表系をなす。補題3より
であり、補題2からなので
すなわち、が成り立つ。また、
はそれぞれ
と合同である(補題14よりわかる)。以上より、は
で全て互いに合同ではない。
が偶数のとき:
今度はとおく。このときは
がの完全代表系をなす。奇数のときと同じく
は成立(
の定義が変わっていることに注意)。従って、
でない限り奇数のケースと同様に
は全て
で互いに非合同となる。
さて、が成り立ったと仮定しよう。補題2からわかる
と比較すれば、この状況になるのはのときで、
に限る。
なので、
のときに
となることがわかる。 Q.E.D.
証明. のとき:
補題16より例外ケースでなければが言える。しかし、今は
なので、例外ケースとなるのは
のときのみ。これは
に反する。
のとき:
とする。すると、
が成り立つ。補題15より
が成り立つ。よって、補題16より例外ケースでなければが従う。
なので例外ケースは起こりえない。 Q.E.D.
証明. を
で割って、
と表す。このとき、補題15より
が成り立つ。よって、補題17よりまたは
が成り立つ。こうして、
が得られる。 Q.E.D.
よくやるように、は完全平方数を表す記号として用います。
証明. とおくと、(1)は
となるので、補題1のPell方程式がなる解を持つことがわかる。すなわち、ある非負整数
が存在して
が成り立つ。このとき、補題9より
。明らかに
なので
である。従って、補題13より
を得る(最初の不等式は例えばから分かる)。両辺を
で割ることにより、
すなわち、を得る。
後半を示す。任意の正の整数が与えられたとき、
と置いてPell方程式
を考える。ここで、
。Pell方程式は常に非自明解を持つので(一般論)、所望の
の存在がわかる。 Q.E.D.
この不等式は後で大活躍します。
証明. の証明:
(Ⅰ)〜(Ⅷ)を満たすような非負整数が存在したと仮定する。最初に
を確認する。
だと仮定しよう。すると、(Ⅱ)より
。(Ⅴ)より
。(Ⅲ)より
。(Ⅵ)より
となるが、(Ⅰ)より
なので
。よって、(Ⅰ)より
となって、(Ⅷ)と
の仮定に矛盾する。よって、
が示された。
(Ⅰ)、(Ⅱ)、(Ⅲ)、補題1、から、
が存在して
が成り立つ。示すべきことは。
(Ⅳ)よりなので、補題3より
。
(Ⅴ)より、すなわち
補題10より
(Ⅵ)より、すなわち
合わせると
が成立する。よって、補題18より
(IⅤ)より。すなわち、
。すると、補題8より
が得られる。よって、
(Ⅱ)、(Ⅳ)、(Ⅴ)よりが言えるので、補題9と合わせると
また、(Ⅶ)より、すなわち
なので、結局
が示されたことになる。
(Ⅷ)より、補題3より
であることに注意すれば、
でなければならないことがわかる。
以上で、の証明が完了する。
の証明:
と仮定する。
とすれば(Ⅰ)が成立。
とおく。すると、補題1より(Ⅱ)が満たされる。
補題7よりは
で割り切れる。また、補題2より正整数
に対して
が成り立つので、
.
として適用することによって
は
で割り切れることがわかる。すなわち、(Ⅳ)を満たす正整数
が存在することがわかった。
とすれば当然(Ⅴ)が成立する。
とすれば補題1より(Ⅲ)が成立。
より
が成り立つ(添字部分に関する単調性は一般項の公式からわかる*5 )。また、(Ⅴ)より
なので、補題10より
である。以上により(Ⅵ)を満たす非負整数
の存在がわかる。
補題3より。補題9より
。(Ⅱ)、(Ⅳ)、(Ⅴ)より
なのだから
。すなわち、(Ⅶ)を満たす非負整数
が存在する。(Ⅷ)は補題3からわかる。 Q.E.D.
証明. 命題1の条件式において、を消去すればよい。 Q.E.D.
証明. これは、Bernoulliの不等式よりわかる:
mathtrain.jp
Q.E.D.
証明. 自明。 Q.E.D.
素数である事の必要十分条件の出発点はWilsonの定理に頼ります:
証明. 有名定理(当ブログでは2015の階乗を10の502乗で割った数の一の位は? - INTEGERSでを証明しています)。
の証明は容易(対偶を取ればよい)。 Q.E.D.
最終的に多項式に向かうにあたって、階乗を消すのに次の補題が決定的に重要な役割を果たします:
証明. 仮定よりであることに注意して、二項定理より
ここで
なので、
を得る。(2)、(3)は
であることを意味している。
より、後は
を示せばよい。
なので、
に帰着される。これは次のようにして示される:
より、
証明. の証明:
が(Ⅰ)〜(Ⅵ)を満たすと仮定する。(Ⅳ)より
、(Ⅵ)より
である。
ならば(Ⅱ)より
となって、矛盾。仮定より
。よって、
が分かる。
ならば(Ⅰ)より
は
を割り切るので、それは(Ⅴ)、(Ⅵ)より
が
を割り切ることを意味する。しかし、
と
は互いに素なのであるから、それはありえない。よって、
となって、(Ⅰ)より
が確定する。
(Ⅳ)よりが成り立つ。また、(Ⅲ)に補題19を適用すると
を得る。よって、補題22より
が成り立つ( (Ⅳ)、(Ⅵ)よりである)。
一方、(Ⅱ)より
なので、とおけば
すなわち、が得られる。
も
も整数なのだから、
。
の証明:
とする。補題19より、(Ⅲ)および
を満たすような
が存在する。
、
、
としよう。この時点で(Ⅳ)、(Ⅴ)、(Ⅵ)も成立。そうして、
と定める。これは(Ⅰ)、(Ⅱ)が成り立つように定義されている。は
を
で割った商なので、非負整数。あとは
のみが示すべきものとして残っている。
現時点で補題22が使える状況になっており、
が成り立つが、の仮定より(ここで初めて使う!)、
が得られる。この二つの不等号がすなわちを言っている。 Q.E.D.
証明. の証明:
Step1 1. 〜 14. が成り立つようなが存在したと仮定する。3.に補題19の前半の主張を適用することにより、
が成り立つ(特に
および
を念頭におく)。
次に、4.と5.に補題19の前半の主張を適用することにより、
が成り立つ(特に、すなわち
も覚えておく)。
6.-7.-8.-11.より系1が発動して(、
は既に確認済み)、
が成り立ち、従って、6.より
となる。
9.は考察しているPell方程式なので、或る非負整数が存在して*6、
、
となる。
なので、11. より
が分かる。すると、補題3より
が狭義単調増加であることから
でなければならない。
これまでに分かったことから、および
であり、これらは全て整数なので
が得られる。10. よりであり、
および補題9より
(5)と合わせることによりが分かった。これより、特に
となる。
Step2 (4)より、。また、
ならば
であるし、
ならば
なので、どちらにせよ
が成り立って、
まとめると、
12. より
であるが、補題12によれば
すなわち
が成り立ち、
ということになる。故に、(6)と合わせれば
が示された。
Step3 再び、(4)を用いれば(さっきとはピックアップする場所を変える!)、、
が分かる。Step2では
なる条件から
を導出したのであるから、であったことから
を得る。しからば、Step2と同様にして、13. から
補題12より
すなわち、
が成り立ち、
が得られる。Step3の初めに並べた不等式から
が示された。
Step4 (4)を用いれば、、
が得られる(
に注意)。また、(7)より
であることに注意すれば、
であることから
が示される。三度目なので詳述する必要なく、14. および補題12から
が結論付けられる(ただし、倍することに注意)。
Step5 1.-2.-3.-(7)-(7)-(9)より、命題2が発動して
が従う。すなわち、が成り立つので、Wilsonの定理によって
は素数でなければならない。
の証明:
が素数であると仮定する。すると、Wilsonの定理によって非負整数
が存在して
が成り立つ。このとき、命題2によって1.-2.-3. および
が成り立つような非負整数が存在することが分かる。
として4. が成立する。補題19より5. が成立するような非負整数
であって
を満たすものが存在する。
としよう。すると、系1により6.-7.-8. が成立するような非負整数
が存在する。
、
とする。Pell方程式の解なので9. が成立。
補題9より、であって、補題3より
なのだから、10. を満たす非負整数
の存在が分かる。
となって、11. を満たすような非負整数の存在が分かる。
さて、現時点で3.〜5.が成立しているのだから、証明の前半の議論がそのまま適用できて
が成立する。従って、および(10)に注意して、補題12(特に後半の主張)より12.-13.-14.を満たすような非負整数
が存在することが分かる。 Q.E.D.
定理1の証明
定理2の1. 〜 14. の(右辺)-(左辺)をそれぞれとおく(全て多項式)。ただし、
のみ
に置き換える(好みの問題であるが、こうすると
も非負整数として扱える)。このとき、
変数
次の多項式
を
と定義する(である)。 すると、定理2より非負整数
に対して
が素数となるための必要十分条件は
で、これは
と同値である。しかし、
かつは整数値をとるので、結局
が成り立つ。 更に、この条件が成り立つとき
素数
を作ろう!
具体的な多項式を作れるということが重要な点であって、素数生成機としての実用性がないことは構成からも明らかです(代入したら素数が次々と生み出されるタイプのものではなく、定理2に従って考えている数が素数かどうかを判定するものです。しかし、その素数判定は実質的にWilsonの定理に頼っているのであって、それ自体が実用性のないものでした。そこから他のアルファベットの値も決定しようとするとPell方程式を解く必要があります)。
にテキトーに非負整数を代入して
を計算しても大抵は負の数になって素数になりません。しかしながら、せっかくなので定理2(および命題1、2)の後半の証明を参考にして
となるような
を一組見つけてみましょう
(として読み替えることに注意)。
(証明中の記号で言えば
。紛らわしいので
を導入する).
より
.
なる
と
を見つける。Pell方程式の一般論で必ずアルゴリズミックに見つけられるものの、ここでは幸い
が即座に見つかる。
.
.
.
.
.
.
.
- Pell方程式
を満たす
であって
であるようなものを見つける。
あ、見つかりました(最小解です)*7。
これは条件を満たしていますネ!
- 次は
とおく。
すなわち、
とおく。
そろそろ、アラビア数字だけで書き下す気力がなくなってきました。。。ここからは、を使って書けるということを理解できたらOKということにして妥協しましょう。
ちょっと大きい数が出てきたよ⭐︎ *8
これで変数用意できました。

素数を作るのって大変〜
謝辞
最後のを作るところで、
の値を間違えていました。これは、
を計算するところで
と間違えたことによって、
というPell方程式ではなく
を解いてしまっていたためです。このことは藤本浩司氏にご指摘いただきました。藤本氏に感謝致します。また、実際は170桁ではなく55桁の数だったため、書籍『素数姫の素数入門』における該当部分も連動してミスということになります。以上について深くお詫び申し上げます。
*1:Davis, Putnam, Robinsonの仕事も使って素数を表現する多項式の存在が1970年に理論的に示され、Matijasevicが1971年に変数
次の多項式の存在を示しています。
*2:例えば、この4人は変数
次のものを見つけており、 Matijasevicは
変数かつ約
次のものを見つけています。
*3:この記事における制限においては、を考える場合は
を仮定すると考えてよい。
*4:これはDavisの論文では証明に使われているのですが、命題1の証明では実は不要です。不要なのに書いてしまったので、せっかくなのでこのまま残しておきます(実際には補題が多すぎて番号を揃えるのが面倒だから消したくないのです笑)。命題1の証明以外を書き上げてから命題1を書こうと思ったら大量に補題が必要だということに気づき、その分の執筆が大変でした。
*5:の部分の寄与は
以下であることに注意
*6:アルファベットが足りない!!
*7:次のWeb上の計算機を利用しました: www.jakebakermaths.org.uk
*8:参考にと簡略化したときの
の桁数を述べますと、
です。
桁の数ではないですよ。こんな表現ないかもしれないですが、(
桁)桁の数です。