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

出典: フリー百科事典『ウィキペディア(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=kF(kは自然数)と表せる。Snの一般項から

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

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

よって、

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

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

より、2peの倍数。2p>eならば、e=2ttは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 リュカ・テスト

参考文献[編集]

関連文献[編集]

関連項目[編集]

外部リンク[編集]