リュカ–レーマー・テスト

**リュカ–レーマー・テスト**（）とは、素数判定法の1つ。メルセンヌ数 *M* = 2 &minus; 1 の素数判定のみに特化している。

名称は、フランスの数学者エドゥアール・リュカおよびアメリカの数学者にちなんで名付けられた。

リュカ–レーマー・テストをさらに一般化した素数判定法であるリュカ–レーマー–リーゼル・テストも参照。

## 概要
初項 S_0 = 4 、漸化式 S_{n+1} = S_n^2 - 2 、一般項 S_n = \omega^{(2^n)} + \bar{\omega}^{(2^n)} で定義される数列 *S* , *S* , *S* , ... について考える（ただし、 \omega = 2 + \sqrt{3},\ \bar{\omega} = 2 - \sqrt{3} 。）。

*p* が奇素数のとき、メルセンヌ数 *M* = 2 &minus; 1 が素数であるための必要十分条件は、*S* が *M* で割り切れることである。

なおフェルマー数にも、同様な素数判定の定理であるが存在する。

## リュカ–レーマー・テストの証明
以下、*Q* = 2 &minus; 1 とする。

### 十分性の証明

まず、*S* ≡ 0 (mod *Q*) であれば、*Q* が素数であることを証明する。
*S* ≡ 0 (mod *Q*) で、かつ *Q* が合成数だと仮定する。すると、*S* は *Q* の一番小さい素因数 *F* を用いて *S* = *kF*（*k*は自然数）と表せる。*S* の一般項から
:\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
という集合 *G* ではどの要素 *g* にも *gg* ≡ 1 (mod *F*) となるような *g* が存在する。つまり、集合 *G* には0は含まれない。よって、集合 *G* には最大で *F*  &minus; 1 個の相異なる要素しか含まれない。*g* = 1 となる *n* のうち最小のものを *e* とすると任意の自然数 *r* について *g* = *g* (*j*は0以上の整数) が成り立つ。よって 1 ≤ *e* ≤ *F* &minus; 1 となる。
:\omega^{2^p}\equiv{1} \pmod{F}
より、2 は *e* の倍数。2 > *e* ならば、*e* = 2 (*t*は0以上*p*&minus;1以下の整数)となる。言い換えれば 2 は *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}
よって、2 = *e* となる。しかし、*F* は *Q* の一番小さい素因数なので、
:F\leqq\sqrt{Q}
よって、*F* &minus; 1 (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* ≡ &minus;1 (mod 4), 3 ≡ &minus;1 (mod 4) で、平方剰余の相互法則により、
:\left(\frac{Q}{3}\right)\left(\frac{3}{Q}\right)={-1}
*Q* = 2 &minus; 1 = 2(2 &minus; 1) + 1 = 2((3 + 1) &minus; 1) + 1 ≡ 1 (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}.
よって、*S* ≡ 0 (mod *Q*) であることは、*Q* が素数であることの必要条件である。

以上により、リュカ-レーマー・テスト
:S_{p-2}\equiv{0} \pmod{Q}\Longleftrightarrow \forall{u}\in\mathbb{N}[2\leqq{u}
が示された。Q.E.D.

## 脚注

## 参考文献
*Lucas-Lehmer_Test

## 関連文献
*
**
*
** - 原書第5版（1979年）の邦訳。
** - ハーディ＆ライト(2001)の復刊。
* - 前編は1次式の整数論、後編は2次式の整数論。
*

## 関連項目
*エドゥアール・リュカ
*メルセンヌ数
*レオンハルト・オイラー
*GIMPS

## 外部リンク
*
*
*
*Mersenne Primes: History, Theorems and Lists（英語）
*The Largest Known Primes（英語）
*GIMPS（英語）