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

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

フェルマーの小定理によれば $p$ が素数で $a$ が $p$ の倍数ではない整数ならば $a^{p-1}\equiv 1{\pmod {p}}$ である。しかし、以前に述べたように、これだけで与えられた整数 $N$ が素数であるかどうかを判定することはできない。というのは $2^{340}\equiv 1{\pmod {341}}$ のように $N$ が合成数でも $a^{N-1}\equiv 1{\pmod {N}}$ となる場合があるからである。 さらに厄介なことに、 $\gcd(a,N)=1$ となる任意の $a$ に対し $a^{N-1}\equiv 1{\pmod {N}}$ となる合成数 $N$ （カーマイケル数）が存在することも 先に述べた通りである。

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

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

合同式に基づく素数判定

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

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

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

定理 1

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

$a^{N-1}\equiv 1{\pmod {N}},$

$N-1$ のすべての素因数 $q$ に対して $a^{(N-1)/q}\not \equiv 1{\pmod {N}}$

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

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

定理 2

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

$a^{N-1}\equiv 1{\pmod {N}},$

$a^{(N-1)/q}\not \equiv 1{\pmod {N}}$

となる $a$ が存在することである（$a$ は各 $q$ に対して異なっていてもよい）。

証明
$N-1=\prod q_{i}^{r_{i}}$ と素因数分解する。各 $q_{i}$ に対応する $a=a(q_{i})$ の位数は $N$ の約数だが $N/q$ の約数ではないので $q_{i}^{r_{i}}$ の倍数でなければならない。ということは $\varphi (N)$ も $q_{i}^{r_{i}}$ の倍数でなければならない。これが各 $q_{i}$ に対して成り立つことから $\varphi (N)=N-1$ である。

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

定理 3

$N=h\cdot 2^{n}+1$ としたときに $h<2^{n}$ となっているとする。このとき $N$ が素数であるための必要十分条件は

$a^{(N-1)/2}\equiv -1{\pmod {N}}$

となる $a$ が存在することである（$a$ は各 $q$ に対して異なっていてもよい）。

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

一方 $N$ が合成数であるとすると$N$ の素因数 $p<{\sqrt {N}}$ がとれる。 ここで $a^{(N-1)/2}\equiv -1{\pmod {N}}$ ならば $p|N|(a^{(N-1)/2}+1)$ より $a^{(N-1)/2}\equiv -1{\pmod {p}}$ も成り立たなければなければならない。 すると $a^{N-1}\equiv 1{\pmod {p}}$ より $a{\pmod {p}}$ の位数は $N-1$ の約数でなければならないが $(N-1)/2$ の約数ではないので $2^{n}$ の倍数でなければならないことがわかる。よって $p\equiv 1{\pmod {2^{n}}}$ であるが このとき

$N>p^{2}\geq (2^{n}+1)^{2}>2^{2n}+1>h\cdot 2^{n}+1=N$

となり、矛盾が起きる。 よって $a^{(N-1)/2}\equiv -1{\pmod {N}}$ のとき $N$ は素数でなければならない。

この判定法はProthが発見したもので、この形の素数に対する単純な判定法を与えている。そのため、現在知られている巨大な素数の多くは $h\cdot 2^{n}+1$ の形のものである。

例 $N=7\times 2^{120}+1,a=5$ に対して

$5^{7\times 2^{119}}\equiv -1{\pmod {7\times 2^{120}+1}}$

となるので $7\times 2^{120}+1$ は素数である。

なお、この数 $7\times 2^{120}+1$ の素数性は次のように示すこともできる。

$2^{2^{117}}\equiv -1{\pmod {7\times 2^{120}+1}}$

より $2{\pmod {7\times 2^{120}+1}}$ の位数は $2^{118}$ に一致する。よって位数の法則より、 $7\times 2^{120}+1$ の素因数は $k\cdot 2^{118}+1$ の形でなければならない。ここで $7\times 2^{120}+1$ が合成数と仮定すると

$7\times 2^{120}+1\geq (2^{118}+1)^{2}>2^{236}$

となって矛盾するので $7\times 2^{120}+1$ は素数である。 （上記の事実から、この数はフェルマー数 $F_{117}=2^{2^{117}}+1$ の素因数なので $F_{117}$ が素数ではないこともわかる）