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

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

デリック・ヘンリー・レーマー英語版は、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト(英語: 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 リュカ・テスト

参考文献[編集]

関連文献[編集]

  • 中村滋『フィボナッチ数の小宇宙(ミクロコスモス) フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月30日。ISBN 4-535-78281-4。
  • 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 
  • 和田秀男数の世界 整数論への道』岩波書店〈科学ライブラリー〉、1981年7月10日。ISBN 4-00-005500-3。 - 前編は1次式の整数論、後編は2次式の整数論。
  • 和田秀男『コンピュータと素因子分解』遊星社(発行) 星雲社(発売)、1999年4月(原著1987年10月20日)、改訂版。ISBN 4-7952-6858-4 ISBN 4-7952-6889-4。

関連項目[編集]