リュカ–レーマー・テスト

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

名称は、フランスの数学者エドゥアール・リュカおよびアメリカの数学者にちなんで名付けられた。

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

 概要 
初項  、漸化式  、一般項  で定義される数列 S , S , S , ... について考える（ただし、  。）。

p が奇素数のとき、メルセンヌ数 M = 2 − 1 が素数であるための必要十分条件は、S が M で割り切れることである中村(2008)、84-85頁和田(1981)、50-52頁、194-199頁和田(1999)、§5 リュカ・テスト。

なおフェルマー数にも、同様な素数判定の定理であるが存在する。

 リュカ–レーマー・テストの証明 
以下、Q = 2 − 1 とする。

 十分性の証明 

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

となる。
なので、両辺にをかけて、

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

よって、

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

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

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

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

より、

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

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

 必要性の証明 

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

Q は素数なので は n = 0, Q の場合を除いて Q の倍数。よって、

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

Q = 2 − 1 = 2(2 − 1) + 1 = 2((3 + 1) − 1) + 1 ≡ 1 (mod 3)よって

つまり、

が成り立ち、よって、

両辺にを掛けて、

この式はを利用して、

とも書ける。
平方剰余の相互法則の第2補充法則により、

よって、

ここで、なので、

となる。両辺にを掛けて、

両辺にを足して、

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

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

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

 脚注 

 参考文献 
Lucas-Lehmer_Test

 関連文献 

 - 原書第5版（1979年）の邦訳。
 - ハーディ＆ライト(2001)の復刊。
 - 前編は1次式の整数論、後編は2次式の整数論。

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

 外部リンク 

Mersenne Primes: History, Theorems and Lists（英語）
The Largest Known Primes（英語）
GIMPS（英語）

Category:数論
Category:整数の類
Category:素数判定
Category:エドゥアール・リュカ
Category:数学に関する記事
Category:数学のエポニム