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

リュカ–レーマー・テスト（）とは、素数判定法の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

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

Źródło i licencja