リュカ–レーマー・テストの証明
デリック・ヘンリー・レーマーは、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト(Lucas–Lehmer primality test) と呼ばれる、メルセンヌ数に対する素数判定法を確立した。
p が奇素数のとき、メルセンヌ数 Mp = 2p − 1 が素数となるための必要十分条件は、S0 = 4, Sn = Sn−12 − 2 (n ≧ 1) と定義したときに Sp−2 が Mp で割り切れることである。
これの一般化であるリュカ–レーマー–リーゼル・テストもある。
なおフェルマー数にも同様な素数判定の定理であるペピンの判定法がある。
数列 S0 , S1 , S2 , ... の一般項を求める。Sn+1 = Sn2 − 2 なので、S0 = α + β , S1 = α2 + β2 となるような α と β を見つけるには、αβ = 1 , α + β = 4 を解くことになる。すると一般項は
S_n=\omega^{2^n}+\bar{\omega}^{2^n},\ \omega=2+\sqrt{3},\ \bar{\omega}=2-\sqrt{3}
となる。
以下、Q = 2p − 1 とする。
まず、Sp−2 ≡ 0 (mod Q) であれば、Q が素数であることを証明する。
Sp−2 ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、Sp−2 は Q の一番小さい素因数 F を用いて Sp−2 = kF(kは自然数)と表せる。Sn の一般項から
\omega^{2^{p-2}+\bar{\omega}^{2^{p-2}=kF
となる。
\omega\bar{\omega}=1なので、両辺に\omega^{2^{p-2}をかけて、
\omega^{2^{p-1}+1=kF\omega^{2^{p-2}
1を移項し、両辺を2乗すると、
\omega^{2^p}=k^2F^2\omega^{2^{p-1}-2kF\omega^{2^{p-2}+1.
よって、
\omega^{2^p}\equiv{1} \pmod{F}
となる。ここで、a+b\sqrt{3} と c+d\sqrt{3}(a, b, c, dは整数)で表される数を考えたとき、a ≡ c (mod F) かつ b ≡ d (mod F) の時に二つの数は F を法として合同であるとする。そして、
G=\{g_n|g_n=a_n+b_n\sqrt{3}\equiv\omega^n \pmod{F},\ 0\leqq a_n<F,\ 0\leqq b_n<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 ≤ e ≤ F2 − 1 となる。
\omega^{2^p}\equiv{1} \pmod{F}
より、2p は e の倍数。2p > e ならば、e = 2t (tは0以上p−1以下の整数)となる。言い換えれば 2p−1 は e の倍数となる。つまり、
\omega^{2^{p-1}\equiv{1}\pmod{F}
となるはずである。しかし、上の式、
\omega^{2^{p-1}+1=kF\omega^{2^{p-2}
より、
\omega^{2^{p-1}\equiv{-1}\pmod{F}
よって、2p = e となる。しかし、F は Q の一番小さい素因数なので、
F\leqq\sqrt{Q}<2^{\frac{p}{2}.
よって、F2 − 1 < 2p となる。
よって、2p = e なので、F2 − 1 < e となり 1 ≤ e ≤ F2 − 1 と矛盾する。
よって、背理法により、Sp−2 ≡ 0 (mod Q) ということは、Q は素数であるということの十分条件である。
次に p が奇素数であり、かつ Q が素数であれば、Sp−2 ≡ 0 (mod Q) であることを証明する。
この証明をするうえで、平方剰余の相互法則を使う。
まず、二項定理より、
(1+\sqrt{3})^Q=1+\begin{pmatrix} Q \\ 1 \end{pmatrix} (\sqrt{3})+\begin{pmatrix} Q \\ 2 \end{pmatrix} (\sqrt{3})^2+...+\begin{pmatrix} Q \\ Q-1 \end{pmatrix} (\sqrt{3})^{Q-1}+(\sqrt{3})^Q
Q は素数なので\begin{pmatrix} Q \\ n \end{pmatrix}=\frac{Q!}{n!(Q-n)!} は n = 0, Q の場合を除いて Q の倍数。よって、
\begin{align}
(1+\sqrt{3})^Q & \equiv 1+(\sqrt{3})^{Q}\pmod{Q} \\
& = 1+3^\frac{Q-1}{2}(\sqrt{3})\\
\end{align}
Q ≡ −1 (mod 4), 3 ≡ −1 (mod 4) で、平方剰余の相互法則により、
\left(\frac{Q}{3}\right)\left(\frac{3}{Q}\right)={-1}
Q = 2p − 1 = 2(2p−1 − 1) + 1 = 2((3 + 1)(p−1)/2 − 1) + 1 ≡ 12 (mod 3)よって
\left(\frac{3}{Q}\right)={-1},\left(\frac{Q}{3}\right)=1.
つまり、
3^\frac{Q-1}{2}\equiv{-1}\pmod{Q}
が成り立ち、よって、
(1+\sqrt{3})^Q\equiv{1+(-1)\sqrt{3}\pmod{Q}.
両辺に(1+\sqrt{3})\left(\frac{Q+1}{2}\right)を掛けて、
(1+\sqrt{3})^{Q+1}\left(\frac{Q+1}{2}\right)\equiv{-Q-1}\pmod{Q}.
この式は(1+\sqrt{3})^2=4+2\sqrt{3}=2\omegaを利用して、
(Q+1)2^\frac{Q-1}{2}\omega^\frac{Q+1}{2}\equiv2^\frac{Q-1}{2}\omega^\frac{Q+1}{2}\pmod{Q}\equiv{-1}\pmod{Q}
とも書ける。
平方剰余の相互法則の第2補充法則\left( \frac{2}{Q} \right) = (-1)^{ \frac{Q^2-1}{8}={1}により、
2^\frac{Q-1}{2}\equiv{1}\pmod{Q}.
よって、
\omega^\frac{Q+1}{2}\equiv{-1}\pmod{Q}.
ここで、\frac{Q+1}{2}=2^{p-1}なので、
\omega^{2^{p-1}\equiv{-1}\pmod{Q}
となる。両辺に\bar{\omega}^{2^{p-2}を掛けて、
\omega^{2^{p-1}\bar{\omega}^{2^{p-2}=(\omega^{2^{p-2})^2(\bar{\omega}^{2^{p-2})=\omega^{2^{p-2}\equiv{-\bar{\omega}^{2^{p-2}}\pmod{Q}.
両辺に\bar{\omega}^{2^{p-2}を足して、
\omega^{2^{p-2}+\bar{\omega}^{2^{p-2}=S_{p-2}\equiv{0}\pmod{Q}.
よって、Sp−2 ≡ 0 (mod Q) であることは、Q が素数であることの必要条件である。
以上により、リュカ-レーマー・テスト
S_{p-2}\equiv{0} \pmod{Q}\Longleftrightarrow \forall{u}\in\mathbb{N}[2\leqq{u}<Q \to{Q}\not\equiv{0} \pmod{u}]
が示された。Q.E.D.