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

合同式の応用の中でも特に重要なものとして、与えられた整数が素数であるかどうかを判定する問題がある。 もちろん、素数・合成数は整除性に基いて定義されているのだから、合同式と関連があるのは当然であるが、そのような自明なことを超えて、より深い応用が存在する。
フェルマーの小定理によれば p {\displaystyle p} が素数で a {\displaystyle a} が p {\displaystyle p} の倍数ではない整数ならば a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} である。しかし、以前に述べたように、これだけで与えられた整数 N {\displaystyle N} が素数であるかどうかを判定することはできない。というのは 2 340 ≡ 1 ( mod 341 ) {\displaystyle 2^{340}\equiv 1{\pmod {341}}} のように N {\displaystyle N} が合成数でも a N − 1 ≡ 1 ( mod N ) {\displaystyle a^{N-1}\equiv 1{\pmod {N}}} となる場合があるからである。 さらに厄介なことに、 gcd ( a , N ) = 1 {\displaystyle \gcd(a,N)=1} となる任意の a {\displaystyle a} に対し a N − 1 ≡ 1 ( mod N ) {\displaystyle a^{N-1}\equiv 1{\pmod {N}}} となる合成数 N {\displaystyle N} (カーマイケル数)が存在することも 先に述べた通りである。
一方、ウィルソンの定理は N {\displaystyle N} が素数であることの必要十分条件を与えているが、階乗を計算するための計算量が非常に大きいため、実用的ではない。
しかし、フェルマーの小定理の変形により、特殊な状況においては N {\displaystyle N} が素数であることを比較的簡単に確認できる場合がある。

合成数を法とする剰余類の構造より a ( mod N ) {\displaystyle a{\pmod {N}}} の位数は λ ( N ) {\displaystyle \lambda (N)} 以下である。ところで λ ( N ) ≤ N − 1 {\displaystyle \lambda (N)\leq N-1} が必ず成立し、かつ等号は N {\displaystyle N} が素数であるとき、そのときに限り成り立つ。 より単純に、フェルマー・オイラーの定理から、 a ( mod N ) {\displaystyle a{\pmod {N}}} の位数は高々 φ ( N ) {\displaystyle \varphi (N)} であるが、やはり φ ( N ) ≤ N − 1 {\displaystyle \varphi (N)\leq N-1} が必ず成立し、等号は N {\displaystyle N} が素数であるとき、そのときに限り成り立つ。
したがって φ ( N ) = N − 1 {\displaystyle \varphi (N)=N-1} は N {\displaystyle N} が素数であるための必要十分条件である。 さらに N {\displaystyle N} が素数であるための必要十分条件は位数 N − 1 {\displaystyle N-1} の剰余類が存在することだということがわかる(必要性は原始根の存在から導かれる)。
位数の法則から次の定理が導かれる。
N {\displaystyle N} が素数であるための必要十分条件は
となる a {\displaystyle a} が存在することである。
この判定法はLucasが発見したもので、合同式に基づく素数判定法の中でも基本的なものである。これを一般化したものがメルセンヌ素数に対するLucas Testである。さて、この判定法は次のように拡張できる。
N {\displaystyle N} が素数であるための必要十分条件は、 N − 1 {\displaystyle N-1} のすべての素因数 q {\displaystyle q} に対して
となる a {\displaystyle a} が存在することである( a {\displaystyle a} は各 q {\displaystyle q} に対して異なっていてもよい)。
証明 N − 1 = ∏ q i r i {\displaystyle N-1=\prod q_{i}^{r_{i}}} と素因数分解する。各 q i {\displaystyle q_{i}} に対応する a = a ( q i ) {\displaystyle a=a(q_{i})} の位数は N {\displaystyle N} の約数だが N / q {\displaystyle N/q} の約数ではないので q i r i {\displaystyle q_{i}^{r_{i}}} の倍数でなければならない。ということは φ ( N ) {\displaystyle \varphi (N)} も q i r i {\displaystyle q_{i}^{r_{i}}} の倍数でなければならない。これが各 q i {\displaystyle q_{i}} に対して成り立つことから φ ( N ) = N − 1 {\displaystyle \varphi (N)=N-1} である。
さらに、特殊な形の数に対しては N − 1 {\displaystyle N-1} の素因数分解を完全に知る必要はない場合がある。最も単純な判定法として、次のものがある。
N = h ⋅ 2 n + 1 {\displaystyle N=h\cdot 2^{n}+1} としたときに h < 2 n {\displaystyle h<2^{n}} となっているとする。このとき N {\displaystyle N} が素数であるための必要十分条件は
となる a {\displaystyle a} が存在することである( a {\displaystyle a} は各 q {\displaystyle q} に対して異なっていてもよい)。
証明 N {\displaystyle N} が素数で a {\displaystyle a} を原始根とすると原始根の応用例 (1) から上記の式が成り立つから、必要性は成り立つ。
一方 N {\displaystyle N} が合成数であるとすると N {\displaystyle N} の素因数 p < N {\displaystyle p<{\sqrt {N}}} がとれる。 ここで a ( N − 1 ) / 2 ≡ − 1 ( mod N ) {\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}} ならば p | N | ( a ( N − 1 ) / 2 + 1 ) {\displaystyle p|N|(a^{(N-1)/2}+1)} より a ( N − 1 ) / 2 ≡ − 1 ( mod p ) {\displaystyle a^{(N-1)/2}\equiv -1{\pmod {p}}} も成り立たなければなければならない。 すると a N − 1 ≡ 1 ( mod p ) {\displaystyle a^{N-1}\equiv 1{\pmod {p}}} より a ( mod p ) {\displaystyle a{\pmod {p}}} の位数は N − 1 {\displaystyle N-1} の約数でなければならないが ( N − 1 ) / 2 {\displaystyle (N-1)/2} の約数ではないので 2 n {\displaystyle 2^{n}} の倍数でなければならないことがわかる。よって p ≡ 1 ( mod 2 n ) {\displaystyle p\equiv 1{\pmod {2^{n}}}} であるが このとき
となり、矛盾が起きる。 よって a ( N − 1 ) / 2 ≡ − 1 ( mod N ) {\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}} のとき N {\displaystyle N} は素数でなければならない。
この判定法はProthが発見したもので、この形の素数に対する単純な判定法を与えている。そのため、現在知られている巨大な素数の多くは h ⋅ 2 n + 1 {\displaystyle h\cdot 2^{n}+1} の形のものである。
例 N = 7 × 2 120 + 1 , a = 5 {\displaystyle N=7\times 2^{120}+1,a=5} に対して
となるので 7 × 2 120 + 1 {\displaystyle 7\times 2^{120}+1} は素数である。
なお、この数 7 × 2 120 + 1 {\displaystyle 7\times 2^{120}+1} の素数性は次のように示すこともできる。
より 2 ( mod 7 × 2 120 + 1 ) {\displaystyle 2{\pmod {7\times 2^{120}+1}}} の位数は 2 118 {\displaystyle 2^{118}} に一致する。よって位数の法則より、 7 × 2 120 + 1 {\displaystyle 7\times 2^{120}+1} の素因数は k ⋅ 2 118 + 1 {\displaystyle k\cdot 2^{118}+1} の形でなければならない。ここで 7 × 2 120 + 1 {\displaystyle 7\times 2^{120}+1} が合成数と仮定すると
となって矛盾するので 7 × 2 120 + 1 {\displaystyle 7\times 2^{120}+1} は素数である。 (上記の事実から、この数はフェルマー数 F 117 = 2 2 117 + 1 {\displaystyle F_{117}=2^{2^{117}}+1} の素因数なので F 117 {\displaystyle F_{117}} が素数ではないこともわかる)