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

は、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト() と呼ばれる、メルセンヌ数に対する素数判定法を確立した。

リュカ–レーマー・テスト 
p が奇素数のとき、メルセンヌ数 M = 2 − 1 が素数となるための必要十分条件は、S = 4, S = S − 2 (n ≧ 1) と定義したときに S が M で割り切れることである。

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

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

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

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

となる。

以下、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（英語）

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