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

リュカ–レーマー・テスト（英語: Lucas–Lehmer primality test）とは、素数判定法の1つ。メルセンヌ数 M_n = 2ⁿ − 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_p = 2^p − 1 が素数であるための必要十分条件は、S_p−2 が M_p で割り切れることである。

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

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

以下、Q = 2^p − 1 とする。

十分性の証明

$S_{p-2}\equiv 0{\pmod {Q}}\Rightarrow$ Qは素数。

まず、S_p−2 ≡ 0 (mod Q) であれば、Q が素数であることを証明する。 S_p−2 ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、S_p−2 は Q の一番小さい素因数 F を用いて S_p−2 = kF（kは自然数）と表せる。S_n の一般項から

$\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^{2}F^{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 ではどの要素 g_n にも g_ng_m ≡ 1 (mod F) となるような g_m が存在する。つまり、集合 G には0は含まれない。よって、集合 G には最大で F ² − 1 個の相異なる要素しか含まれない。g_n = 1 となる n のうち最小のものを e とすると任意の自然数 r について g_r = g_je+r (jは0以上の整数) が成り立つ。よって 1 ≤ e ≤ F² − 1 となる。

$\omega ^{2^{p}}\equiv {1}{\pmod {F}}$

より、2^p は e の倍数。2^p > e ならば、e = 2^t (tは0以上p−1以下の整数)となる。言い換えれば 2^p−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}}$

よって、2^p = e となる。しかし、F は Q の一番小さい素因数なので、

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

よって、F² − 1 < 2^p となる。 よって、2^p = e なので、F² − 1 < e となり 1 ≤ e ≤ F² − 1 と矛盾する。 よって、背理法により、S_p−2 ≡ 0 (mod Q) ということは、Q は素数であるということの十分条件である。

必要性の証明

p が奇素数であり、かつ Q が素数 $\Rightarrow S_{p-2}\equiv 0{\pmod {Q}}.$

次に p が奇素数であり、かつ Q が素数であれば、S_p−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{aligned}(1+{\sqrt {3}})^{Q}&\equiv 1+({\sqrt {3}})^{Q}{\pmod {Q}}\\&=1+3^{\frac {Q-1}{2}}({\sqrt {3}})\\\end{aligned}}$

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

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

Q = 2^p − 1 = 2(2^p−1 − 1) + 1 = 2((3 + 1)^(p−1)/2 − 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}}\equiv 2^{\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_p−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.

参考文献

• Lucas-Lehmer_Test

関連文献

• 中村滋『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』日本評論社、2002年9月30日。ISBN 4-535-78281-4。 
  • 中村滋『フィボナッチ数の小宇宙（ミクロコスモス）　フィボナッチ数、リュカ数、黄金分割』（改訂版）日本評論社、2008年1月25日。ISBN 978-4-535-78492-5。http://www.nippyo.co.jp/book/3222.html。 
• Hardy, G. H.; Wright, E. M. (31 July 2008), Heath-Brown, Roger; Silverman, Joseph; Wiles, Andrew, eds., An Introduction to the Theory of Numbers (sixth ed.), USA: Oxford University Press, ISBN 978-0-19-921986-5, http://ukcatalogue.oup.com/product/9780199219865.do#.UdgOFeaCjIU 
  • G.H.ハーディ、E.M.ライト『数論入門』 I、示野信一・矢神毅翻訳、シュプリンガー・フェアラーク東京、2001年7月、89-90,114-116,137頁。ISBN 4-431-70848-0。  - 原書第5版（1979年）の邦訳。
  • G・H・ハーディ、E・M・ライト『数論入門』 I、示野信一・矢神毅翻訳、丸善出版、2012年1月、89-90,114-116,137頁。ISBN 978-4-621-06226-5。http://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062265.html。  - ハーディ＆ライト(2001)の復刊。
• 和田秀男『数の世界　整数論への道』岩波書店〈科学ライブラリー〉、1981年7月10日。ISBN 4-00-005500-3。http://www.iwanami.co.jp/.BOOKS/00/3/0055000.html。  - 前編は1次式の整数論、後編は2次式の整数論。
• 和田秀男『コンピュータと素因子分解』（改訂版）遊星社(発行) 星雲社(発売)、1999年4月（原著1987年10月20日）。ISBN 4-7952-6858-4 ISBN 4-7952-6889-4。http://www2.odn.ne.jp/yuseisha/daiki/comp-c.htm。 

関連項目

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

外部リンク

• 世界大百科事典 第2版『メルセンヌ数』 - コトバンク
• リュカテストによるメルセンヌ素数の発見法 (PDF)
• Weisstein, Eric W. "Mersenne number". mathworld.wolfram.com (英語).
• Weisstein, Eric W. "Mersenne prime". mathworld.wolfram.com (英語).
• Mersenne Primes: History, Theorems and Lists（英語）
• The Largest Known Primes（英語）
• GIMPS（英語）