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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

リュカ–レーマー・テスト[編集]

p が奇素数のとき、メルセンヌ数 Mp = 2p − 1 が素数となるための必要十分条件は、S0 = 4, Sn = Sn−12 − 2 (n ≧ 1) と定義したときに Sp−2Mp で割り切れることである[1][2][3]

リュカ–レーマー・テストの証明[編集]

数列の一般項[編集]

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

となる。

以下、Q = 2p − 1 とする。

十分性[編集]

Qは素数。

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

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

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

よって、

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

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

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

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

より、

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

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

必要性[編集]

p が奇素数であり、かつ Q が素数

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

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

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

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

つまり、

が成り立ち、よって、

両辺にを掛けて、

この式はを利用して、

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

よって、

ここで、なので、

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

両辺にを足して、

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

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

が示された。QED

脚注[編集]

  1. ^ 中村(2008)、84-85頁
  2. ^ 和田(1981)、50-52頁、194-199頁
  3. ^ 和田(1999)、§5 リュカ・テスト

参考文献[編集]

関連文献[編集]

関連項目[編集]

外部リンク[編集]