初等整数論/合同式に基づく素数判定


合同式の応用の中でも特に重要なものとして、与えられた整数が素数であるかどうかを判定する問題がある。 もちろん、素数・合成数は整除性に基いて定義されているのだから、合同式と関連があるのは当然であるが、そのような自明なことを超えて、より深い応用が存在する。

フェルマーの小定理によれば が素数で の倍数ではない整数ならば である。しかし、以前に述べたように、これだけで与えられた整数 が素数であるかどうかを判定することはできない。というのは のように が合成数でも となる場合があるからである。 さらに厄介なことに、 となる任意の に対し となる合成数 (カーマイケル数)が存在することも 先に述べた通りである。

一方、ウィルソンの定理 が素数であることの必要十分条件を与えているが、階乗を計算するための計算量が非常に大きいため、実用的ではない。


しかし、フェルマーの小定理の変形により、特殊な状況においては が素数であることを比較的簡単に確認できる場合がある。


合同式に基づく素数判定

編集

合成数を法とする剰余類の構造より   の位数は   以下である。ところで   が必ず成立し、かつ等号は   が素数であるとき、そのときに限り成り立つ。 より単純に、フェルマー・オイラーの定理から、  の位数は高々   であるが、やはり   が必ず成立し、等号は   が素数であるとき、そのときに限り成り立つ。

したがって    が素数であるための必要十分条件である。 さらに   が素数であるための必要十分条件は位数   の剰余類が存在することだということがわかる(必要性は原始根の存在から導かれる)。


位数の法則から次の定理が導かれる。

定理 1
編集

  が素数であるための必要十分条件は

 
  のすべての素因数   に対して  

となる   が存在することである。

この判定法はLucasが発見したもので、合同式に基づく素数判定法の中でも基本的なものである。これを一般化したものがメルセンヌ素数に対するLucas Testである。さて、この判定法は次のように拡張できる。

定理 2
編集

  が素数であるための必要十分条件は、   のすべての素因数   に対して

 
 

となる   が存在することである(  は各   に対して異なっていてもよい)。

証明
  と素因数分解する。各   に対応する   の位数は   の約数だが   の約数ではないので   の倍数でなければならない。ということは    の倍数でなければならない。これが各   に対して成り立つことから   である。


さらに、特殊な形の数に対しては   の素因数分解を完全に知る必要はない場合がある。最も単純な判定法として、次のものがある。

定理 3
編集

  としたときに   となっているとする。このとき   が素数であるための必要十分条件は

 

となる   が存在することである(  は各   に対して異なっていてもよい)。

証明
  が素数で   を原始根とすると原始根の応用例 (1) から上記の式が成り立つから、必要性は成り立つ。

一方   が合成数であるとすると  の素因数   がとれる。 ここで   ならば   より   も成り立たなければなければならない。 すると   より   の位数は   の約数でなければならないが   の約数ではないので   の倍数でなければならないことがわかる。よって   であるが このとき

 

となり、矛盾が起きる。 よって   のとき   は素数でなければならない。


この判定法はProthが発見したもので、この形の素数に対する単純な判定法を与えている。そのため、現在知られている巨大な素数の多くは   の形のものである。

  に対して

 

となるので   は素数である。

なお、この数   の素数性は次のように示すこともできる。

 

より   の位数は   に一致する。よって位数の法則より、   の素因数は   の形でなければならない。ここで   が合成数と仮定すると

 

となって矛盾するので   は素数である。 (上記の事実から、この数はフェルマー数   の素因数なので   が素数ではないこともわかる)