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

リュカ–レーマー・テスト（テンプレート:Lang-en）とは、素数判定法の1つ。メルセンヌ数 Mテンプレート:Sub = 2テンプレート:Sup − 1 の素数判定のみに特化している。

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

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

概要

初項 $S_0=4$ 、漸化式 $S_{n+1}=S_n^2-2$ 、一般項 $S_n={\omega }^{(2^n)}+{\overline{\omega }}^{(2^n)}$ で定義される数列 Sテンプレート:Sub , Sテンプレート:Sub , Sテンプレート:Sub , ... について考える（ただし、 $\omega =2+\sqrt{3},\overline{\omega }=2-\sqrt{3}$ 。）。

p が奇素数のとき、メルセンヌ数 Mテンプレート:Sub = 2テンプレート:Sup − 1 が素数であるための必要十分条件は、Sテンプレート:Sub が Mテンプレート:Sub で割り切れることである。

なおフェルマー数にも、同様な素数判定の定理であるテンプレート:Ill2が存在する。

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

以下、Q = 2テンプレート:Sup − 1 とする。

十分性の証明

テンプレート:Quotation まず、Sテンプレート:Sub ≡ 0 (mod Q) であれば、Q が素数であることを証明する。 Sテンプレート:Sub ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、Sテンプレート:Sub は Q の一番小さい素因数 F を用いて Sテンプレート:Sub = kF（kは自然数）と表せる。Sテンプレート:Sub の一般項から

${\omega }^{2^{p-2}}+{\overline{\omega }}^{2^{p-2}}=kF$

となる。 $\omega \overline{\omega }=1$なので、両辺に${\omega }^{2^{p-2}}$をかけて、

${\omega }^{2^{p-1}}+1=kF{\omega }^{2^{p-2}}$

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

${\omega }^{2^p}=k^2{F}^2{\omega }^{2^{p-1}}-2kF{\omega }^{2^{p-2}}+1.$

よって、

${\omega }^{2^p}\equiv 1(\mathrm{mod}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(\mathrm{mod}F),0\leqq a_n<F,0\leqq b_n<F\}$

という集合 G ではどの要素 gテンプレート:Sub にも gテンプレート:Subgテンプレート:Sub ≡ 1 (mod F) となるような gテンプレート:Sub が存在する。つまり、集合 G には0は含まれない。よって、集合 G には最大で F テンプレート:Sup − 1 個の相異なる要素しか含まれない。gテンプレート:Sub = 1 となる n のうち最小のものを e とすると任意の自然数 r について gテンプレート:Sub = gテンプレート:Sub (jは0以上の整数) が成り立つ。よって 1 ≤ e ≤ Fテンプレート:Sup − 1 となる。

${\omega }^{2^p}\equiv 1(\mathrm{mod}F)$

より、2テンプレート:Sup は e の倍数。2テンプレート:Sup > e ならば、e = 2テンプレート:Sup (tは0以上p−1以下の整数)となる。言い換えれば 2テンプレート:Sup は e の倍数となる。つまり、

${\omega }^{2^{p-1}}\equiv 1(\mathrm{mod}F)$

となるはずである。しかし、上の式、

${\omega }^{2^{p-1}}+1=kF{\omega }^{2^{p-2}}$

より、

${\omega }^{2^{p-1}}\equiv -1(\mathrm{mod}F)$

よって、2テンプレート:Sup = e となる。しかし、F は Q の一番小さい素因数なので、

$F\leqq \sqrt{Q}<2^{\frac{p}{2}}.$

よって、Fテンプレート:Sup − 1 < 2テンプレート:Sup となる。 よって、2テンプレート:Sup = e なので、Fテンプレート:Sup − 1 < e となり 1 ≤ e ≤ Fテンプレート:Sup − 1 と矛盾する。 よって、背理法により、Sテンプレート:Sub ≡ 0 (mod Q) ということは、Q は素数であるということの十分条件である。

必要性の証明

テンプレート:Quotation 次に p が奇素数であり、かつ Q が素数であれば、Sテンプレート:Sub ≡ 0 (mod Q) であることを証明する。 この証明をするうえで、平方剰余の相互法則を使う。 まず、二項定理より、

$(1+\sqrt{3}{)}^Q=1+\left(\begin{array}{c}Q\\ 1\end{array}\right)(\sqrt{3})+\left(\begin{array}{c}Q\\ 2\end{array}\right)(\sqrt{3}{)}^2+...+\left(\begin{array}{c}Q\\ Q-1\end{array}\right)(\sqrt{3}{)}^{Q-1}+(\sqrt{3}{)}^Q$

Q は素数なので$\left(\begin{array}{c}Q\\ n\end{array}\right)=\frac{Q!}{n!(Q-n)!}$ は n = 0, Q の場合を除いて Q の倍数。よって、

$\begin{array}{cc}(1+\sqrt{3}{)}^Q& \equiv 1+(\sqrt{3}{)}^Q(\mathrm{mod}Q)\\ & =1+3^{\frac{Q-1}{2}}(\sqrt{3})\\ \end{array}$

Q ≡ −1 (mod 4), 3 ≡ −1 (mod 4) で、平方剰余の相互法則により、

$\left(\frac{Q}{3}\right)\left(\frac{3}{Q}\right)=-1$

Q = 2テンプレート:Sup − 1 = 2(2テンプレート:Sup − 1) + 1 = 2((3 + 1)テンプレート:Sup − 1) + 1 ≡ 1テンプレート:Sup (mod 3)よって

$\left(\frac{3}{Q}\right)=-1,\left(\frac{Q}{3}\right)=1.$

つまり、

$3^{\frac{Q-1}{2}}\equiv -1(\mathrm{mod}Q)$

が成り立ち、よって、

$(1+\sqrt{3}{)}^Q\equiv 1+(-1)\sqrt{3}(\mathrm{mod}Q).$

両辺に$(1+\sqrt{3})\left(\frac{Q+1}{2}\right)$を掛けて、

$(1+\sqrt{3}{)}^{Q+1}\left(\frac{Q+1}{2}\right)\equiv -Q-1(\mathrm{mod}Q).$

この式は$(1+\sqrt{3}{)}^2=4+2\sqrt{3}=2\omega$を利用して、

$(Q+1)2^{\frac{Q-1}{2}}{\omega }^{\frac{Q+1}{2}}\equiv 2^{\frac{Q-1}{2}}{\omega }^{\frac{Q+1}{2}}(\mathrm{mod}Q)\equiv -1(\mathrm{mod}Q)$

とも書ける。 平方剰余の相互法則の第2補充法則$\left(\frac{2}{Q}\right)=(-1{)}^{\frac{Q^2-1}{8}}=1$により、

$2^{\frac{Q-1}{2}}\equiv 1(\mathrm{mod}Q).$

よって、

${\omega }^{\frac{Q+1}{2}}\equiv -1(\mathrm{mod}Q).$

ここで、$\frac{Q+1}{2}=2^{p-1}$なので、

${\omega }^{2^{p-1}}\equiv -1(\mathrm{mod}Q)$

となる。両辺に${\overline{\omega }}^{2^{p-2}}$を掛けて、

${\omega }^{2^{p-1}}{\overline{\omega }}^{2^{p-2}}=({\omega }^{2^{p-2}}{)}^2({\overline{\omega }}^{2^{p-2}})={\omega }^{2^{p-2}}\equiv -{\overline{\omega }}^{2^{p-2}}(\mathrm{mod}Q).$

両辺に${\overline{\omega }}^{2^{p-2}}$を足して、

${\omega }^{2^{p-2}}+{\overline{\omega }}^{2^{p-2}}=S_{p-2}\equiv 0(\mathrm{mod}Q).$

よって、Sテンプレート:Sub ≡ 0 (mod Q) であることは、Q が素数であることの必要条件である。

以上により、リュカ-レーマー・テスト

$S_{p-2}\equiv 0(\mathrm{mod}Q)⟺\mathrm{\forall }u\in \mathbb{N}[2\leqq u<Q\to Q\equiv ̸0(\mathrm{mod}u)]$

が示された。Q.E.D.

参考文献

• Lucas-Lehmer_Test

関連文献

• テンプレート:Cite book
  • テンプレート:Cite book
• テンプレート:Citation
  • テンプレート:Cite book - 原書第5版（1979年）の邦訳。
  • テンプレート:Cite book - ハーディ＆ライト(2001)の復刊。
• テンプレート:Cite book - 前編は1次式の整数論、後編は2次式の整数論。
• テンプレート:Cite book

関連項目

• エドゥアール・リュカ
• メルセンヌ数
• レオンハルト・オイラー
• GIMPS

外部リンク

• テンプレート:Kotobank
• テンプレート:MathWorld
• テンプレート:MathWorld
• Mersenne Primes: History, Theorems and Lists（英語）
• The Largest Known Primes（英語）
• GIMPS（英語）