デリック・ヘンリー・レーマー(英語版)は、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト(英語: Lucas–Lehmer primality test) と呼ばれる、メルセンヌ数に対する素数判定法を確立した。
p が奇素数のとき、メルセンヌ数 Mp = 2p − 1 が素数となるための必要十分条件は、S0 = 4, Sn = Sn−12 − 2 (n ≧ 1) と定義したときに Sp−2 が Mp で割り切れることである[1][2][3]。
これの一般化であるリュカ–レーマー–リーゼル・テストもある。
なおフェルマー数にも同様な素数判定の定理であるペピンの判定法(英語版)がある。
数列の一般項
数列 S0 , S1 , S2 , ... の一般項を求める。Sn+1 = Sn2 − 2 なので、S0 = α + β , S1 = α2 + β2 となるような α と β を見つけるには、αβ = 1 , α + β = 4 を解くことになる。すると一般項は
![{\displaystyle S_{n}=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}},\ \omega =2+{\sqrt {3}},\ {\bar {\omega }}=2-{\sqrt {3}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/fd8ded4dbd2113efece3f070b03fde6afa45b2b4)
となる。
以下、Q = 2p − 1 とする。
十分性
Qは素数。
まず、Sp−2 ≡ 0 (mod Q) であれば、Q が素数であることを証明する。
Sp−2 ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、Sp−2 は Q の一番小さい素因数 F を用いて Sp−2 = kF(kは自然数)と表せる。Sn の一般項から
![{\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kF}](//wikimedia.org/api/rest_v1/media/math/render/svg/06919d7421e5b27d60ef4d998c2c088ffd03e9d1)
となる。
なので、両辺に
をかけて、
![{\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0efaca0befd41496d1e10712558f25b0743a8c3b)
1を移項し、両辺を2乗すると、
![{\displaystyle \omega ^{2^{p}}=k^{2}F^{2}\omega ^{2^{p-1}}-2kF\omega ^{2^{p-2}}+1.}](//wikimedia.org/api/rest_v1/media/math/render/svg/434f6d14fe0328e73a38bf5a78294f17200c930a)
よって、
![{\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7febd239a6616a3e6c7c4c96c85134d94bfae1a1)
となる。ここで、
と
(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\}}](//wikimedia.org/api/rest_v1/media/math/render/svg/582377deb034e8a41d160a0e04cedebf3fd8f659)
という集合 G ではどの要素 gn にも gngm ≡ 1 (mod F) となるような gm が存在する。つまり、集合 G には0は含まれない。よって、集合 G には最大で F 2 − 1 個の相異なる要素しか含まれない。gn = 1 となる n のうち最小のものを e とすると任意の自然数 r について gr = gje+r (jは0以上の整数) が成り立つ。よって 1 ≤ e ≤ F2 − 1 となる。
![{\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7febd239a6616a3e6c7c4c96c85134d94bfae1a1)
より、2p は e の倍数。2p > e ならば、e = 2t (tは0以上p−1以下の整数)となる。言い換えれば 2p−1 は e の倍数となる。つまり、
![{\displaystyle \omega ^{2^{p-1}}\equiv {1}{\pmod {F}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/3a3d87c41752ed16e8cfcea7c4c17576707c2a35)
となるはずである。しかし、上の式、
![{\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0efaca0befd41496d1e10712558f25b0743a8c3b)
より、
![{\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {F}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/8c62c950aace3d37720f6b18f0edd104a4df967f)
よって、2p = e となる。しかし、F は Q の一番小さい素因数なので、
![{\displaystyle F\leqq {\sqrt {Q}}<2^{\frac {p}{2}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/3b251841b7541d74bb5c5744751d04546977e7db)
よって、F2 − 1 < 2p となる。
よって、2p = e なので、F2 − 1 < e となり 1 ≤ e ≤ F2 − 1 と矛盾する。
よって、背理法により、Sp−2 ≡ 0 (mod Q) ということは、Q は素数であるということの十分条件である。
必要性
p が奇素数であり、かつ
Q が素数
![{\displaystyle \Rightarrow S_{p-2}\equiv 0{\pmod {Q}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/c6712214a2e9cfb5fea4c8d2566b167b90f7a435)
次に p が奇素数であり、かつ Q が素数であれば、Sp−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}}](//wikimedia.org/api/rest_v1/media/math/render/svg/e216c0a8d0a7b3181eb22319503793558089a2d3)
Q は素数なので
は 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}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/1958948f9858dc359282b83689e4fc55a0b0c1d2)
Q ≡ −1 (mod 4), 3 ≡ −1 (mod 4) で、平方剰余の相互法則により、
![{\displaystyle \left({\frac {Q}{3}}\right)\left({\frac {3}{Q}}\right)={-1}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0634bda6209a61e1be44e22d97b4ab78c5d7d92d)
Q = 2p − 1 = 2(2p−1 − 1) + 1 = 2((3 + 1)(p−1)/2 − 1) + 1 ≡ 12 (mod 3)よって
![{\displaystyle \left({\frac {3}{Q}}\right)={-1},\left({\frac {Q}{3}}\right)=1.}](//wikimedia.org/api/rest_v1/media/math/render/svg/9c447640a05ea97b9928ddf7f03924c31a7aa0e7)
つまり、
![{\displaystyle 3^{\frac {Q-1}{2}}\equiv {-1}{\pmod {Q}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7357ed8a0a1cf6dc661748d5556f8769c41f7384)
が成り立ち、よって、
![{\displaystyle (1+{\sqrt {3}})^{Q}\equiv {1+(-1){\sqrt {3}}}{\pmod {Q}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/672be7e79903bd83017b2a996030b80cda3fcdd3)
両辺に
を掛けて、
![{\displaystyle (1+{\sqrt {3}})^{Q+1}\left({\frac {Q+1}{2}}\right)\equiv {-Q-1}{\pmod {Q}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/b4d2912ba293a012fe9adb9096e2f6a94248b0fb)
この式は
を利用して、
![{\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}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/a397fc1ffc9417c866cf21e31b33ffe05df93f58)
とも書ける。
平方剰余の相互法則の第2補充法則
により、
![{\displaystyle 2^{\frac {Q-1}{2}}\equiv {1}{\pmod {Q}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/b873142c71b59f24c9fed0ac937c2cc51935651e)
よって、
![{\displaystyle \omega ^{\frac {Q+1}{2}}\equiv {-1}{\pmod {Q}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/053beddff9906df2a08da76f14610a72308ab585)
ここで、
なので、
![{\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {Q}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/1f50270b8c1f537aa4ba8dca9dddeaea7470ea6f)
となる。両辺に
を掛けて、
![{\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}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/77cc4850407712c773978a4ac980e59993490bdf)
両辺に
を足して、
![{\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=S_{p-2}\equiv {0}{\pmod {Q}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/2a36591e075b5edc2badcef2ffd9dc8dfcb52f3a)
よって、Sp−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}}]}](//wikimedia.org/api/rest_v1/media/math/render/svg/3fd12c20742557f75a70e4faa385ea0a41ec1e77)
が示された。Q.E.D.