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

デリック・ヘンリー・レーマー（英語版）は、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト(英語: Lucas–Lehmer primality test) と呼ばれる、メルセンヌ数に対する素数判定法を確立した。

p が奇素数のとき、メルセンヌ数 M_p = 2^p − 1 が素数となるための必要十分条件は、S₀ = 4, S_n = S_n−1² − 2 (n ≧ 1) と定義したときに S_p−2 が M_p で割り切れることである^[1][2][3]。

これの一般化であるリュカ–レーマー–リーゼル・テストもある。

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

数列 S₀ , S₁ , S₂ , ... の一般項を求める。S_n+1 = S_n² − 2 なので、S₀ = α + β , S₁ = α² + β² となるような α と β を見つけるには、αβ = 1 , α + β = 4 を解くことになる。すると一般項は

${\displaystyle S_{n}=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}},\ \omega =2+{\sqrt {3}},\ {\bar {\omega }}=2-{\sqrt {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.

• Lucas-Lehmer_Test

• 中村滋『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月30日。ISBN 4-535-78281-4。 
  • 中村滋『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』（改訂版）日本評論社、2008年1月25日。ISBN 978-4-535-78492-5。http://www.nippyo.co.jp/book/3222.html。 
• Hardy, G. H.; Wright, E. M. (31 July 2008), Heath-Brown, Roger; Silverman, Joseph; Wiles, Andrew, eds., An Introduction to the Theory of Numbers (sixth ed.), USA: Oxford University Press, ISBN 978-0-19-921986-5, http://ukcatalogue.oup.com/product/9780199219865.do#.UdgOFeaCjIU 
  • G.H.ハーディ、E.M.ライト（英語版）『数論入門』 I、示野信一・矢神毅翻訳、シュプリンガー・フェアラーク東京、2001年7月、89-90,114-116,137頁。ISBN 4-431-70848-0。  - 原書第5版（1979年）の邦訳。
  • G・H・ハーディ、E・M・ライト『数論入門』 I、示野信一・矢神毅翻訳、丸善出版、2012年1月、89-90,114-116,137頁。ISBN 978-4-621-06226-5。http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062265.html。  - ハーディ＆ライト(2001)の復刊。
• 和田秀男『数の世界　整数論への道』岩波書店〈科学ライブラリー〉、1981年7月10日。ISBN 4-00-005500-3。http://www.iwanami.co.jp/.BOOKS/00/3/0055000.html。  - 前編は1次式の整数論、後編は2次式の整数論。
• 和田秀男『コンピュータと素因子分解』（改訂版）遊星社(発行) 星雲社(発売)、1999年4月（原著1987年10月20日）。ISBN 4-7952-6858-4 ISBN 4-7952-6889-4。http://www2.odn.ne.jp/yuseisha/daiki/comp-c.htm。 

• エドゥアール・リュカ
• メルセンヌ数
• レオンハルト・オイラー
• GIMPS

• 世界大百科事典 第2版『メルセンヌ数』 - コトバンク
• リュカテストによるメルセンヌ素数の発見法 (PDF)
• Weisstein, Eric W. "Mersenne number". mathworld.wolfram.com (英語).
• Weisstein, Eric W. "Mersenne prime". mathworld.wolfram.com (英語).
• Mersenne Primes: History, Theorems and Lists（英語）
• The Largest Known Primes（英語）
• GIMPS（英語）