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

デリック・ヘンリー・レーマー（英語版）は、エドゥアール・リュカの判定法を改良し、今日ではリュカ–レーマー・テスト(英語: 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 = ω 2 n + ω ¯ 2 n ,   ω = 2 + 3 ,   ω ¯ = 2 − 3 {\displaystyle S_{n}=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}},\ \omega =2+{\sqrt {3}},\ {\bar {\omega }}=2-{\sqrt {3}}} となる。 以下、Q = 2p − 1 とする。 S p − 2 ≡ 0 ( mod Q ) ⇒ {\displaystyle S_{p-2}\equiv 0{\pmod {Q}}\Rightarrow } Qは素数。 まず、Sp−2 ≡ 0 (mod Q) であれば、Q が素数であることを証明する。 Sp−2 ≡ 0 (mod Q) で、かつ Q が合成数だと仮定する。すると、Sp−2 は Q の一番小さい素因数 F を用いて Sp−2 = kF（kは自然数）と表せる。Sn の一般項から ω 2 p − 2 + ω ¯ 2 p − 2 = k F {\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kF} となる。 ω ω ¯ = 1 {\displaystyle \omega {\bar {\omega }}=1} なので、両辺に ω 2 p − 2 {\displaystyle \omega ^{2^{p-2}}} をかけて、 ω 2 p − 1 + 1 = k F ω 2 p − 2 {\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}} 1を移項し、両辺を2乗すると、 ω 2 p = k 2 F 2 ω 2 p − 1 − 2 k F ω 2 p − 2 + 1. {\displaystyle \omega ^{2^{p}}=k^{2}F^{2}\omega ^{2^{p-1}}-2kF\omega ^{2^{p-2}}+1.} よって、 ω 2 p ≡ 1 ( mod F ) {\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}} となる。ここで、 a + b 3 {\displaystyle a+b{\sqrt {3}}} と c + d 3 {\displaystyle 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 3 ≡ ω n ( mod F ) ,   0 ≦ a n < F ,   0 ≦ b n < F } {\displaystyle 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 となる。 ω 2 p ≡ 1 ( mod F ) {\displaystyle \omega ^{2^{p}}\equiv {1}{\pmod {F}}} より、2p は e の倍数。2p > e ならば、e = 2t (tは0以上p−1以下の整数)となる。言い換えれば 2p−1 は e の倍数となる。つまり、 ω 2 p − 1 ≡ 1 ( mod F ) {\displaystyle \omega ^{2^{p-1}}\equiv {1}{\pmod {F}}} となるはずである。しかし、上の式、 ω 2 p − 1 + 1 = k F ω 2 p − 2 {\displaystyle \omega ^{2^{p-1}}+1=kF\omega ^{2^{p-2}}} より、 ω 2 p − 1 ≡ − 1 ( mod F ) {\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {F}}} よって、2p = e となる。しかし、F は Q の一番小さい素因数なので、 F ≦ Q < 2 p 2 . {\displaystyle 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 が素数 ⇒ S p − 2 ≡ 0 ( mod Q ) . {\displaystyle \Rightarrow S_{p-2}\equiv 0{\pmod {Q}}.} 次に p が奇素数であり、かつ Q が素数であれば、Sp−2 ≡ 0 (mod Q) であることを証明する。 この証明をするうえで、平方剰余の相互法則を使う。 まず、二項定理より、 ( 1 + 3 ) Q = 1 + ( Q 1 ) ( 3 ) + ( Q 2 ) ( 3 ) 2 + . . . + ( Q Q − 1 ) ( 3 ) Q − 1 + ( 3 ) Q {\displaystyle (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 は素数なので ( Q n ) = Q ! n ! ( Q − n ) ! {\displaystyle {\begin{pmatrix}Q\\n\end{pmatrix}}={\frac {Q!}{n!(Q-n)!}}} は n = 0, Q の場合を除いて Q の倍数。よって、 ( 1 + 3 ) Q ≡ 1 + ( 3 ) Q ( mod Q ) = 1 + 3 Q − 1 2 ( 3 ) {\displaystyle {\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) で、平方剰余の相互法則により、 ( Q 3 ) ( 3 Q ) = − 1 {\displaystyle \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)よって ( 3 Q ) = − 1 , ( Q 3 ) = 1. {\displaystyle \left({\frac {3}{Q}}\right)={-1},\left({\frac {Q}{3}}\right)=1.} つまり、 3 Q − 1 2 ≡ − 1 ( mod Q ) {\displaystyle 3^{\frac {Q-1}{2}}\equiv {-1}{\pmod {Q}}} が成り立ち、よって、 ( 1 + 3 ) Q ≡ 1 + ( − 1 ) 3 ( mod Q ) . {\displaystyle (1+{\sqrt {3}})^{Q}\equiv {1+(-1){\sqrt {3}}}{\pmod {Q}}.} 両辺に ( 1 + 3 ) ( Q + 1 2 ) {\displaystyle (1+{\sqrt {3}})\left({\frac {Q+1}{2}}\right)} を掛けて、 ( 1 + 3 ) Q + 1 ( Q + 1 2 ) ≡ − Q − 1 ( mod Q ) . {\displaystyle (1+{\sqrt {3}})^{Q+1}\left({\frac {Q+1}{2}}\right)\equiv {-Q-1}{\pmod {Q}}.} この式は ( 1 + 3 ) 2 = 4 + 2 3 = 2 ω {\displaystyle (1+{\sqrt {3}})^{2}=4+2{\sqrt {3}}=2\omega } を利用して、 ( Q + 1 ) 2 Q − 1 2 ω Q + 1 2 ≡ 2 Q − 1 2 ω Q + 1 2 ( mod Q ) ≡ − 1 ( mod Q ) {\displaystyle (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補充法則 ( 2 Q ) = ( − 1 ) Q 2 − 1 8 = 1 {\displaystyle \left({\frac {2}{Q}}\right)=(-1)^{\frac {Q^{2}-1}{8}}={1}} により、 2 Q − 1 2 ≡ 1 ( mod Q ) . {\displaystyle 2^{\frac {Q-1}{2}}\equiv {1}{\pmod {Q}}.} よって、 ω Q + 1 2 ≡ − 1 ( mod Q ) . {\displaystyle \omega ^{\frac {Q+1}{2}}\equiv {-1}{\pmod {Q}}.} ここで、 Q + 1 2 = 2 p − 1 {\displaystyle {\frac {Q+1}{2}}=2^{p-1}} なので、 ω 2 p − 1 ≡ − 1 ( mod Q ) {\displaystyle \omega ^{2^{p-1}}\equiv {-1}{\pmod {Q}}} となる。両辺に ω ¯ 2 p − 2 {\displaystyle {\bar {\omega }}^{2^{p-2}}} を掛けて、 ω 2 p − 1 ω ¯ 2 p − 2 = ( ω 2 p − 2 ) 2 ( ω ¯ 2 p − 2 ) = ω 2 p − 2 ≡ − ω ¯ 2 p − 2 ( mod Q ) . {\displaystyle \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}}.} 両辺に ω ¯ 2 p − 2 {\displaystyle {\bar {\omega }}^{2^{p-2}}} を足して、 ω 2 p − 2 + ω ¯ 2 p − 2 = S p − 2 ≡ 0 ( mod Q ) . {\displaystyle \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 ≡ 0 ( mod Q ) ⟺ ∀ u ∈ N [ 2 ≦ u < Q → Q ≢ 0 ( mod u ) ] {\displaystyle 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.