リュカ–レーマー・テストの証明

リュカ–レーマー・テスト（英語: Lucas–Lehmer primality test）とは、素数判定法の1つ。メルセンヌ数 M_n = 2ⁿ − 1 の素数判定のみに特化している。

名称は、フランスの数学者エドゥアール・リュカおよびアメリカの数学者デリック・ヘンリー・レーマー（英語版）にちなんで名付けられた。

リュカ–レーマー・テストをさらに一般化した素数判定法であるリュカ–レーマー–リーゼル・テストも参照。

概要

初項 ${\displaystyle S_{0}=4}$ 、漸化式 ${\displaystyle S_{n+1}=S_{n}^{2}-2}$ 、一般項 ${\displaystyle S_{n}=\omega ^{(2^{n})}+{\bar {\omega }}^{(2^{n})}}$ で定義される数列 S₀ , S₁ , S₂ , ... について考える（ただし、 ${\displaystyle \omega =2+{\sqrt {3}},\ {\bar {\omega }}=2-{\sqrt {3}}}$ 。）。

p が奇素数のとき、メルセンヌ数 M_p = 2^p − 1 が素数であるための必要十分条件は、S_p−2 が M_p で割り切れることである^[1][2][3]。

なおフェルマー数にも、同様な素数判定の定理であるペパンの判定法（英語版）が存在する。

リュカ–レーマー・テストの証明

以下、Q = 2^p − 1 とする。

十分性の証明

${\displaystyle S_{p-2}\equiv 0{\pmod {Q}}\Rightarrow }$ Qは素数。

まず、S_p−2 ≡ 0 (mod Q) であれば、Q が素数であることを証明する。 S_p−2 ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、S_p−2 は Q の一番小さい素因数 F を用いて S_p−2 = kF（kは自然数）と表せる。S_n の一般項から

${\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kF}$

となる。 ${\displaystyle \omega {\bar {\omega }}=1}$なので、両辺に${\displaystyle \omega ^{2^{p-2}}}$をかけて、

${\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}}$

1を移項し、両辺を2乗すると、

${\displaystyle \omega ^{2^{p}}=k^{2}F^{2}\omega ^{2^{p-1}}-2kF\omega ^{2^{p-2}}+1.}$

よって、

${\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}}$

となる。ここで、${\displaystyle a+b{\sqrt {3}}}$ と ${\displaystyle c+d{\sqrt {3}}}$（a, b, c, dは整数）で表される数を考えたとき、a ≡ c (mod F) かつ b ≡ d (mod F) の時に二つの数は F を法として合同であるとする。そして、

${\displaystyle G=\{g_{n}|g_{n}=a_{n}+b_{n}{\sqrt {3}}\equiv \omega ^{n}{\pmod {F}},\ 0\leqq a_{n}<F,\ 0\leqq b_{n}<F\}}$

という集合 G ではどの要素 g_n にも g_ng_m ≡ 1 (mod F) となるような g_m が存在する。つまり、集合 G には0は含まれない。よって、集合 G には最大で F ² − 1 個の相異なる要素しか含まれない。g_n = 1 となる n のうち最小のものを e とすると任意の自然数 r について g_r = g_je+r (jは0以上の整数) が成り立つ。よって 1 ≤ e ≤ F² − 1 となる。

${\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}}$

より、2^p は e の倍数。2^p > e ならば、e = 2^t (tは0以上p−1以下の整数)となる。言い換えれば 2^p−1 は e の倍数となる。つまり、

${\displaystyle \omega ^{2^{p-1}}\equiv {1}{\pmod {F}}}$

となるはずである。しかし、上の式、

${\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}}$

より、

${\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {F}}}$

よって、2^p = e となる。しかし、F は Q の一番小さい素因数なので、

${\displaystyle F\leqq {\sqrt {Q}}<2^{\frac {p}{2}}.}$

よって、F² − 1 < 2^p となる。 よって、2^p = e なので、F² − 1 < e となり 1 ≤ e ≤ F² − 1 と矛盾する。 よって、背理法により、S_p−2 ≡ 0 (mod Q) ということは、Q は素数であるということの十分条件である。

必要性の証明

p が奇素数であり、かつ Q が素数 ${\displaystyle \Rightarrow S_{p-2}\equiv 0{\pmod {Q}}.}$

次に p が奇素数であり、かつ Q が素数であれば、S_p−2 ≡ 0 (mod Q) であることを証明する。 この証明をするうえで、平方剰余の相互法則を使う。 まず、二項定理より、

${\displaystyle (1+{\sqrt {3}})^{Q}=1+{\begin{pmatrix}Q\\1\end{pmatrix}}({\sqrt {3}})+{\begin{pmatrix}Q\\2\end{pmatrix}}({\sqrt {3}})^{2}+...+{\begin{pmatrix}Q\\Q-1\end{pmatrix}}({\sqrt {3}})^{Q-1}+({\sqrt {3}})^{Q}}$

Q は素数なので${\displaystyle {\begin{pmatrix}Q\\n\end{pmatrix}}={\frac {Q!}{n!(Q-n)!}}}$ は n = 0, Q の場合を除いて Q の倍数。よって、

${\displaystyle {\begin{aligned}(1+{\sqrt {3}})^{Q}&\equiv 1+({\sqrt {3}})^{Q}{\pmod {Q}}\\&=1+3^{\frac {Q-1}{2}}({\sqrt {3}})\\\end{aligned}}}$

Q ≡ −1 (mod 4), 3 ≡ −1 (mod 4) で、平方剰余の相互法則により、

${\displaystyle \left({\frac {Q}{3}}\right)\left({\frac {3}{Q}}\right)={-1}}$

Q = 2^p − 1 = 2(2^p−1 − 1) + 1 = 2((3 + 1)^(p−1)/2 − 1) + 1 ≡ 1² (mod 3)よって

${\displaystyle \left({\frac {3}{Q}}\right)={-1},\left({\frac {Q}{3}}\right)=1.}$

つまり、

${\displaystyle 3^{\frac {Q-1}{2}}\equiv {-1}{\pmod {Q}}}$

が成り立ち、よって、

${\displaystyle (1+{\sqrt {3}})^{Q}\equiv {1+(-1){\sqrt {3}}}{\pmod {Q}}.}$

両辺に${\displaystyle (1+{\sqrt {3}})\left({\frac {Q+1}{2}}\right)}$を掛けて、

${\displaystyle (1+{\sqrt {3}})^{Q+1}\left({\frac {Q+1}{2}}\right)\equiv {-Q-1}{\pmod {Q}}.}$

この式は${\displaystyle (1+{\sqrt {3}})^{2}=4+2{\sqrt {3}}=2\omega }$を利用して、

${\displaystyle (Q+1)2^{\frac {Q-1}{2}}\omega ^{\frac {Q+1}{2}}\equiv 2^{\frac {Q-1}{2}}\omega ^{\frac {Q+1}{2}}{\pmod {Q}}\equiv {-1}{\pmod {Q}}}$

とも書ける。 平方剰余の相互法則の第2補充法則${\displaystyle \left({\frac {2}{Q}}\right)=(-1)^{\frac {Q^{2}-1}{8}}={1}}$により、

${\displaystyle 2^{\frac {Q-1}{2}}\equiv {1}{\pmod {Q}}.}$

よって、

${\displaystyle \omega ^{\frac {Q+1}{2}}\equiv {-1}{\pmod {Q}}.}$

ここで、${\displaystyle {\frac {Q+1}{2}}=2^{p-1}}$なので、

${\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {Q}}}$

となる。両辺に${\displaystyle {\bar {\omega }}^{2^{p-2}}}$を掛けて、

${\displaystyle \omega ^{2^{p-1}}{\bar {\omega }}^{2^{p-2}}=(\omega ^{2^{p-2}})^{2}({\bar {\omega }}^{2^{p-2}})=\omega ^{2^{p-2}}\equiv {-{\bar {\omega }}^{2^{p-2}}}{\pmod {Q}}.}$

両辺に${\displaystyle {\bar {\omega }}^{2^{p-2}}}$を足して、

${\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=S_{p-2}\equiv {0}{\pmod {Q}}.}$

よって、S_p−2 ≡ 0 (mod Q) であることは、Q が素数であることの必要条件である。

以上により、リュカ-レーマー・テスト

${\displaystyle S_{p-2}\equiv {0}{\pmod {Q}}\Longleftrightarrow \forall {u}\in \mathbb {N} [2\leqq {u}<Q\to {Q}\not \equiv {0}{\pmod {u}}]}$

が示された。Q.E.D.