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

は、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト() と呼ばれる、メルセンヌ数に対する素数判定法を確立した。
リュカ–レーマー・テスト.
"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" の一般項から
となる。
formula_3なので、両辺にformula_4をかけて、
1を移項し、両辺を2乗すると、
よって、
となる。ここで、formula_8 と formula_9（"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 &gt; "e" ならば、"e" = 2 ("t"は0以上"p"−1以下の整数)となる。言い換えれば 2 は "e" の倍数となる。つまり、
となるはずである。しかし、上の式、
より、
よって、2 = "e" となる。しかし、"F" は "Q" の一番小さい素因数なので、
よって、"F" − 1 &lt; 2 となる。
よって、2 = "e" なので、"F" − 1 &lt; "e" となり 1 ≤ "e" ≤ "F" − 1 と矛盾する。
よって、背理法により、"S" ≡ 0 (mod "Q") ということは、"Q" は素数であるということの十分条件である。
必要性.
次に "p" が奇素数であり、かつ "Q" が素数であれば、"S" ≡ 0 (mod "Q") であることを証明する。
この証明をするうえで、平方剰余の相互法則を使う。
まず、二項定理より、
"Q" は素数なのでformula_17 は "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)よって
つまり、
が成り立ち、よって、
両辺にformula_23を掛けて、
この式はformula_25を利用して、
とも書ける。
平方剰余の相互法則の第2補充法則formula_27により、
よって、
ここで、formula_30なので、
となる。両辺にformula_32を掛けて、
両辺にformula_32を足して、
よって、"S" ≡ 0 (mod "Q") であることは、"Q" が素数であることの必要条件である。
以上により、リュカ-レーマー・テスト
が示された。Q.E.D.